3

我在sqlite中有这张表

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

例如，我有 100 条记录，我需要获取（使用我自己的坐标）表中最近的点。

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

谢谢

4

8 回答 8

6

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

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

应该减少很多你需要做的计算。

如果您希望始终在 X 距离内找到一个位置，您可以查询落在您的坐标 +/- x KM（正方形）范围内的 x/y 坐标，然后计算它们是否落在您所在点的 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 公里内得到结果，并且您希望您的数据库能够快速计算，您可以这样做：

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

现在，这会在一个正方形中为您提供所有结果。然后检查它们实际上是否在圆圈中很重要 - 您需要将任何东西放在角落中，因为实际上可能比圆圈边缘的坐标更接近。因此，对于每个点，首先检查它是否在圆内（用于测试点是否在圆内的方程式）然后计算距离并保持最近的距离。如果您没有得到结果，请扩大圈子。

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

于 2013-08-24T16:17:13.360 回答
4

您是否查看过如何计算地球上两点之间距离的网站？

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

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

希望这些信息对您有所帮助。

享受编码... :)

于 2013-08-28T10:01:44.797 回答
2

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

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

于 2013-09-02T16:29:09.260 回答
2

两点之间的距离：((x1 - x2) ^ 2 + (y1 - y2) ^ 2) ^ 0.5。但是，这些点之间的距离是直线。最有可能的是，存在诸如本地与高速公路之类的变量，更不用说单向街道和水道，您需要在其中找到最近的桥梁。因此，我建议使用 Google 和 Bing 地图 api。有限数量的搜索是免费的。

于 2013-08-24T17:32:21.957 回答
1

让我确保这是正确的：你有 point a，还有一个 points 表a[]。目前，您执行以下操作：

  • 循环b[]
    • 从到distance_b[i]a
    • 如果distance小于minimumDistance
      • 放minimumDistance = distance
      • 放closestPoint = i
  • 返回closestPoint

如果是这样，您会O(n)及时找到它，这实际上并没有太大的改进。您必须检查所有点以查看最接近的点。

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

于 2013-08-29T17:28:22.977 回答
1

取决于您在两极附近时对正确性的关心程度

如果最接近 pythagorean 距离足够好，您可以在 sql 的 orderby 中使用它

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

从技术上讲不是最正确的，但可以节省从数据库中获取所有位置并循环它们，让 sqlite 为你做这件事

于 2013-09-01T15:03:42.720 回答
1

你可以使用我的 php 类希尔伯特曲线@phpclasses.org。它使用怪物曲线和四键来找到最短距离。要搜索四键，您可以使用任何深度。

于 2013-09-01T23:53:58.147 回答
1

虽然这不是最好的选择。
让您试图找出N英里/公里半径范围内的最短距离（对于固定的位置数/您的位置表数据不会定期更改）。
添加另一列Distance_Index (DI)一个自多引用键 ArrayType。一旦运行一个程序并根据与该 DI 的距离以升序更新带有 ID 的 DI。现在从下一次开始，距离与您同在。只需对数据库进行查询并使用它。
样本表数据

现在，在您的问题中，N 内的位置没有更少，那么 DI 不会太长。只是作为一种意见。

于 2013-09-02T09:46:46.603 回答