两个矩形的交集和差异

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

有没有一种优雅的实现方法？我的希望是避免为每个可能遇到的情况编写代码。

- Noctis Skytower

---

你意识到如果“self”完全包含“other”的话会发生什么吗？ - Oleh Prypin

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个矩形！

该方法通过查找穿过矩形的所有垂直线（xs）和水平线（ys

）来工作（图片上的所有黑色和灰色线条）。

坐标集转换为sorted列表，并进行pairwise操作（[a，b，c]变成[(a，b)，(b，c)]）。

这样水平和垂直线段的product会给我们原始矩形由这些线分割成的所有矩形。

现在只需yield出所有这些矩形，除了交叉的那一个。

- Oleh Prypin

---

假设你的实现是正确的，我应该能够使用你的代码来实现我的类中的__and__方法。对于get_partitions方法有什么想法吗？ - Noctis Skytower

@NoctisSkytower 已更新完整的类。 - Oleh Prypin

谢谢你的帮助！有时候能够依靠其他人的智慧真是太好了。 - Noctis Skytower

在找到一些额外的时间后，你的代码最终被重构如下所示。 - Noctis Skytower

Answer 2

Oleh Prypin 在提供的代码方面非常有帮助。以下是同样代码的重构版本。

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

Answer 3

为了完整的程序，Rectangle类被用作实际示例以展示其用法：

# The robots have requested your help setting up a new base on the
# island. They need you to define the visibility of a building from the
# southern edge of the base. To help you out, you have been given a map
# of the buildings in the complex. The map is an orthogonal projection
# of each of the buildings onto a horizontal plane. It is oriented on a
# rectangular coordinate system so that the positive x-axis points east
# and the positive y-axis points north. No two buildings in the map
# overlap or touch. Each of the buildings have perfectly rectangular
# sides and are aligned from north to south and from east to west. The
# map is a list of buildings. Every building is presented as the list
# with coordinate of south-west corner, coordinate of north-east corner
# and height - [Xsw, Ysw, Xne, Yne, height]. We need to determinate how
# many of the buildings are visible from the area just south of the base
# (excluding the angle of vision, just using projection.) See the
# illustration below.

# Input: Building coordinates and heights as a list of lists. The
# coordinates are integers. The heights are integers or floats.

# Output:The quantity of visible buildings as an integer.

# Example:
# checkio([
#     [1, 1, 4, 5, 3.5],
#     [2, 6, 4, 8, 5],
#     [5, 1, 9, 3, 6],
#     [5, 5, 6, 6, 8],
#     [7, 4, 10, 6, 4],
#     [5, 7, 10, 8, 3]
# ]) == 5 #"First"
# checkio([
#     [1, 1, 11, 2, 2],
#     [2, 3, 10, 4, 1],
#     [3, 5, 9, 6, 3],
#     [4, 7, 8, 8, 2]
# ]) == 2 #"Second"
# assert checkio([
#     [1, 1, 3, 3, 6],
#     [5, 1, 7, 3, 6],
#     [9, 1, 11, 3, 6],
#     [1, 4, 3, 6, 6],
#     [5, 4, 7, 6, 6],
#     [9, 4, 11, 6, 6],
#     [1, 7, 11, 8, 3.25]
# ]) == 4 #"Third"

# How it is used: This concept is useful for image recognition systems
# and graphical systems. When rendering of 3D model you should determine
# the visibility of the surfaces. This concept also can be applied in
# architecture and city planning, allowing you to plan out which sides
# of a building will receive sunlight, or if a building will block
# natural light in another building.

# Precondition: 0 < |buildings| < 10> 10
# ∀ x ∈ coordinate : x is an integer; 0 ≤ x ≤10
# ∀ h ∈ heights : x is an integer or a float; 0 < h ≤20

################################################################################

from itertools import combinations, product, starmap, tee
from pprint import pprint
from random import randint

################################################################################

