在多個多邊形上搜索點的最佳方法

Question

我需要將給定點（lat，lon）與幾個多邊形進行匹配，以確定是否存在匹配。

最簡單的方法是遍歷每個多邊形並應用點多邊形檢查算法，但這是非常昂貴的。

我做的下一個優化是爲每個多邊形（上邊界，下邊界）定義一個邊界矩形，並針對每個邊界框迭代檢查點（比較檢查多邊形中所有點的比較較少）。

是否有其他優化可能？綁定矩形點上的空間索引或geohash會有幫助嗎？

Answer 1

進一步優化：

邊界框的想法是好的。檢查點是否在邊界框中速度非常快。

如果您還需要更多的速度，你可以做更多的預先計算是這樣的：

1. 對於每個polgon創建邊框。
2. 定義覆蓋您地圖的尺寸​​相同的「圖塊」。
3. 對於每個圖塊，創建一個重疊的多邊形列表。你可以這樣做，首先檢查邊界框是否與瓦片重疊。如果他們這樣做，你檢查多邊形是否與瓦片重疊。

在搜索時，這樣做：

1. 確定您所在的瓦這是一個快速的操作。
2. 現在你有潛在的多邊形列表。
3. 對於每個多邊形，檢查點是否在邊界框中。
   如果是，使用您提到的更昂貴的算法檢查點是否在多邊形中。

我已經使用了這個算法幾次，它非常快。通過改變分塊大小，你可以選擇內存佔用和性能之間取得平衡：

想到的極端情況：

• 覆蓋整個地圖的一個巨大的瓷磚：
  你會得到你的地圖中所有元素的一個列表，你必須檢查所有的邊界框。

• 非常小的瓷磚（每個國家只有一個多邊形的地圖只有1x1米）：
  您將獲得大量瓷磚。所有的多邊形將被分割成多個瓦片，每個瓦片將只有一個多邊形。但是，一旦你發現了哪個點（快），幾乎100％肯定只有一個多邊形需要檢查。

你需要在兩者之間的某個地方。如果您只需要這一段時間，則可能需要在性能上選擇較低的內存佔用量。最佳瓷磚尺寸也取決於多邊形尺寸的均勻性。所以，沒有自動的方法來計算最佳的瓷磚尺寸，你只需稍微調整一下，直到你找到正確的尺寸。