4

给定一组地理位置（以纬度/经度的形式），我将如何找到最受欢迎的位置？

例如，我编译了一张包含各种点的地图：

地图链接

我们可以看到，除了 1、4、6 和 9 之外，所有点都集中在大约一个位置。我如何计算该组的平均位置？理想情况下，随着地图的人口越来越多，我想计算第二个最受欢迎的位置，第三个最受欢迎的位置等。

我怎么能解决这个问题？

提前致谢。

4

2 回答 2

5

如果您需要一个简单的解决方案，它会给您一个很好的估计并且易于编码......

  • 选择您认为位置大小的半径（我们会说 100m）
  • 遍历您的位置，使它们成为您圈子的中心
  • 使用 Point-in-Circle 计算圆内有多少其他点
  • 在它的圆圈内拥有最多点的位置成为您最受欢迎的位置，现在从您的集合中删除所有这些点并重复第 2 至第 n 最受欢迎。

如何将距离转换为纬度和经度？将经度纬度转换为米

例如，1 度的纬度在 110574 和 111693 米之间。

于 2013-01-28T20:42:10.907 回答
2

DBSCAN 算法可能是您正在寻找的。

它是一种根据密度找到点簇的算法。由于在您的情况下，流行意味着密集，您可以使用它来解决此任务。它需要两个参数：

  • eps，每个点周围的半径，在该半径内寻找其他点以形成集群，
  • minPts，一个点周围半径内所需的点数，以将节点组视为一个集群。

您还需要一个函数来测量点之间的距离。由于您有（纬度，经度）对（通常为WGS84 格式），因此您需要Haversize 距离。

该算法有多种实现方式。如果您使用的是Java，Apache Commons Math提供了一个不错的实现（有关更多详细信息和一些代码片段，请参见此处）。调用eps = 1.0（半径为 1 公里）和DBSCANClustererminPts = 0 （集群有 1 个或更多点）。请参阅此答案以实现Haversine 距离（确保与eps使用的相同测量单位匹配）。最后通过减小大小对集群进行排序，使其按“受欢迎程度”排序：

Collections.sort(clusters, (o1, o2) -> 
    Integer.compare(o2.getSize(), o1.getSize());
Cluster<? extends Clusterable> mostPopular = clusters.get(0);

如果我没记错的话，这个实现解决了关于它的大小（点数）的二次时间问题。如果您将面临的问题的所有实例都与您的示例具有相同的大小，那么您将没有问题。

于 2015-12-04T16:12:28.167 回答