两个矩形的交点和差异

Question

搜索互联网并没有给出以下问题的满意解决方案.给定一个Rectangle定义如下的类:

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

你将如何创建一个方法来获得交集和生成器来获得两个矩形的差异？据推测,需要更完整地实现以下方法,但我不清楚应该写什么.

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

有没有人对这些方法有优雅的实现？我希望避免为可能遇到的每个可能的案例编写代码.

Answer 1

这是一个完整的解决方案.
类中的方法是不合逻辑的,因此重要的部分是可见的,无需滚动.

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))
# []

交叉点基于SFML的实现.它被证明是正确的,并且解释起来并不有趣.

然而,差异是很有趣的.

请考虑以下情况,并将它们与代码底部的相应示例进行比较.该方法可以从0到8个矩形返回!

它的工作原理是找到穿过矩形的所有vertical(xs)和horizo​​ntal(ys)线(图片上的所有黑线和灰线).

坐标集转换为sorted列表并拍摄pairwise([a, b, c]变为[(a, b), (b, c)]).

在product这样的水平和垂直段的给了我们一切,我们被这些线划分成原一成长方形.

剩下的就是yield除了交叉点之外的所有这些矩形.