Skip to main content
 首页 » 编程设计

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

2025年05月04日11softidea

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

此操作将应用于数百万以上的矩形集,因此算法效率和利用 GPU 也很重要。

请您参考如下方法:

GEOS 的优美界面可能是您正在寻找的库,但我从未将其用于此目的。

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

A) 每个矩形都有四个坐标,左、右、上、下。

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

c) Interval Tree 用于维护每个矩形的上下范围,其左边缘已遇到且右边缘尚未遇到

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

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

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

3) 在Interval Tree中搜索与这个矩形的Top-Bottom范围重叠的部分;处理每个发现的重叠。

4) 将这个矩形的Top-Bottom范围插入到Interval Tree中,并在Priority Queue中添加一个元素,优先级设置为从矩形开始的Right值,引用添加到Interval Tree中的区间。

5) 返回步骤1)得到下一个矩形。