2

我需要解决在地图上标记数千个项目的问题，即使用户缩小，标记也会以令人困惑的方式重叠。这是一个 Android MapView，但我的问题更笼统。

我知道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;

现在在每个簇的中心绘制一个标记。

我使用了可更新的 Delaunay 三角剖分和优先级队列来提高 (1) 的效率，但最近发现删除的 kd-trees也可以工作。DT 算法与 kd-trees（O(n log n) 平均值）具有相同的渐近复杂度，但我的猜测是它在实践中会更快。

问题：

  • 是否有更好的算法来查找集群？贪心算法可以产生比按最小数量分离标记严格需要的更少的集群。找到最大的集合可能是 NP 困难的。有比贪婪更好的启发式方法吗？
  • 是否值得尝试使用 kd-tree 代替 Delaunay 三角测量？DT 在 10,000 个节点上的性能在快速平板电脑上是微不足道的：缩放后最多 2 秒。
  • 是否存在将标记放置在集群质心的现有软件包？
4

0 回答 0