获取从一个点到一条线段的最短距离

Question

我有一个SQLite表：

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

我举个例子，我有100条记录，我需要使用我的坐标在表格中找到最近的点。

我的方法是计算当前点与表格中每个点之间的距离，然后返回距离最短的那个点，但我正在寻找更好的解决方案。

谢谢。

- Peril

---

更新了我的回答。如果您不想失去任何辛苦赚来的声誉，我很乐意提供更多细节 - 只需问就行 :) - Matthew

Answer 1

一种可能的解决方案是使用网格来处理整个地图，并将点预先分配到特定的行/列。然后：

1. 计算您新点的网格位置 - 为此添加一个数据库列。
2. 计算当前网格中所有坐标的距离 - 如果存在一个网格
3. 您仍需要计算下一个网格中的所有距离（您不太可能完全位于当前正方形中心，因此始终需要检查从最佳匹配所在的网格外一格的距离。）

应该可以大大减少您需要执行的计算次数。

如果您希望总是在X距离内找到位置，则可以查询在该范围内落入您坐标+/- x公里的x/y坐标（一个正方形），计算它们是否在x公里圆圈内，然后选择最短的。

更新-网格选项

我假设您已经进行了两点之间距离的计算并且不会描述它。

如果您手边有一本地图册，您可以通过在索引中查找某个地方来看一个示例。它将为您提供一个页面和一个网格位置，例如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公里范围内获得结果，并且希望您的数据库能够快速计算，您可以执行以下操作：

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

现在这样做可以给你一个放在正方形中的所有结果。重要的是，你需要检查它们是否实际上在圆内——你需要舍弃任何在角落里的点，因为可能比边缘上的坐标更接近。因此，对于每个点，请先检查它是否在圆内（测试一个点是否在圆内的公式），然后计算距离并保留最近的那个。如果没有得到结果，请扩大圆的半径。

同样地，选择好的半径将取决于您的数据。

- Matthew

---

“最近点对”算法在已知一个点的情况下并不实用。此外，他目前使用的是O(n)的解决方案，因此建议使用O(nlogn)的解决方案有些奇怪。除此之外，其余部分都是正确的，但开头有些误导性。 - Geobits

@Geobits 谢谢 - 实际上我认为当我重新阅读他的问题并在第一次回答中扩展问题时，我已经删除了那部分。现在已经删除了。 - Matthew

这很有道理。它看起来确实是临时加上去的，就像两个完全不同的答案。给你点赞，先生。 - Geobits

@Geobits 如果你在这个地区，我会带你去钓鱼 @ B7 - 很棒的地方 :) - Matthew

Answer 2

你看过这个网站，关于如何计算两点之间的距离吗？

但要记住它仅基于地球表面给出距离，而不是基于实际到达该位置的路径。因此，如果您想根据实际路径计算距离，则可以使用Google MAP API。

Google Maps API根据实际路径给出两点之间的距离。

希望这些信息肯定能帮助到您。

享受编程...:)

- Shreyash Mahajan

---

感谢@Peril接受答案。很乐意帮助您。如果您还有其他问题，请告诉我。 - Shreyash Mahajan

Answer 3

两点之间的距离: ((x1 - x2) ^ 2 + (y1 - y2) ^ 2) ^ 0.5。然而，这些点之间的距离是直线距离。很可能会有像当地道路与高速公路这样的变量，更不用说单行道和水路，需要找到最近的桥梁。因此，我建议使用Google和Bing地图api。它们免费提供有限数量的搜索。

- Robert Co

---

我正在使用离线的osmdroid地图，所以无法使用Google API，但我的点数非常有限，最多只能搜索到200个点。 - Peril

+1 如果使用方向 API。在现实场景中，直线距离并不太有意义。 - Frank

Answer 4

在SQLite中基于半径获取记录的查询中有一个相当聪明的解决方案，它是基于在插入行时预计算每个位置的一些三角函数值，然后可以仅使用算术函数在查询中计算距离。

我已经在自己的代码中非常成功地使用了它。

- Liminal

Answer 5

取决于你在靠近极地时对正确性的关注程度

如果最接近的勾股距离足够好，你可以在sql的orderby中使用这个

例如：SELECT * FROM locations ORDERBY (Lat-myLat)*(Lat-myLat) + (Lon-myLon)*(Lon-myLon) LIMIT 1

虽然不是技术上最正确的方法，但节省了从数据库获取所有位置并循环遍历它们的步骤，让sqlite代替你完成这些操作

- Tristan Burnside

Answer 6

你可以使用我的PHP类Hilbert Curve @ phpclasses.org。它使用一个monster curve和quadkey来找到最短距离。要搜索quadkey，您可以使用任何深度。

- Micromega

Answer 7

尽管这不是最佳选择。
假设你正在尝试查找固定数量的位置/位置表数据的 N 英里/公里半径内的最短距离，而这些数据并不经常更改。
添加另一个名为 Distance_Index（DI）的列，它是自引用键ArrayType。运行一次过程，并根据与此DI的距离按升序更新ID。现在，从下一次开始，距离就在您身边了。只需向数据库发出查询并使用它即可。

现在，在您的问题中，如果位置数在N之内，则DI不会太长。仅作为意见。

- Pradip

Answer 8

让我确认一下：您有一个点a，和一个点表a[]。目前，您做的事情是这样的：

循环b[] - 从b[i]到a获取distance - 如果distance小于minimumDistance - 设置minimumDistance = distance - 设置closestPoint = i 返回closestPoint 如果是这样，您正在以O(n)时间找到它，这不能真正得到改进。您必须检查所有点以查看哪些是最接近的。

然而，正如Matthew指出的那样，您可以通过将点分配到网格来减少n的数量。这可以大大减少需要比较的点数。代价是一些预处理时间和稍微复杂的逻辑。如果您有一个长点列表（或distance()函数需要很长时间），您肯定会想要做这样的事情。

- Geobits