WGS84座標中的聚類或過濾點

Question

所以我試圖解決一個問題。我有一個可以成爲球員的觀點，我周圍有幾個對象，有些更接近呃。例如，我想排除所有更遠的點，並使用距離包括更近的點。如何羣集或過濾對象。我正在考慮空間分區。這些對象位於地理座標中。對象的數量可以是10.000

Answer 1

如果允許每個單點移動，更新對於kd樹或類似的自適應結構可能會變得昂貴。我想我會採用靜態分區方法，例如將空間劃分爲一組單元格（二次或矩形），並且每個單元格存儲對所包含點的引用，以及所包含點集合的最大和最小座標。當點移動時，可以簡單地計算它們所在的當前單元格。在計算距離時，只需確定相關單元格，然後使用線性時間計算與其包含的點的距離。

我看到三個基本優點這種方法：

1. 通過查看當前包含的最小和最大座標每個單元可以很容易地確定是否其空，如果沒有，整套包含點數與玩家當前位置有關。

2. 您可以用完美的平衡組織樹形結構（例如四叉樹）中的靜態單元。對於樹的每個內部節點，您存儲並更新其子節點的最小和最大座標。請注意，更新非常便宜，因爲樹的結構完全不受影響。

3. 您不需要對點進行排序（因爲這對於其他結構或特定實現是必需的）。如果物體快速移動，這可以爲您節省很多性能。

4. 構建和維護數據結構很簡單。您不必用異乎尋常的測試案例和複雜的結構更新破壞您的大腦。

當然，選擇非自適應數據結構有一些缺點，因爲它是非適應性的。例如，你高度依賴於網格單元的大小。如果你選擇它太小（最壞的情況：每個單元一個點），樹的深度會增大，而且遍歷變得很昂貴。另一方面，如果你選擇它太大（最糟糕的情況：在某個點上，所有的點都在同一個單元格中），你將執行許多不必要的和可能很昂貴的距離計算。

總而言之，這取決於您擁有的數據類型。我給你的建議應該給出相當好的結果，但可能有更有效的方法來做到這一點。如果你有足夠的時間，同時實施自適應和靜態分區方法，可以提出一些有代表性的測試並將它們相互比較。

希望這有助於;）