軸對齊矩形相交

Question

我需要一個算法，需要軸對準的矩形的一個未排序的陣列和 返回任何一對矩形的重疊

每個矩形具有兩個變量中，左上角的座標和在右下角

Answer 1

這可能是有點複雜的面試，要看是什麼樣的工作， 這是一個幾何計算一種算法，

答案可以在這裏找到： http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf

Answer 2

下面是在DuduAlul的鏈接中提出的交集算法的簡要說明。

該解決方案需要使用能夠執行範圍查詢的搜索樹。範圍查詢要求K1和K2之間的值的所有項目，並且它應該是O（R + log N）操作，其中N是樹項目的總數，R是結果的數目。

該算法採用掃描方式：

1）排序的所有左，右邊緣的矩形，根據自己的X值，到列表L.

2）創建一個新的空範圍搜索樹T，爲矩形的頂部Y的排序/塔底

3）創建獨特的矩形對

4）導線L的升序的一個新的空的結果集RS。爲以L所有的V：

     如果V.isRightEdge（）

            T.remove（V.rectangle.top）

           Ť .remove（V.rectangle.bottom）

     其他

           對於所有u在T.getRange（V.rectangle.top，V.rectangle.bottom）

                  RS.add （< V.rectangle，U.rectangle>）

            T.add（V.rectangle。頂部）

            T.add（V.rectangle.bottom）

5）返回RS

---

的時間複雜度是O（R + N日誌N），其中R是交叉點的實際數量。

- 編輯 -

我想通了，解決的辦法是不完全正確 - 在樹T的相交測試錯過某些情況下。樹應保持Y間隔而不是Y值，理想情況下應該是Interval Tree。

Answer 3

Sweep and prune是很多物理引擎解決這類問題的方法。

David Baraff's SIGGRAPH notes有一個很好的解釋，在7.2節邊界框下。