Intersection and difference of two rectangles
Solution 1
Here is a complete solution for you.
Methods in the class are ordered illogically so that the important parts are visible without scrolling.
import itertools
class Rectangle:
def intersection(self, other):
a, b = self, other
x1 = max(min(a.x1, a.x2), min(b.x1, b.x2))
y1 = max(min(a.y1, a.y2), min(b.y1, b.y2))
x2 = min(max(a.x1, a.x2), max(b.x1, b.x2))
y2 = min(max(a.y1, a.y2), max(b.y1, b.y2))
if x1<x2 and y1<y2:
return type(self)(x1, y1, x2, y2)
__and__ = intersection
def difference(self, other):
inter = self&other
if not inter:
yield self
return
xs = {self.x1, self.x2}
ys = {self.y1, self.y2}
if self.x1<other.x1<self.x2: xs.add(other.x1)
if self.x1<other.x2<self.x2: xs.add(other.x2)
if self.y1<other.y1<self.y2: ys.add(other.y1)
if self.y1<other.y2<self.y2: ys.add(other.y2)
for (x1, x2), (y1, y2) in itertools.product(
pairwise(sorted(xs)), pairwise(sorted(ys))
):
rect = type(self)(x1, y1, x2, y2)
if rect!=inter:
yield rect
__sub__ = difference
def __init__(self, x1, y1, x2, y2):
if x1>x2 or y1>y2:
raise ValueError("Coordinates are invalid")
self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2
def __iter__(self):
yield self.x1
yield self.y1
yield self.x2
yield self.y2
def __eq__(self, other):
return isinstance(other, Rectangle) and tuple(self)==tuple(other)
def __ne__(self, other):
return not (self==other)
def __repr__(self):
return type(self).__name__+repr(tuple(self))
def pairwise(iterable):
# https://docs.python.org/dev/library/itertools.html#recipes
a, b = itertools.tee(iterable)
next(b, None)
return zip(a, b)
# 1.
a = Rectangle(0, 0, 1, 1)
b = Rectangle(0.5, 0.5, 1.5, 1.5)
print(a&b)
# Rectangle(0.5, 0.5, 1, 1)
print(list(a-b))
# [Rectangle(0, 0, 0.5, 0.5), Rectangle(0, 0.5, 0.5, 1), Rectangle(0.5, 0, 1, 0.5)]
# 2.
b = Rectangle(0.25, 0.25, 1.25, 0.75)
print(a&b)
# Rectangle(0.25, 0.25, 1, 0.75)
print(list(a-b))
# [Rectangle(0, 0, 0.25, 0.25), Rectangle(0, 0.25, 0.25, 0.75), Rectangle(0, 0.75, 0.25, 1), Rectangle(0.25, 0, 1, 0.25), Rectangle(0.25, 0.75, 1, 1)]
# 3.
b = Rectangle(0.25, 0.25, 0.75, 0.75)
print(a&b)
# Rectangle(0.25, 0.25, 0.75, 0.75)
print(list(a-b))
# [Rectangle(0, 0, 0.25, 0.25), Rectangle(0, 0.25, 0.25, 0.75), Rectangle(0, 0.75, 0.25, 1), Rectangle(0.25, 0, 0.75, 0.25), Rectangle(0.25, 0.75, 0.75, 1), Rectangle(0.75, 0, 1, 0.25), Rectangle(0.75, 0.25, 1, 0.75), Rectangle(0.75, 0.75, 1, 1)]
# 4.
b = Rectangle(5, 5, 10, 10)
print(a&b)
# None
print(list(a-b))
# [Rectangle(0, 0, 1, 1)]
# 5.
b = Rectangle(-5, -5, 10, 10)
print(a&b)
# Rectangle(0, 0, 1, 1)
print(list(a-b))
# []
Intersection is based on SFML's implementation. It is proven correct and is not interesting to explain.
The difference, however, was a lot of fun to make.
Consider the following cases and compare them with corresponding examples at the bottom of the code. The method may return from 0 to 8 rectangles!
It works by finding all the vertical (xs
) and horizontal (ys
) lines that go through our rectangle (all the black and grey lines on the picture).
The coordinate sets are turned into sorted
lists and taken pairwise
([a, b, c]
becomes [(a, b), (b, c)]
).
The product
of such horizontal and vertical segments gives us all the rectangles that we divided the original one into by these lines.
All that remains is to yield
all of these rectangles except the intersection.
Solution 2
Oleh Prypin was extremely helpful with the provided code. The following is a refactored version of the same.
from itertools import product, tee
def test():
print('Example 1:')
a = Rectangle(1, 1, 5, 5)
b = Rectangle(3, 3, 7, 7)
print(a & b)
print(list(a - b))
##########################
print('Example 2:')
b = Rectangle(3, 2, 7, 4)
print(a & b)
print(list(a - b))
##########################
print('Example 3:')
b = Rectangle(2, 2, 4, 4)
print(a & b)
print(list(a - b))
##########################
print('Example 4:')
b = Rectangle(6, 2, 10, 6)
print(a & b)
print(list(a - b))
##########################
print('Example 5:')
b = Rectangle(0, 0, 6, 6)
print(a & b)
print(list(a - b))
##########################
print('Example 6:')
b = Rectangle(2, 0, 4, 6)
print(a & b)
print(list(a - b))
def pairwise(iterable):
"s -> (s0, s1), (s1, s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
class Rectangle:
__slots__ = '__x1', '__y1', '__x2', '__y2'
def __init__(self, x1, y1, x2, y2):
self.__setstate__((min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)))
def __repr__(self):
return '{}({})'.format(type(self).__name__, ', '.join(map(repr, self)))
def __eq__(self, other):
return self.data == other.data
def __ne__(self, other):
return self.data != other.data
def __hash__(self):
return hash(self.data)
def __len__(self):
return 4
def __getitem__(self, key):
return self.data[key]
def __iter__(self):
return iter(self.data)
def __and__(self, other):
x1, y1, x2, y2 = max(self.x1, other.x1), max(self.y1, other.y1), \
min(self.x2, other.x2), min(self.y2, other.y2)
if x1 < x2 and y1 < y2:
return type(self)(x1, y1, x2, y2)
def __sub__(self, other):
intersection = self & other
if intersection is None:
yield self
else:
x, y = {self.x1, self.x2}, {self.y1, self.y2}
if self.x1 < other.x1 < self.x2:
x.add(other.x1)
if self.y1 < other.y1 < self.y2:
y.add(other.y1)
if self.x1 < other.x2 < self.x2:
x.add(other.x2)
if self.y1 < other.y2 < self.y2:
y.add(other.y2)
for (x1, x2), (y1, y2) in product(pairwise(sorted(x)),
pairwise(sorted(y))):
instance = type(self)(x1, y1, x2, y2)
if instance != intersection:
yield instance
def __getstate__(self):
return self.x1, self.y1, self.x2, self.y2
def __setstate__(self, state):
self.__x1, self.__y1, self.__x2, self.__y2 = state
@property
def x1(self):
return self.__x1
@property
def y1(self):
return self.__y1
@property
def x2(self):
return self.__x2
@property
def y2(self):
return self.__y2
@property
def width(self):
return self.x2 - self.x1
@property
def height(self):
return self.y2 - self.y1
intersection = __and__
difference = __sub__
data = property(__getstate__)
if __name__ == '__main__':
test()
Noctis Skytower
BY DAY: Computer Science Faculty @ PCC "I am Alpha and Omega, the beginning and the end, the first and the last." —Revelation 22:13 "For, behold, I create new heavens and a new earth: and the former shall not be remembered, nor come into mind." —Isaiah 65:17 "It is better to trust in the Lord than to put confidence in man. It is better to trust in the Lord than to put confidence in princes." —Psalm 118:8-9
Updated on June 09, 2022Comments
-
Noctis Skytower almost 2 years
Searching the internet has not given a satisfactory solution for the following problem. Given a class
Rectangle
defined as the following:class Rectangle: def __init__(self, x1, y1, x2, y2): if x1 > x2 or y1 > y2: raise ValueError('coordinates are invalid') self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2 @property def width(self): return self.x2 - self.x1 @property def height(self): return self.y2 - self.y1 def bounds(self, other): return Rectangle(min(self.x1, other.x1), min(self.y1, other.y1), max(self.x2, other.x2), max(self.y2, other.y2)) def intersect(self, other): return self.x1 < other.x2 and self.x2 > other.x1 and \ self.y1 < other.y2 and self.y2 > other.y1
How would you create a method to get the intersection and a generator to get the difference of two rectangles? Presumably, a more complete implementation of the following methods are needed, but it is not clear to me what should be written.
def __and__(self, other): if self.intersect(other): # return a new rectangle that provides # the intersection between self and other return None def __sub__(self, other): take_away = self & other if take_away is None: return self if take_away is self: return None return self.get_partitions(take_away) def get_partitions(self, take_away): # yield 1 or 3 rectangles that are not part of take_away # alternative: # yield 1 or 2 overlapping rectangles not part of take_away
Does anyone have an elegant implementation for these methods? My hope is to avoid writing code for every conceivable case that might be encountered.
-
Noctis Skytower almost 10 yearsAssuming your implementation is correct, I should be able to use your code to implement the
__and__
method in my class. Any ideas for theget_partitions
method? -
Oleh Prypin almost 10 years@NoctisSkytower Updated with complete class.
-
Noctis Skytower almost 10 yearsThanks for your help! Being able to rely on the smarts of other people is rather nice sometimes.
-
Noctis Skytower over 9 yearsAfter finding some extra time, your code finally got refactored as seen down below.