マーカーが紛らわしい方法で重なり合うように、ユーザーがズームアウトした場合でも、正確で読みやすく、高速な方法でマップ上の何千ものアイテムをマークする問題を解決する必要があります。それは AndroidMapViewですが、私の質問はより一般的です。
Fluster、グリッドベースのスキーム、およびさまざまなヒューリスティック を認識しています。
これらのアルゴリズムは、クラスター マーカーが重心に対応していないという点で不正確であるように見えます。私のアプリケーションは安全性が重要であり、マーカーがかなり大きいため、近似では十分ではありません。
アルゴリズムを発明した後、それが最初に使用されたのは 80 年代であることがわかりました。その適切な説明は、「凝集型の階層的な幾何学的重心クラスタリング」です。 疑似コードは次のとおりです。
-- Greedy hierarchical clustering
given R the clearance radius of markers
let S be a set, initially singleton clusters containing exactly one marker each
loop
let <a,b> be the pair of clusters in S with closest centroids, distance d apart; (1)
if d >= 2R, exit the loop;
remove a and b from S;
insert new Cluster(a union b) into S;
end loop;
ここで、各クラスターの重心に 1 つのマーカーを描画します。
(1) を効率的にするために、更新可能な Delaunay 三角形分割と優先キューを使用しましたが、最近、削除を伴う kd ツリーも機能することがわかりました。DT アルゴリズムは、kd ツリーと同じ漸近的な複雑さ (O(n log n) 平均) ですが、実際にはより高速になると思います。
質問：
- クラスターを見つけるためのより良いアルゴリズムはありますか? 貪欲なアルゴリズムでは、最小量でマーカーを分離するために厳密に必要なクラスターよりも少ないクラスターが生成される可能性があります。最大のセットを見つけることは、おそらく NP 困難です。貪欲よりも優れたヒューリスティックはありますか?
- Delaunay 三角形分割の代わりに kd-tree を試す価値はありますか? 10,000 ノードでの DT のパフォーマンスは、高速タブレットではわずかです。ズーム後最大 2 秒です。
- クラスター重心にマーカーを配置する既存のパッケージはありますか?