地理空间路由

Question

我是一名物流程序员，被要求确定一个GPS点是否“偏离路线”，其中路线由多个地理空间点（纬度、经度）组成。

什么是最佳算法来确定一个点是否靠近路线？我将使用C#和SQL Server，但如果我知道要使用什么算法，这并不重要。

我已经考虑过：

1. 找到两个最近的点，并确定三角形的面积是否超过特定限制。
2. 使用所有点对的向量，然后检查它们中的任何一个是否与由GPS点和我确定为“下一个”路线点定义的向量相似。

我没有数学学位，但如果给出正确的术语和搜索引擎，我可能可以处理任何事情。

我将不得不每小时进行至少4000次计算，因此由于数据量的原因，使用映射解决方案可能不可接受。

- Doug Heeren

---

你所提出的问题很有趣。那个三角形面积的解决方案不可行，因为两个非常远的点会生成一个表面积很大的三角形，即使该点只稍微偏离路线。我不确定是否有更好的解决方案。感谢你给了我思考的东西。 - Brian Willis

你正在使用哪个版本的SQL Server？除了纬度/经度之外，你是否有关于公交车位置的其他属性？例如公交车ID、路线ID等，这些信息是否可以与正确的道路/路线相关联？ - RyanKDalton

@RyanDalton 2005年，很遗憾。据我所知，2012年在空间数据方面有一些非常好的功能。我不排斥使用Mongo或其他数据库，但这将需要更多的工作来设置和维护另一个具有实时信息的数据库。 - Doug Heeren

@BrianWillis 是的，这就是我提出问题的原因。我想到那不会起作用。找到GPS点与涉及线路之间的距离也不行。 - Doug Heeren

Answer 1

我每小时需要进行至少4000次计算，因此使用映射解决方案可能不可行。

实际上，这是一个完美的例子，可以受益于映射解决方案。不是传统的“查看地图并确定距离”，而是“让数据库确定最接近您GPS点的路线”。

既然您说不反对使用不同的数据库，您可以考虑：

1. 具有Spatial Database Engine函数的SQL Server 2008，或者
2. 带有开源PostGIS（空间）扩展的PostgreSQL，它具有比MS SQL 2008更多的空间分析功能。

请看PostGIS ST_Distance函数或MS SQL Server 2008 STDistance函数。这是一篇很好的博客文章, 描述了SQL2005与SQL2008的优势。

您还可以考虑阅读（或询问更详细的地图制作）gis.stackexchange上的帖子。整个小组致力于空间分析。您可以看看一些好的讨论。

• 查找最接近输入经纬度的经纬度（SQL Server 2008）
• PostGIS：给定点到线串上最近点的距离

- RyanKDalton

---

谢谢。我有一个朋友向我推荐了gis.stackexchange。速度是我使用地图方案的担忧。我每小时至少需要处理4000个。但你说得对，这可能是最准确的解决方案。 - Doug Heeren

Answer 2

请谷歌搜索“Along-track distance”，您将找到在航空业中常用的公式。或者，cross-track distance也可能是您想要的内容。

- Has QUIT--Anony-Mousse

---

谢谢，这看起来就是我在寻找的答案。 - Doug Heeren

Answer 3

以下内容怎么样...

遍历所有线段 lineSegSlope = 计算每个线段的斜率

从问题点绘制一个假线段，与当前线段相交。这是通过反转lineSegSlope并乘以-1来获得新斜率，然后将目标点X、Y和新斜率替换为y-y1 = b * (x-x1)完成的。您的X输入x1，您的Y输入Y1，您的newSlope输入B。

为线段制定方程式。

如果你把两条线放在一起画，它们应该形成一个X，每个角都是90度。

计算两条线的交点

计算交点与您的新点之间的距离。如果它大于某个可容忍的值，则新点太远了。

这看起来很混乱，但希望它能行。

- mj_

---

当我推理时，路线上的点与问题点之间的角度是导致这个问题的原因。如果线段远离点，但路线上两点的角度使得线段在延长后非常接近该点，则会产生一个错误的答案。不过，我对此还有些困惑，所以我的回答可能是错误的。 - Doug Heeren

我明白你的意思，发现得不错。但在这种情况下，线段的实际端点将是最接近的点。然后，您可以计算目标点到线段端点的距离。你遇到了一个有趣的小问题。 - mj_

Answer 4

你能将现有的路径作为二维线段序列，然后取出查询点并找到最近的点和最近的线段吗？ 该最近点/线段的距离即为所关心的距离。

如果你只涉及相对较低的纬度（在60度以下），你或许可以将纬度和经度看作平面坐标系，如同墨卡托投影。

否则，你可以将坐标系转换成相对于穿过部分路径点的大圆运行时的坐标系。

除非你要处理数百万个路径点，否则不应该会CPU时间问题。

- Mike Dunlavey

---

这是我考虑过的公式之一，但我发现根据路线的形状，有些情况下它不起作用。大多数路线都不是直线，有些甚至会折返。当时间涉及到时，情况变得更加复杂，但我将其留到另一个问题中。 - Doug Heeren

Answer 5

一种朴素的方法是将新的 GPS 点插入到路径的各个位置。从在第一个点 P0 之前插入它开始，然后在第一个和第二个点 P0 和 P1 之间插入它，如此等等，直到尝试将其插入为最后一个点。每次尝试在位置处插入它时，计算电路的总距离并保存最短的总距离。这可以通过预先计算腿距离并存储该总和来加快速度。通过减去您将要插入新点的腿距离，并将新距离从点 P(n) 到您的 GPS 点添加到 P(n+1) 中，检查距离。如果最短总距离在您的容差水平内，则可以接受。

这可能不是“最佳”算法（取决于您对最佳的定义），但它对于路径中的点数的时间和空间复杂度都是 O(n)。因此，除非您的路线中有大量点，否则每次检查应该少于一秒钟，因此这应该符合您的时间要求。

此外，请确保在计算路径上相邻点之间的距离时使用haversine distance equations。

- andand

---

对我来说，最好的是在很大一部分情况下快速而准确。当路径中两点之间的距离更大时，这种情况下的容差水平需要增加，不是吗？ - Doug Heeren