算法 - 在地圖上對位置進行分組

我有一個n個位置的列表，每個位置都包含一個緯度，經度和一個時間戳。這些地點將被固定在地圖上。算法 - 在地圖上對位置進行分組

但是，需要將靠近在一起的位置進行分組，以最近更改的位置爲中心，以便地圖不會被引腳充斥。

我最初的想法是：

此方法可行，但效率非常低。最壞的情況是〜O（n^2）。

有什麼算法可以更好地執行嗎？

2017-09-17 MK Yung

https://blog.mapbox.com/clustering-millions-of-points-on-a-map-with-supercluster-272046ec5c97 –

要打敗二次運行時，請使用索引。

在經緯度上，您可能想要使用R樹，球樹，覆蓋樹或類似物，因爲kd樹顯然只適用於歐幾里得距離，而不是半島。

2017-09-17 13:51:51

[R - 樹是正確的關鍵字。我在這裏使用https://github.com/davidmoten/rtree實現，性能非常好。謝謝 –

但是最後我檢查了，它不可能Haversine距離很好。 ELKI版本可以。我認爲它使用這種方法：Schubert E.，Zimek A.，Kriegel HP。用於索引地理數據的R-樹上的大地距離查詢。 SSTD 2013。 –

我有一個hacky的解決方案，你可能會工作，如果你沒有問題的近似答案。

一般來說，緯度經度會出現幾個小數點後幾位小數點，如（12.9877949,77.6095064）。現在你只能選擇小數點後的幾位數字，一般在幾公里之內。

像12.9877979,77.6095054更接近12.9877949,77.6095064因此，如果我只取得2小數點，現在我會通過列表並選擇具有相同值的那些。

然而，這如果你需要非常精確的計算

將無法正常工作

2017-09-17 19:16:11

回答