语境：
带有 100 万个标记（带有纬度/经度的对象）的谷歌地图要显示。我们使用 Fluster 2 进行聚类。
对于缩放级别 11 到 21（假设有 21 个缩放级别，并且 21 是最接近地面的），聚类标记（创建聚类标记）的计算时间很好。
我遇到的问题：
缩放 11 后（当用户从地面缩小时），聚集聚类正在减慢。考虑到标记的数量，大约 1,000,000，我需要快速计算方法或周转。
顺便说一句，我对商业解决方案不感兴趣。
问问题
1927 次
2 回答
1
Fluster 2 是一个 javascript，它是客户端集群，对吗？
拥有数百万个点，如果可能，您应该考虑绝对使用服务器端集群，甚至提前使用集群前点。
本主题与此 https://stackoverflow.com/questions/986852/clustering-coordinates-on-server-side有关
有了这么多点，您可以进行简单的网格聚类。这是 google 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 个项目大约需要 1 秒 O(n) 和 20 秒 O(nlogn)。
如果不能保持 O(n)，则应考虑一些技巧，仅在计算中使用部分数据。
于 2011-09-17T18:35:18.223 回答
0
您可以使用空间索引并减少维度。然后，您可以在每个缩放级别上分别拉标记。我为学术目的编写了一个包含许多空间填充曲线和四键的 PHP 脚本。我也有一些商业解决方案。
首先，您可以阅读：
- 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。
当您需要更准确的搜索时，您仍然可以使用它来消除所有位置的最近邻计算。
于 2012-11-13T08:32:45.647 回答