高效的庫檢測和剪切重疊的矩形python

Question

我有一組相互重疊的矩形。我需要檢測一組矩形中是否存在重疊。如果存在重疊，那麼我需要更新座標，以便矩形的集合不再重疊。我想知道是否有適合這個任務的現有python庫。

該操作將應用於數百萬個矩形，所以算法效率和利用GPU也很重要。

Answer 1

GEOS的界面可能是您正在尋找的庫，但我從未用於此目的。

在這種情況下，您可能更容易推出自己的產品。該算法是一種簡單的掃描線算法，每個矩形的平均複雜度與log（N）成比例。

A）每個矩形的特點是四個座標，左，右，上，下。

B）的矩形將在其左的順序座標

c）中的區間樹被用於保持用於每個矩形，其左邊緣已經遇到和右邊緣還未上下範圍被處理遇到

d）優先級隊列被保持，由右邊緣有序的，當前處於區間樹

1中的所有的矩形的）獲取將要處理的第一或下一個矩形。如果沒有更多可用，請退出。

2）雖然優先級隊列上的任何元素的優先級小於或等於此矩形的左值，但請從優先級隊列中刪除該元素，並從間隔樹中刪除相關元素。

3）搜索間隔樹與此矩形的上下範圍重疊;處理找到的每個重疊。

4）將此矩形的頂部 - 底部範圍插入到間隔樹中，並將優先級隊列中的元素添加到優先級設置爲右側的矩形中，引用添加到間隔樹。

5）返回步驟1）獲取下一個矩形。