从一个点获得最短距离

Question

我在sqlite中有这个表

Locations
ID
Lat ( latitude)
Lon ( longitude) 
Type
Name
City

我有100个记录,我需要得到(使用我自己的坐标)我表中最近的点.

我所做的是获得当前点与表中每个点之间的最短距离,并返回最短点,但我正在寻找更好的解决方案

谢谢

Answer 1

一种可能的解决方案是为您感兴趣的整个地图使用网格,并将点预分配给特定的行/列.然后:

1. 计算新点的网格位置 - 为此向数据库添加一列.
2. 计算当前网格中所有坐标的距离 - 如果存在的话
3. 您仍然需要计算下一个网格中的所有距离(您不太可能完全居中于当前的方格,您总是需要检查距离最佳匹配的网格距离.)

应该减少你需要做的计算次数.

如果您希望始终在X距离内找到一个位置,您可以查询x/y坐标,这些坐标将在您的坐标范围内+/- x KM(一个正方形),计算它们是否落在您的点的xKM圆圈内,然后选择最短的.

更新 - 网格选项

我假设你已经在两点计算之间做距离,并且不会描述.

如果您有方便的地图集,您可以通过在索引中查找位置来查看示例.它将为您提供一个页面和网格位置,如M5.如果你去那个页面,它会有用数字和字母标记的行和列,如果你看到第M行和第5列相交的方块,你会在那里找到那个城市.要为您的系统执行此操作,您需要:

1. 确定你的网格应该有多大(你的点有多密集 - 拥有一个大网格并且你的所有点落在一个方格中都没有用).
2. 对于每个点,计算它所在的网格.如果您的多边形很复杂,那么多边形代码中有大量的点要复制.如果(就我的例子而言)你只是使用正方形,你只需要确定每个点之间的哪一行/列.
3. 有关用户位置和最近点的示例,请参见地图:

因此,如果用户是绿色标记,他将在C4中.您将搜索C4中的所有其他点并确定最接近的是#2.然后你还必须检查一个网格,以确保没有比你找到的更近的项目,所以这包括正方形:B3,B4,B5,C3,C5,D3,D4,D5 .当你这样做时,你将从C3中选择#3并完成.

如果用户在方形D2中没有其他点,那么你会在C2中找到你的第一场比赛.检查C1,C2,C3,D1,D3,E1,E2,E3时.一旦找到,你将再次需要检查另一个半径,这将是:B0-4,C0,C4,D0,D4,E0,E4,F0-4.您可以看到网格选择对于尽可能提高效率非常重要.

另请注意,假设您的网格与我的手绘示例不同.

选项2:

如果您希望X km内的结果,并且您希望数据库快速计算出来,您可以执行以下操作:

LatMin = currentLatCoord-radiusValInDegrees
LatMax = currentLatCoord+radiusValInDegrees
LonMin = currentLonCoord-radiusValInDegrees
LonMax = currentLonCoord+radiusValInDegrees

SELECT * 
From Locations 
WHERE Lat BETWEEN LatMin AND LatMax
  AND Lon BETWEEN LonMin AND LonMax

现在,这将为您提供正方形的所有结果.重要的是,然后检查它们实际上是在圆圈中 - 您需要在角落中放下任何角落,因为实际上可能存在比圆形边缘更近的坐标.因此,对于每个点,检查它是否首先在圆内(测试点是否在圆内)的方程式,然后计算距离并保持最接近的距离.如果没有得到结果,请加宽圆圈.

同样,选择良好的半径取决于您的数据.