两个矩形的交点和差
问题描述
搜索互联网并没有为以下问题提供令人满意的解决方案.给定一个类Rectangle，定义如下:
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.
解决方案
这里有一个完整的解决方案.
类中的方法被不合逻辑地排序，因此重要部分无需滚动即可看到.
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 基于 SFML 的实现.它被证明是正确的，解释起来并不有趣.
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.
考虑以下案例并将它们与代码底部的相应示例进行比较.该方法可能返回 0 到 8 个矩形！
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!
它的工作原理是找到穿过我们矩形的所有垂直 (xs) 和水平 (ys) 线(图片上的所有黑色和灰色线).
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).
坐标集变成sorted列表，取pairwise([a, b, c]变成[(a, b), (b, c)]).
The coordinate sets are turned into sorted lists and taken pairwise ([a, b, c] becomes [(a, b), (b, c)]).
这些水平和垂直部分的 product 为我们提供了我们用这些线将原始矩形划分成的所有矩形.
The product of such horizontal and vertical segments gives us all the rectangles that we divided the original one into by these lines.
剩下的就是yield除了交点之外的所有这些矩形.
All that remains is to yield all of these rectangles except the intersection.
相关文章