我有大量的點數據（2D）（每秒數千）。在這張地圖上，我有幾個固定的多邊形（幾十到幾百個）。確定一個點的多邊形是
我想確定它所在的多邊形（多邊形可以相交）的每個點的實時（在功能相當強大的筆記本電腦上的幾毫秒的順序）。 我以爲我會用ray casting algorithm。然而，我需要一種預處理數據的方式，以避免掃描每個多邊形。 因此，我考慮使用樹方法（PM四叉樹或Rtree？）。有沒有其他相關的方法？ 是否有一個很好的PM Quadtree實現你會推薦（無論使用哪種語言，最好是C（++），Java或Python）？
我已經開發了一個Java庫中的幾個多維索引，它可以找到here。它包含R *樹，STR-Tree，4個四叉樹（2個用於點，2個用於矩形）和一個臨界樹（可通過交錯座標來用於空間數據）。我還開發了PH-Tree。
有所有的基於直線/點的樹，所以你將不得不把你的多邊形轉換成矩形，例如通過計算邊界框。對於所有返回的邊界框，如果多邊形確實與點相交，則必須手動計算。 如果你的矩形不太拉長，這應該仍然是有效的。
我通常會發現PH-Tree是最有效的樹，如果一個點與100個矩形或更少（甚至更好，10個或更少）相交，則它具有快速構建時間和非常快的查詢時間。 STR/R * - 樹脂在更大的重疊尺寸（1000+）下效果更好。四叉樹有點不可靠，當插入數百萬個元素時，它們在數值精度上存在問題。
假設每個查詢有一百萬個矩形和平均一個結果的三維樹，PH-Tree在我的桌面（i7 4xxx）上每個查詢需要大約3微秒，即每毫秒300個查詢。