哪個空間數據結構（算法）最適合（搜索）一組區域（空間數據）？

Question

我有一組區域（地理柵欄）是多邊形。這組數據是固定的;所以不需要插入和刪除數據。哪個數據結構可用於搜索查詢點（經度，緯度）所在的區域？

注意：我已經成功實現了KD-Tree（實際上是一個2D-Tree）的一組點。但它不適用於這個問題。然後我實現了一棵R樹;它解決了這個問題，但速度很慢（或者我的實現很糟糕）。

謝謝

注：我已經在R-樹的實施工作，現在工作得很好。

Answer 1

A R-Tree數據結構可以用於這個問題。

Answer 2

由於您沒有插入/刪除並且可能有足夠的時間來預處理數據，因此您可以使用一些額外的內存來加速計算。預處理的基本思路：

1. 取所有的多邊形點並確定最小的軸對齊的包圍它們的邊界矩形;基本上這是X和Y的最小值和最大值。
2. 選擇您將用於創建搜索網格的分配因子dX和dY。選擇分配因子的兩個冪可以稍後加快計算速度。
3. 翻譯多邊形數據，使它們的邊界矩形最小值與（0,0）重合並展開矩形，使其成爲每個維度中分區因子的整數倍。
4. 考慮每個網格正方形並製作與正方形相交的多邊形列表。存儲這個列表爲每個網格廣場。根據數據的性質（有多少多邊形可以期望與正方形相交），可以通過多種方法優化存儲空間或速度。

現在，當你想查找包含點的區域：

1. 使用我們前面定義的原點轉換點，並確定包含點的方格（如果你使用兩種動力，這是一個移位操作;否則就是劃分。）
2. 看看網格正方形的列表。如果它是空的，則不存在包含多邊形。如果不是，則必須考慮列表中的每個多邊形並搜索相交。

這適用於展開和大多數不相交的多邊形，特別是如果您可以選擇足夠細的網格以便每平方只有幾個多邊形。如果您碰到有許多相交多邊形的正方形，則速度會很慢。一個額外的優化是爲每個列出的多邊形在正方形上標記一個標記，以指示該正方形完全包含在該多邊形內;這樣可以避免在很多情況下進行慢速遏制測試，但每個多邊形條目只需一位。如果您的網格間距與多邊形尺寸相比很好，這是非常有價值的，因爲大多數平方不會位於交點或邊緣。

如果您需要更高的速度，您可以使用多邊形參考在每個正方形上開始存儲邊緣信息。您只需測試實際與正方形區域相交的多邊形邊緣。這可以減少每個多邊形只進行少量邊緣測試的工作量。