私はn個の場所のリストを持ち、それぞれが緯度、経度、タイムスタンプで構成されています。これらの場所は地図上に固定されます。アルゴリズム - マップ上の場所のグループ化
ただし、マップがピンによってフラッディングされないように、最近接に変更された位置を中心にしてグループ化する必要があります。
私の最初の考えは次のようになります。タイムスタンプ
この方法は機能しますが、非常に非効率的です。最悪の場合は〜O（n^2）です。
パフォーマンスが向上するアルゴリズムはありますか？
2次ランタイムに勝つには、インデックスを使用します。
緯度と経度では、k樹木は明らかにhaversineではなくユークリッド距離でしか動作しないので、Rツリー、ボールツリー、カバーツリーなどを使用することができます。
Rが必要な場合は
しかし、これは動作しません。 -Treeは正しいキーワードです。私はhttps://github.com/davidmoten/rtreeの実装を使用しており、パフォーマンスは抜群です。ありがとう –
しかし最後に私はチェックした、それは非常にHaversineの距離を行うことができませんでした。 ELKIのバージョンは可能です。私はそれがこのアプローチを使用すると思う：Schubert E.、Zimek A.、Kriegel HP。地理的データを索引付けするためのR木に関する測地距離問合せ2013年のSSTD。 –
おおよその答えで大丈夫であれば、うまくいくかもしれないハッキーな解決策があります。
一般に、緯度経度は、（12.9877949,77.6095064）のようにいくつかの小数点を超えていくつかになります。これで、小数点以下の桁数を選択することができ、通常は数キロメートル以内に収まります。
12.9877979,77.6095054のようなものは12.9877949,77.6095064に近いので、小数点以下2桁までとすると、両方とも12.98,77.60になります。今度はリストを通って同じ値のものを選びます。あなたは非常に正確な計算
https://blog.mapbox.com/clustering-millions-of-points-on-a-map-with-supercluster-272046ec5c97 –