如何将“接近”的纬度/经度点分组？

Question

我有一个用户提交的纬度/经度点数据库，试图将“接近”的点组合在一起。这里的“接近”是相对的，但现在似乎约为500英尺。

起初，我的想法是可以按照具有相同纬度/经度前3个小数位（大约是300x300的盒子，但随着远离赤道而变化）的行进行分组。

然而，这种方法似乎缺乏很多，“接近”不能显著不同于每个小数位所代表的距离。它没有考虑到两个位置可能在第三个（或任何）小数位上具有不同的数字，但仍然在该位表示的距离内（33.1239和33.1240）。

我也思考了这样一种情况：点A和点C都与点B“接近”，但彼此之间并不接近-它们应该被分组吗？如果是这样，那么当点D“接近”点C（而没有其他点）时会发生什么-它也应该被分组吗？当然，我必须确定期望的行为，但如何实现其中任何一种方式呢？

能否有人指导我如何完成这项工作以及可以使用哪些不同的方法/方法？

我感觉自己好像漏掉了一些显而易见的东西。

目前，数据是一个MySQL数据库，由PHP应用程序使用；但是，如果它们是实现此目标的关键部分，我也可以接受其他存储方法。此处。

- Tim Lytle

---

也许这里有一些信息：http://en.wikipedia.org/wiki/Geodatabase - Stéphane

没有人能够为您指明正确的方向，除非您解释一下您的目标。为什么您想要对这些点进行分组？ - Unreason

@Unreason - 更详细地说，这些点表示用户'标记'特定位置，假设是如果多个用户标记了彼此靠近的位置，则应将其视为一个位置。然而，将经度/纬度点分组的目标是在 ~500英尺以内的点，似乎非常具体，并已经产生了有益的答案。 - Tim Lytle

@TimLytle，你能告诉我你最终是如何解决你的问题的吗？ - zeus

Answer 1

有许多方法可以确定两点之间的距离，但在绘制二维图上的点时，您可能想使用欧几里得距离。如果(x1，y1)表示第一个点，(x2，y2)表示第二个点，则它们之间的距离为：

d = sqrt( (x2-x1)^2 + (y2-y1)^2 )

关于分组，您可能希望使用某种二维平均值来确定物体之间的“接近程度”。例如，如果您有三个点，(x1，y1)，(x2,y2)，(x3，y3)，则可以通过简单取平均值来找到这三个点的中心：

x(mean) = (x1+x2+x3)/3
y(mean) = (y1+y2+y3)/3

您可以通过判断每个点到中心的距离来确定是否应该将其作为“簇”的一部分。

---

有许多方法可以定义聚类，这些方法都使用某种变体的聚类算法。我现在很匆忙，没有时间进行总结，但是请查看链接和算法，希望其他人能够提供更多详细信息。祝好运！

- eykanal

---

有想法如何使用更多的点来实现该分组方法吗？ - Tim Lytle

是的，我希望你不要问那个问题 :) 有许多非常复杂的聚类算法，我会更新帖子以反映其中一些。 - eykanal

距离只是故事的一部分。在以 (0,0) 为圆心、半径为 “distance” 的圆上可能存在无限数量的点，它们之间可能相距很远。您还应确定角度。当然，使用一些聚类算法可以真正解决这个问题。 - Michał Klimczak

Answer 2

使用与您在问题中概述的类似方法获取近似结果集，然后通过进行正确计算来缩小该近似集。如果您正确选择网格大小（即舍入坐标的程度），则至少可以希望将要完成的工作量减少到可接受的水平，尽管您必须管理该网格大小。

例如，PostgreSQL的earthdistance扩展通过将纬度/经度对转换为（x，y，z）笛卡尔坐标来工作，将地球建模为均匀球体。 PostgreSQL具有复杂的索引系统，允许将这些坐标或其周围的框索引到R树中，但是即使没有这样做，您也可以组合一些有用的东西。

如果您取出（x，y，z）三元组并舍去-即乘以某个因子并截断为整数-那么您就有了三个整数，可以将它们连接起来以生成“盒子名称”，该名称标识您“网格”中的一个点所在的框。

