檢索設置包含指定點

我無法弄清楚如何在執行的方式實現這種矩形的，所以我決定要問你們。檢索設置包含指定點

我有一個矩形列表 - 實際上atm只有正方形，但我可能不得不稍後遷移到矩形，所以讓我們堅持它們，並保持它更一般 - 在2維空間。每個矩形由兩個點指定，矩形可以重疊，我不會過多關心設置時間，因爲這些矩形基本上是靜態的，並且有一些空間用於預先計算任何設置內容（如構建樹，排序，預先計算其他向量，等等）。哦，如果這是任何問題，我正在用JavaScript開發。

要我實際的問題：給定一個點，我怎麼一組包括這一點，所有的矩形？

線性方法不執行不夠好。所以我尋找比O（n）更好的表現。我讀了一些東西，比如在Bounding Volume Hierarchies和類似的東西上，但是無論我嘗試過矩形可以重疊的事實（並且我實際上想要得到所有這些東西，如果這個點位於多個矩形內）似乎總是以我的方式。

是否有什麼建議嗎？我錯過了明顯的東西嗎？ BVH是否適用於可能重疊的界限？如果是這樣，我該如何構建這樣一個可能重疊的樹？如果不是，我還能使用什麼？如果邊界在內部，外部或者沒有確定，我就無需擔心。

如果有人能想出什麼有益像一個鏈接或我是多麼的愚蠢使用BVH誇大其詞，而不是Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem我會很感激！

編輯：好的，我用R-Trees玩了一下，這正是我正在尋找的東西。事實上，我正在使用endy_c建議的RTree實現http://stackulator.com/rtree/。它表現非常好，完全滿足了我的要求。非常感謝您的支持人員！

來源

2010-10-31 Daniel Baulig

我假設你的矩形與笛卡爾座標軸對準？ – 2010-10-31 15:14:43

是的，抱歉忘了提及這一點。該設置基本上非常簡單，除了事實矩形可以重疊。這是非常微不足道的，但只要你（或我，事實上）儘量減少複雜性（有諷刺意味），它就會失去控制，並且我無法控制它。 – 2010-10-31 15:24:05

我們可以使用持久段樹來優化它到每個查詢O（log n）。 – 2016-06-30 08:33:31

你可以看看R-樹

Java code

也有一個維基，但只能發佈一個鏈接;-)

來源

2010-10-31 15:51:22 Doggett

javascript中的另一個示例：http://stackulator.com/rtree/ – 2010-10-31 15:56:46

可以劃分空間分爲網格，並且對於每個網格單元具有在該網格中存在至少部分的矩形（或矩形標識符）的列表。僅在相應網格的單元格中搜索矩形。複雜度應該是O（sqrt（n））。

另一種方法是保持X1，Y1，X2，Y2四個值排序的數組和二進制搜索你的那些4個陣列內的點。每個搜索的結果是一組矩形候選，最終結果是這四組交集。根據實現交集的方式，這應該比O（n）有效。

來源

2010-10-31 15:29:44 Dialecticus

+1好方法 - 但我們仍然需要知道'n'（點或矩形）。 – 2010-10-31 15:41:40

我真的很喜歡你的第一種方法，可能很簡單。我想過使用「網格」，實際上它基本上是BVH的appraoch（但是線性排列而不是層次結構），但對於將矩形放在多個區域的問題我從不遺憾。我會多考慮一下。 – 2010-10-31 15:41:50

檢索設置包含指定點

回答

相關問題