高效組重疊矩形

Question

組合重疊矩形的最佳方法是什麼？我試過使用OpenCV，但grouprectangles方法不能按預期工作。

我想過做這樣的事情：

L = [every rectangle] 
L_next = [] 
while not L.empty(): 
    for rectangle in L: 
     L.remove(rectangle) 
     for other_rectangle in L: 
      if rectangle overlaps with other_rectangle: 
       L_next += rectangle + other_rectangle 
    L = L_next 
    L_next = [] 

由於每個未合併將從下一個列表被丟棄，在最壞的情況下矩形，我有n/2迭代外部循環。這兩個內部循環應該執行n和n - 1次，以便在最壞的情況下算法應該大致爲O(n^3)，假設我沒有遺漏任何內容並且每個步驟僅需要O(1)。

問題：

1）需要用等價類或東西的程度，以正確合併矩形的羣體。 Boost有這樣的嗎？

2）這似乎是必須經常進行的操作，所以我很驚訝沒有找到更多的材料。那是怎麼回事？ 3）假設真的沒有已經實現的東西來做到這一點，有沒有人有一些建議，以改善我的方法？

4）查看兩個矩形重疊的最佳方法是什麼？

Answer 1

我會看看pygame.Rect.collide方法來回應你的問題。由於矩形重疊檢測在遊戲中非常普遍，我猜他們的實現在計算複雜性方面非常好。