いうライブラリを使用しており、これがどういう仕組みで動いているのか気になったので調べてみました。使用してつくったサービスはこちら👇https://minsta.apphttps://photomap24.comクラスター化とはそもそもクラスター化とは何かというと、地図上の近い距離に複数のマーカー等が存在するときにグルーピングして表示することで、単純に見やすくなったり余計なマーカーの描画を防ぐというものです。大量のマーカーやピンを表示するようなアプリではほぼ必須の機能と言えると思います。同じような方法で実装されているようなので、この実装が現状のデファクトスタンダートになっているみたいです。クラスター化の仕組みクラスター化の仕組みについてですが、ライブラリ作者様のわかりやすい解説記事があったのでこちらの内容をベースに説明します。つのステップが実行されています。つのポイントにまとめて(クラスタリングして)いきます。この処理は最初にマーカーをロードしたタイミングで全てのズームレベルにおいて実行され、処理としては最も重い部分になります。目のステップでは、現在画面で表示されているエリアの座標とズームレベルに対応するクラスターを探索します。目のステップでズームレベルごとにクラスタリングされているデータの中から探索するだけですが、ユーザー操作に応じてリアルタイムに実行される部分なのでパフォーマンスが重要な部分でもあります。説明すると上の2つのステップだけで完結するのですが、これらの処理は以下で説明するような方法で効率的に実行されています。階層的な貪欲クラスタリング指定された半径以内に存在するポイントをクラスタリングしていくにあたって、単純に全てのズームレベルで全てのポイントを探索すると効率が悪いので、階層的な貪欲クラスタリングという方法で探索します。つのポイントとして見なしてクラスタリングを行うというものです。下図を見るとわかるように、ズームレベルを小さくしていくとクラスター化されたものをさらにクラスター化するような形になっていくので、探索しなければいけないポイント数が指数関数的に減少させられていることがわかると思います。階層的に実行することで計算量を減らせるとはいえ、必ずどこかのズームレベルでは各ポイントで近傍探索をする必要があり、これを大量のポイントで実行するのは直感的に重そうな処理だと感じると思います。いうデータ構造を使用して探索を高速化しています。軸方向で分割していき、木構造を構築することで二分探索的に処理できるという感じらしいです。よる近傍探索についての詳しい解説はこちらの記事などを参照ください。https://tecsingularity.com/algorithm/kdtree/自作してみたクラスタリングの仕組みがわかったところで、自分でも勉強がてら実装してみました。使用して各データはオブジェクトとして管理するようようにしました。威力を体感するため、今回はただの線形探索を使った実装にしました。本家と自作でそれぞれマーカーをロードしてクラスタリング処理が完了するまでの時間を計測してみました。以下の表はランダムな座標にマーカーを配置し、各マーカー数ごとにクラスタリングにかかった時間を測定した結果です。超えてくると一気に性能が劣化しているのがわかります。秒以内で終わるのを見るとアルゴリズムの偉大さを感じます。構築する分のオーバーヘッドが存在する影響だと思います。個以下など局所的なユースケースであれば自作ライブラリも使えなくはなさそうといった感じでしょうか。使用する場合と線形探索でパフォーマンスは変わるのですが、最初のクラスタリング処理ほど顕著な差は現れなかったので今回こちらは測定していません。いうライブラリを参考に地図上のマーカーをクラスター化する技術について調べてみました。実装自体は小さなライブラリですが、あらかじめクラスタリング処理しておくことによる高速な表示、階層的に処理していくことで計算量の削減、高速な近傍探索アルゴリズムの使用など、様々な工夫がされていてとても勉強になりました。実装やサーバ側でのクラスタリング実行など、まだ気になる要素がいくつかあるのでその辺りも今後調べてみたいと思っています。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。