python - 如何在python中找到矩形交点？

Question

具有 (minx, miny, maxx, maxy) 形式的平行于轴的矩形列表:

rectangles = [
    Rectangle(90,40,110,70),
    Rectangle(10,40,40,70),
    Rectangle(75,60,95,80),
    Rectangle(30,20,60,50),
    Rectangle(100,20,130,50),
    Rectangle(70,10,85,40)
]

我需要获取一组矩形的列表，其中每个矩形至少与另一个矩形相交:

[
    (Rectangle(10,40,40,70), Rectangle(30,20,60,50)), 
    (Rectangle(70,10,85,40)), 
    (Rectangle(75,60,95,80), Rectangle(90,40,110,70), Rectangle(100,20,130,50))
]

算法不能太幼稚，要快。

我尝试过的:

1. 查找 python 区间树实现 - 我找不到任何好的...
2. 我尝试了这个存储库:https://github.com/booo/rectangleintersection/blob/master/rectangleIntersection.py ，它适用于上面的示例，但无法处理真实世界的数据。
3. 我通读了 scikit image和 Shapely文档，但没有找到矩形相交的算法。

Answer 1

相交矩形可以看作是图中的连接节点，“传递”相交矩形集可以看作 Connected Components .要找出哪些矩形相交，我们首先执行 Plane Sweep .为了让它相当快，我们需要一个 Interval Tree . Banyan提供一个:

from collections import defaultdict
from itertools import chain
from banyan import SortedDict, OverlappingIntervalsUpdator

def closed_regions(rects):

    # Sweep Line Algorithm to set up adjacency sets:
    neighbors = defaultdict(set)
    status = SortedDict(updator=OverlappingIntervalsUpdator)
    events = sorted(chain.from_iterable(
            ((r.left, False, r), (r.right, True, r)) for r in set(rects)))
    for _, is_right, rect in events:
        for interval in status.overlap(rect.vertical):
            neighbors[rect].update(status[interval])
        if is_right:
            status.get(rect.vertical, set()).discard(rect)
        else:
            status.setdefault(rect.vertical, set()).add(rect)

    # Connected Components Algorithm for graphs:
    seen = set()
    def component(node, neighbors=neighbors, seen=seen, see=seen.add):
        todo = set([node])
        next_todo = todo.pop
        while todo:
            node = next_todo()
            see(node)
            todo |= neighbors[node] - seen
            yield node
    for node in neighbors:
        if node not in seen:
            yield component(node)

rect.vertical顺便说一句是元组 (rect.top, rect.bottom) .

时间复杂度为O(n log n + k) , 其中n是矩形的数量，k实际交叉点的数量。所以它非常接近最优。

编辑:因为有些困惑，我需要补充一点，矩形应该有 left <= right和 top <= bottom . IOW，它们所在坐标系的原点在左上角，而不是通常在几何学中的左下角。