確定哪些多邊形的點是從一個大組多邊形

Question

說我有一個2D平面上，覆蓋有多邊形（標識爲頂點的陣列）中，類似於：

可以說，我在這個平面上也有一個座標點，最簡單的方法是返回這個點存在於哪個多邊形中？

儘管這個例子列出了4個多邊形，但運行check on each polygon to see if the point is within it會很簡單，但我正在構建一個目前有150個多邊形的系統，並且可能會擴展到數千個，因此這樣做可能會變得非常緩慢。

那麼，是否有任何解決方案來做到這一點，不會導致遍歷所有可用的多邊形，並檢查點是否存在？

Answer 1

您可以使用kd-tree或r-tree。它可以減少搜索空間。你也可以找一個四叉樹。您可以選擇四邊形尺寸以適合多邊形，並儘量減少重疊的邊界框。