1

我有一个地理编码条目数据库。我需要确定哪两个条目与总条目的子集相距最远。例如，我选择一个包含 10 个条目的列表，然后从该列表中确定哪两个位置代表该列表中的最大距离。

我无法解决如何解决这个问题。我什至考虑过使用弧度，但似乎没有什么能满足要求。

仅供参考，LAMP 堆栈在这里...

4

4 回答 4

2

以下查询将计算所有点之间的距离并返回距离最大的两个点：

SELECT coor1.longitude as lon1,
       coor1.latitude as lat1,
       coor2.longitude as lon2,
       coor2.latitude as lat2,
       (ACOS(
         COS(RADIANS(coor1.latitude))  * 
         COS(RADIANS(coor1.longitude)) *
         COS(RADIANS(coor2.latitude))  *
         COS(RADIANS(coor2.longitude)) + 
         COS(RADIANS(coor1.latitude))  *
         SIN(RADIANS(coor1.longitude)) *
         COS(RADIANS(coor2.latitude))  *
         SIN(RADIANS(coor2.longitude)) +
         SIN(RADIANS(coor1.latitude))  * 
         SIN(RADIANS(coor2.latitude))
         ) * 6378                        --- Use 3963.1 for miles
       ) 
AS DistanceKM
FROM coordinates coor1,
     coordinates coor2
WHERE NOT (coor1.longitude = coor2.longitude AND coor1.latitude = coor2.latitude)
ORDER BY DistanceKM DESC
LIMIT 1;                                 --- Only the biggest

现在我建议事先进行这些计算并将结果存储在单独的表中。

于 2009-08-15T22:38:10.340 回答
2

从表面上看，这可以通过首先找到点的凸包来解决（例如，使用Graham 的 scan），然后在其上旋转卡尺的直径。

于 2009-08-15T22:39:38.747 回答
1

蛮力方法：

  1. 通过平均纬度和经度值找到十个列表的中心。

  2. 对于数据库中的每个（纬度，经度）对，使用大圆公式计算从步骤（1）到中心的距离

  3. 选择最大的两个距离。

明显的优化：将世界分成N个“正方形”（例如，经度10度，纬度10度）并预先计算每个配对中心之间的大圆距离。将其存储在数据库中。现在，您可以快速查找最远的“正方形”，并且只检查这些图块内的（纬度、经度）对。

于 2009-08-15T22:30:25.737 回答
0

这是在 PHP 中实现的基于纬度和经度的两点之间距离的算法。

请注意，如果“总条目的子集”很大，您很快就会有很多计算要做。如果是这种情况，您可能需要考虑预先计算城市对之间的距离。

编辑：为什么 10 度优化不起作用：

取四个正方形如下图

-------------------
|        |        |
|   A    |   B    |
|        |        |
|_______1|________|
|        |2       |
|   C    |   D    |
|        |        |
|_______3|________|

通过仅测量正方形的中心并比较这些距离，您会得到 A 和 D 比 A 和 C 相距更远。但是，城市 1 和 3 显然比 1 和 2 相距更远。

于 2009-08-15T22:36:40.233 回答