两个矩形的交集和差异 [英] Intersection and difference of two rectangles
问题描述
Rectangle 定义如下： class Rectangle：
def __init __（self，x1，y1，x2，y2）：
if x1> x2或y1> y2：
增加ValueError（'坐标无效'）
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 （自我，其他）：
返回矩形，
max（self.x2，other.x2），max（self.y2，other.y2））
def intersect（self，other）：
return self。 x1< other.x2和self.x2> other.x1和\ $ b $ b self.y1< other.y2和self.y2> other.y1
您将如何创建一个方法来获取交点和生成器以获取两个矩形的区别？可能需要更完整地实现以下方法，但是我不清楚应该写什么。
<$ p $ b $
def __and __（self，other）：
如果self.intersect（other）：
＃返回一个新的矩形，它提供
＃self和其他
返回无
def __sub __（self，other）：
take_away = self&其他
如果take_away是None：
返回self
如果take_away是self：
返回None
返回self.get_partitions（take_away）
def get_partitions（self，take_away）：
＃产生1或3个不是take_away的一部分的矩形
＃alternative：
＃产生1或2个重叠的矩形不是take_away的一部分
有没有人有这些方法的优雅实现？我希望避免为每个可能遇到的情况编写代码。 解决方案
这是一个完整的解决方案。
在类中的方法是不合逻辑的，这样重要的部分就可以在不滚动的情况下显示出来。
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（min max（a.x1，a.x2），max（b.x1，b.x2））
y2 = min（max（a.y1，a.y2），max（b.y1，b.y2 ））
如果x1
__and__ =交点
def差值（self，other）：
inter = self& other
如果不是inter：
yield self
return
xs = {self.x1，self.x2}
ys = {self.y 1，self.y2}
如果self.x1< other.x1< self.x2：xs.add（other.x1）;
如果self.x1< other.x2< self.x2：xs。添加（other.x2）
如果self.y1< other.y1< self.y2：ys.add（other.y1）
如果self.y1< other.y2< self.y2：ys。在itertools.product中添加（other.y2）
（x1，x2），（y1，y2） ）：
rect = type（self）（x1，y1，x2，y2）
if rect！= inter：
yield rect
__sub__ = difference
def __init __（self，x1，y1，x2，y2）：
如果x1> x2或y1> y2：
raise ValueError（坐标无效）
self.x1， self.y1，self.x2，self.y2 = x1，y1，x2，y2
$ b $ def __iter __（self）：
yield self.x1
yield self.y1
产生self.x2
产生self.y2
def __eq __（self，other）：
return isinstance（other，Rectangle）a nd tuple（self）== tuple（other）
def __ne __（self，other）：
return not（self == other）
def __repr __（self）：
返回类型（self）.__名称__ + repr（tuple（self））
def pairwise（可迭代）：
＃https://docs.python.org /dev/library/itertools.html#recipes
a，b = itertools.tee（可迭代）
下一个（b，无）
返回zip（a，b）
$ b $ 1.
a =矩形（0,0,1,1）
b =矩形（0.5,0.5,1.5,1.5）
print（a& b）
＃矩形（0.5,0.5,1,1）
print（list（ab））
＃[矩形（0,0,0,0.5），矩形（0,0.5,0.5,0.5,0.5,0.5） 1），Rectangle（0.5,0,1,0.5）]
＃2.
b =矩形（0.25,0.25,1.25,0.75）
print（a& b）
＃Rectangle（0.25,0.25,1,0.75）
print（list（ab））
＃[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 =矩形（0.25，0.25，0.75，0。 75）
print（a& b）
＃矩形（0.25,0.25,0.75,0.75）
print（list（ab））
＃[Rectangle（0，0， （0.25,0.75,0.25,0.25,0.25,0.25,0.25,0.75,0.0,0.25,0.25,0.75），矩形（0,0.75,0.25,1），矩形（0.25,0,0.75,0.25），矩形（0.25,0.75,0.75,1），矩形（0.75,0,1,0.25），Rectangle（0.75,0.25,1,0.75），Rectangle（0.75,0.75,1,1）]
＃4.
b = Rectangle（ （b）
print（a& b）
＃None
print（list（ab））
＃[Rectangle（0，0，1，1， ）]
＃5.
b =矩形（-5，-5，10，10）
print（a& b）
＃Rectangle（0，0 ，1，1）
print（list（ab））
＃[]
<交叉点基于 SFML的实现
然而，这种差异带来了很多乐趣。
考虑以下情况并将其与代码底部的相应示例进行比较。该方法可能会返回0到8个矩形！
xs ）和水平线（ 坐标系变成
sorted 列表并取 pairwise （ [a，b，c] 变成 [（a，b），（b，c）] ）。
$ b $ product 这样的水平和垂直线段给了我们所有的矩形，我们用这些线条分割了原来的矩形。
剩下的是 yield 所有这些矩形，除了交集。
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 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.
这篇关于两个矩形的交集和差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
