地圖有超過100萬點的標記，在發行高縮放級別

Question

語境：

谷歌地圖100萬個標記（對象與經/緯度）來顯示。我們使用Fluster 2進行聚類。

對於縮放級別11到21（假設有21個縮放級別，21是最接近地面的），聚類標記（創建聚類標記）的計算時間很好。

問題我遇到：

集聚聚類變焦11（當用戶從​​地面縮小）下來後正在緩慢。鑑於標記的數量大約爲1,000,000個，我需要一種快速計算方法或者一個週轉。

順便說一句，我對商業解決方案不感興趣。

Answer 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網格聚類的示例代碼博客中提到快速的技術。

有趣的問題:) 在由jon kleinberg提供的算法設計書中，提到了計算1.000.000個項目給O（n）約1秒，O（nlogn）約爲20秒。

如果不能保留O（n），那麼應該考慮一些技巧，只在計算中使用部分數據。

Answer 2

您可以使用空間索引並縮小尺寸。然後，您可以在每個縮放級別上分別拉出標記。我寫了一個帶有許多空間填充曲線的PHP腳本和一個用於學術目的的quadkey。我也有一些商業解決方案。

要開始，你可以閱讀：

• http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
• http://msdn.microsoft.com/en-us/library/bb259689.aspx。

當您需要更精確的搜索時，仍然可以使用它來消除所有位置的最近鄰居計算。