使用python检测和裁剪重叠矩形的高效库

Question

我有一组相互重叠的矩形。我需要检测一组矩形中是否存在重叠。如果存在重叠，则需要更新坐标，以便矩形集不再重叠。我想知道是否有适合这项任务的现有python库。

此操作将应用于million+矩形集，因此算法效率和利用图形处理器也将是重要的。

Answer 1

GEOS的漂亮界面可能就是您正在寻找的库，但我从未将其用于此目的。

在这种情况下，使用自己的代码可能会更容易。该算法是一种简单的扫描线算法，每个矩形的平均复杂度与log(N)成正比。

A)每个矩形由四个坐标表征，左、右、上、下。

B)将按照矩形的左坐标顺序处理矩形

c)使用区间树来维护每个矩形的上下范围，这些矩形的左边缘已经被遇到，而右边缘还没有被遇到

D)维护当前在区间树中的所有矩形的按右边缘排序的优先级队列

1)获取要处理的第一个或下一个矩形。如果没有更多的可用，则退出。

2)当优先级队列上的任何元素的优先级小于或等于此矩形的左值时，从优先级队列中删除该元素，并从间隔树中删除关联的元素。

3)在区间树中搜索与该矩形的顶部-底部范围重叠；处理找到的每个重叠部分。

4)将该矩形的自上而下范围插入到区间树中，并在优先级队列中添加一个元素，该元素的优先级设置为该矩形的右值，引用添加到区间树中的区间。

5)返回步骤1)获取下一个矩形。