如果您想搜索距离某个目标点X公里内的所有点，则生成围绕该点的所有“盒子名称”（一旦您也将目标点转换为（x，y，z）三元组，那很容易），并消除不与地球表面相交的所有框（更麻烦，但使用每个角上的x ^ 2 + y ^ 2 + z ^ 2 = R ^ 2公式将告诉您），您最终得到一个列表，其中包含目标点可以在其中的框-因此只需搜索与这些框之一匹配的所有点，这也会返回一些额外的点。因此，作为最后阶段，您需要计算到目标点的实际距离并消除一些（再次，这可以通过在笛卡尔坐标系中工作并将目标大圆距离半径转换为割线距离来加快）。

微调涉及确保您不必搜索太多框，同时不要带入太多额外的点。我发现将每个点在几个不同的网格上进行索引很有用（例如1Km，5Km，25Km，125Km等分辨率）。理想情况下，您希望仅搜索一个框，记住一旦目标半径超过网格大小，它就会扩展至至少27个。

我使用了这种技术来使用Lucene构建空间索引，而不是在SQL数据库中进行计算。它确实有效，尽管设置它需要一些微调，并且索引需要一段时间生成并且相当大。使用R树来保存所有坐标是一种更好的方法，但需要更多的自定义编码-此技术基本上仅需要快速的哈希表查找（因此可能适用于当今流行的所有NoSQL数据库，并且应该可以在SQL数据库中使用）。

- araqnid

Answer 3

也许有些过度，但我认为这是一个聚类问题：距离度量将决定如何计算两个元素的相似度。如果您需要更成熟的解决方案，请尝试使用数据挖掘：实用机器学习工具和技术，并使用Weka或Orange。

- Roberto Russo

Answer 4

如果我要解决这个问题，我会从网格开始。将每个点放入网格的一个方格中。寻找人口密集的网格。如果相邻的网格没有人口密集，那么你就有了一个不错的组合。

如果你有相邻的人口密集的网格，你可以在每个网格的中心放置一个圆形，并优化圆形区域与（圆内的点数*一些可调节的权重）的比例。不是完美的方法，但很容易。更好的分组方案是更复杂的优化问题。

- patros

Answer 5

面临相似的问题时，我只是将经度和纬度 向下取整 直到获得所需的“接近度”（以米为单位）。在我的情况下，将它们取到小数点后4位可以将位置分组，当它们大约相隔13米时。

如果经度或纬度为负数 - 将floor替换为ceil

首先向下（或向上）取整到所需的精度，然后按四舍五入的经度和纬度进行分组。

测量两个地理位置之间距离的代码来自获取基于纬度/经度的两个点之间的距离.

from math import sin, cos, sqrt, atan2, radians

R = 6373.0
lat1 = radians(48.71953)
lon1 = radians(-73.72882)
lat2 = radians(48.719)
lon2 = radians(-73.728)
    
dlon = lon2 - lon1
dlat = lat2 - lat1

a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
c = 2 * atan2(sqrt(a), sqrt(1 - a))

distance = (R * c)*1000

print("Distance in meters:", round(distance))

距离为 84 米。

预期情况下，对于相同的角度，南部的距离较大，北部的距离较小。 对于相同的坐标，但在赤道上，距离为 109 米（将纬度修改为 0.71953 和 0.719）。

我修改了以下数字的位数，并始终在 Long 和 Lats 上单击一次，测量出的距离如下：

lat1 = radians(48.71953)
lon1 = radians(-73.72882)
lat2 = radians(48.71954)
lon2 = radians(-73.72883)
Distance in meters  1

lat1 = radians(48.7195)
lon1 = radians(-73.7288)
lat2 = radians(48.7196)
lon2 = radians(-73.7289)
Distance in meters  13

lat1 = radians(48.719)
lon1 = radians(-73.728)
lat2 = radians(48.720)
lon2 = radians(-73.729)
Distance in meters  133

lat1 = radians(48.71)
lon1 = radians(-73.72)
lat2 = radians(48.72)
lon2 = radians(-73.73)
Distance in meters  1333

摘要: 将经纬度保留4位小数并向上/向下取整，将有助于您对相距约13米的位置进行分组。 此数字取决于上述方程式：赤道附近较大，在北部较小。

- Toren

Answer 6

如果你考虑经纬度，实时数据需要考虑几个因素：障碍物，如河流和湖泊，以及设施，如桥梁和隧道。你不能简单地将它们分组；如果你使用k-means这样的简单算法，你将无法将它们分组。我认为你应该采用空间聚类方法，比如划分CLARANS方法。

- Deepak Upreti