快速算法可以找到上百萬個多邊形中的數千個點？

Question

我試圖通過Web服務發現了數千點的多邊形百萬首.AT我實現Java中的算法（點在多邊形），但它需要很長的時間。而後來我在MySQL拆表，並試圖使用多線程來解決它，但仍然效率低下。有沒有更快的算法或實現來解決這個問題？

加上對多邊形的描述。二維，靜態，複雜的多邊形（也有孔）。

任何建議將不勝感激。

Answer 1

我THIK這裏是分而治之會做，你可以嘗試做subpolyons或簡化一些poonts的，也許嘗試啓發式方法的情況下，也有我的5美分。

Answer 2

測試點對一萬個多邊形是要花費大量的時間，不管你在多邊形的功能點是多麼有效。

您需要縮小搜索列表的範圍。首先爲每個多邊形制作一個邊界框，並在點位於邊界框內時僅選擇多邊形。

如果多邊形不改變，你可以每個多邊形轉換爲一組三角形。測試一個點是否在三角形中應該比測試更快，以查看它是否在任意多邊形中。儘管三角形的數量會比多邊形的數量大得多，但總體來說可能會更快。

Answer 3

如果多邊形的集合是靜態的，首先將它們註冊到空間數據結構上可能會有幫助 - 假設多邊形不會彼此重疊太多，則R-tree可能是一個不錯的選擇。

要測試一個針對多邊形集合的點，首先會找到樹中的封閉葉（O(log(n))樣式操作），然後只需要對多邊形執行完整的多邊形點測試與封閉的葉子相關聯。

這一方法應大大加快每個點測試，但需要一個額外的設置階段建立的R-樹。

希望這會有所幫助。

Answer 4

如果您處理數百萬個多邊形，則無論您的命中測試功能如何優化或有多少線程能夠解決您的查詢，您都需要某種空間分區，否則它會變得很慢。

什麼樣的空間分區？ 它取決於：

• 2D？ 3D？
• 你的多邊形是否設置爲靜態？如果不是，經常更改它？
• 你對這一套要求是什麼樣的要求？
• 它是什麼樣的多邊形？三角形？凸？凹？複雜？有孔？

我們需要更多的信息來幫助你。

編輯

下面是一個簡單的空間分割方案。

假設您的二維空間上有給定步驟的笛卡爾網格。

當您添加一個多邊形：

• 計算其邊框
• 查找與邊框
• 對於每個單元相交的所有網格單元，在一個特殊的表中添加一行。

表看起來是這樣的：cell_x，cell_y，polygon_id。添加正確的索引（至少cell_x和cell_y）

當然，你要選擇你的網格步所以大部分的多邊形奠定了不到10個細胞，否則你的桌子會迅速變得龐大。

它現在很容易在一個給定的點找到多邊形：

• 計算哪個小區的點所屬
• 獲取關聯到該小區
• 對於每個多邊形的所有多邊形，用你的hit-測試功能

這個解決方案是遠非最佳，但容易器具。