2

環境:

表示する 100 万個のマーカー (緯度/経度を持つオブジェクト) を備えた Google マップ。クラスタリングには Fluster 2 を使用します。

ズーム レベル 11 から 21 の場合 (21 のズーム レベルがあり、21 が地面に最も近いと仮定)、マーカーのクラスター化 (クラスター マーカーの作成) の計算時間は問題ありません。

私が遭遇する問題:

ズーム 11 の後 (ユーザーが地面からズームアウトしたとき) に、凝集クラスタリングが遅くなります。約 1,000,000 のマーカーの数を考えると、高速な計算方法またはターンアラウンドのいずれかが必要です。

ところで、私は商用ソリューションには興味がありません。

4

2 に答える 2

1

Fluster 2は、クライアント側のクラスタリングであるjavascriptですよね?

数百万のポイントがある場合は、サーバー側のクラスタリングを使用するか、可能であれば事前にクラスター化前のポイントを使用することを検討する必要があります。

このトピックは、この https://stackoverflow.com/questions/986852/clustering-coordinates-on-server-sideに関連しています

その多くのポイントを使用して、単純なグリッドクラスタリングを作成できます。これは、グーグル http://code.google.com/intl/da-K/apis/maps/articles/toomanymarkers.html#gridbasedclusteringで言及されているように高速な手法です。

C# http://kunuk.wordpress.com/2011/09/15/clustering-grid-clusterのサンプルコードを使用して、グリッドクラスタリングに関するブログを作成しました 。

興味深い質問:)jonkleinbergによるアルゴリズムデザインの本には、1.000.000アイテムの計算で、O(n)に約1秒、O(nlogn)に20秒が与えられるという記述があります。

O(n)を維持できない場合は、計算でデータの一部のみを使用するようにいくつかのトリックを検討する必要があります。

于 2011-09-17T18:35:18.223 に答える
0

空間インデックスを使用して次元を減らすことができます。次に、各ズーム レベルで個別にマーカーを取得できます。アカデミックな目的で、多くのスペース充填曲線とクワッドキーを備えた PHP スクリプトを作成しました。私はまた、いくつかの商用ソリューションを持っています。

開始するには、次を読むことができます。

より正確な検索が必要な場合でも、それを使用して、すべての場所で最近傍計算を排除できます。

于 2012-11-13T08:32:45.647 に答える