TESTS = {
    "0. Basics": [
        #First
        {
            "input":
                [
                    [1, 1, 4, 5, 3.5],
                    [2, 6, 4, 8, 5],
                    [5, 1, 9, 3, 6],
                    [5, 5, 6, 6, 8],
                    [7, 4, 10, 6, 4],
                    [5, 7, 10, 8, 3]
                ],
            "answer": 5,
            "explanation": [5, 1, 3, 4, 0, 2]
        },
        #Second
        {
            "input":
                [
                    [1, 1, 11, 2, 2],
                    [2, 3, 10, 4, 1],
                    [3, 5, 9, 6, 3],
                    [4, 7, 8, 8, 2]
                ],
            "answer": 2
        },
        #Third
        {
            "input":
                [
                    [1, 1, 3, 3, 6],
                    [5, 1, 7, 3, 6],
                    [9, 1, 11, 3, 6],
                    [1, 4, 3, 6, 6],
                    [5, 4, 7, 6, 6],
                    [9, 4, 11, 6, 6],
                    [1, 7, 11, 8, 3.25]
                ],
            "answer": 4
        },
        #Alone
        {
            "input":
                [
                    [0, 0, 1, 1, 10]
                ],
            "answer": 1
        },
        #Shadow
        {
            "input":
                [
                    [2, 2, 3, 3, 4],
                    [2, 5, 3, 6, 4]
                ],
            "answer": 1
        },
    ],
    "1. Extra": [
        #H1
        {
            "input":
                [
                    [1, 1, 3, 3, 20],
                    [3, 4, 5, 6, 10],
                    [5, 1, 7, 3, 20],
                    [1, 7, 7, 9, 20]
                ],
            "answer": 4
        },
        #H2
        {
            "input":
                [
                    [1, 1, 3, 3, 20],
                    [3, 4, 5, 6, 20],
                    [5, 1, 7, 3, 20],
                    [1, 7, 7, 9, 20]

                ],
            "answer": 3
        },
        #H3
        {
            "input":
                [
                    [0, 1, 1, 2, 2.5],
                    [0, 3, 1, 4, 3.5],
                    [0, 5, 1, 6, 1.5],
                    [3, 0, 4, 2, 30],
                    [5, 0, 6, 2, 2],
                    [7, 0, 8, 2, 2],
                    [4, 3, 8, 4, 2],
                    [4, 5, 5, 6, 1],
                    [7, 5, 8, 6, 3]
                ],
            "answer": 7
        },
        #H4
        {
            "input":
                [
                    [0, 0, 10, 1, 10],
                    [3, 3, 4, 4, 1],
                    [5, 5, 6, 6, 1],
                    [7, 7, 8, 8, 1]
                ],
            "answer": 1
        },
    ],
    "2. Random": [
        #Half-Random
        {
            "input":
                [
                    [0, 0, 10, 1, 10],
                    [3, 3, 4, 4, randint(1, 9)],
                    [5, 5, 6, 6, randint(1, 9)],
                ],
            "answer": 1
        },

        #Half-Random
        {
            "input":
                [
                    [1, 1, 2, 2, 1],
                    [randint(3, 5), randint(3, 5), randint(6, 8), randint(6, 8), 1]
                ],
            "answer": 2
        },
    ]
}

################################################################################

def test():
    for category, tests in sorted(TESTS.items()):
        for test in tests:
            i, a = test['input'], test['answer']
            o = checkio(i)
            if o != a:
                print('Category:', category)
                print('  Input:')
                pprint(i, indent=8)
                print('  Output:', o)
                print('  Answer:', a)

def checkio(buildings):
    buildings = sorted(starmap(Building, buildings), key=lambda b: b.z)
    for a, b in combinations(buildings, 2):
        if a.seen:
            a.cover(b)
    return sum(b.seen for b in buildings)

################################################################################

class Building:

    def __init__(self, x1, y1, x2, y2, height):
        self.rect = [Rectangle(x1, 0, x2, height)]
        self.z = min(y1, y2)

    def __str__(self):
        return 'Z = {}; {}'.format(self.z, self.rect)

    def cover(self, other):
        for s in self.rect:
            other.rect = list(flatten(o - s for o in other.rect))

    @property
    def seen(self):
        return bool(self.rect)

def flatten(iterable):
    if isinstance(iterable, Rectangle):
        raise TypeError()
    for item in iterable:
        try:
            yield from flatten(item)
        except TypeError:
            yield item

################################################################################

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__)

def pairwise(iterable):
    "s -> (s0, s1), (s1, s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

################################################################################

if __name__ == '__main__':
    test()

- Noctis Skytower