地理空间路由

我是一名物流程序员，并且我被要求弄清楚GPS点是否是“非路线”，其中路线由若干地理空间点（纬度，经度）组成。地理空间路由

确定点是否在路线附近的最佳算法是什么？我将使用C＃和SQL Server，但是如果我知道使用什么算法，这真的不重要。

我认为

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

我没有数学学位，但是我可以处理任何给定正确条件和搜索引擎的东西。

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

来源

2012-01-18 Doug Heeren

什么你问是一个有趣的问题。三角形的表面积解决方案不起作用，因为两个相距很远的点会产生一个具有大表面面积的三角形，即使该点只是略微偏离路线。不知道我有更好的解决方案。谢谢你给我一些想法。 –

您使用的是哪个版本的SQL Server？你有关于巴士位置除lat/long以外的属性吗？公交车ID，路线ID等可以绑定到正确的道路上吗？ – RyanDalton

@RyanDalton 2005不幸的。据我所知，2012年有关于空间数据的一些相当不错的功能。我并没有使用mongo或其他数据库，但最终还是需要更多的工作来设置和维护具有实时信息的另一个数据库。 –

谷歌对于“Along-track distance”，你应该找到航空中常用的公式。或者，cross-track distance也可以是你想要的。

来源

2012-01-18 21:57:17

谢谢，这看起来是我正在寻找的答案。 –

您可以将现有路线作为二维线段的序列，然后带上您的查询点并找到最近的点和最近的线段？到最近点/线段的距离将是您关心的距离。

如果您坚持相对较低的纬度（低于60度），您可能会将经度和纬度视为简单平坦，就像墨卡托投影一样。

如果不是，则可以将坐标系转换为相对于穿过某些路线点的大圆的坐标系。

除非您处理数百万个路线点，否则CPU时间不应该有问题。

来源

2012-01-18 22:08:43

这是我考虑过的公式之一，但是我发现它根据路线的形状而不起作用。他们中的大多数人不在一条直线附近，其中一些人自我折腾。如果涉及时间，情况会变得更加复杂，但我保存了另一个问题。 –

如何通过所有线段以下...

迭代

lineSegSlope =斜率计算为每个线段

绘制从所讨论相交当前行中的点假装线分割。这是通过倒置lineSegSlope并乘以-1得到新斜率，然后将目标点X，Y和新斜率替换为y-y1 = b *（x-x1）来完成的。您的X进入x1，您的Y进入Y1，并且您的newSlope进入B.

为线段建立方程。

如果你画两条线在彼此的顶部，他们应该做一个X，其中每个角落是90度。

计算两行

的交点计算交点和新的点之间的距离。如果它大于某个可接受的值，那么这个新点太过分了。

这看起来像一团糟，但希望它能工作。

来源

2012-01-18 22:26:17

路线上的点与所讨论的点之间的角度是当我推理出来时抛弃这个点的角度。如果线段距离该点较远，但路线两点的角度使得该线非常靠近延伸点，则会产生不正确的答案。我很努力地理解这一点，所以我可能会对此有错误的回应。 –

我明白你在说什么，很好。不过，我认为在这种情况下，线段的实际结束将是最接近的点。然后可以计算从目标点到线段末端的距离。有趣的小问题，你在这里。 –

一个天真的做法是在沿线的各个地方插入新的GPS点。首先在第一个点P0之前插入它，然后在第一个点和第二个点P0和P1之间插入，直到你尝试插入它作为最后一个点。每次尝试将其插入某个位置时，计算电路的总距离并保存最短的总距离。这可以通过预先计算腿部距离并存储该总和来加快。通过减去插入新点的腿部的腿部距离来检查距离，并将点P（n）到你的GPS点的新距离加到P（n + 1）上。如果这个最短的总距离在你的公差水平内，你可以接受它。

这可能不是“最好的”算法（取决于您对最佳的定义），但它对于时间和空间复杂度的路线中的点数是O（n）。所以，除非你的路线中有很多点数，否则每次检查都应该少于一秒，所以这应该在你的时间要求之内。

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

来源

2012-01-18 22:27:20 andand

对我而言，在很大一部分情况下，它是快速而准确的。当路线中的点之间的距离较大时，这种情况下的容差水平将需要增长吗？ –

我将不得不作出至少4000计算如此使用映射溶液一个小时可能是不能接受的，由于体积。

在实际上，这是一个很好的例子，其中一个映射解决方案将是有益的。不是你的传统的“看地图和确定距离”，而是“让数据库确定什么是最接近你的GPS点的路线

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

的SQL Server 2008，其具有Spatial Database Engine功能，或
的PostgreSQL与开源PostGIS（空间）的扩展，其具有显著更多空间分析函数，MS SQL 2008

查看PostGIS ST_Distance函数或MS SQL Server 2008的STDistance函数。这是一个很好的blog entry，它描述了SQL2005与SQL2008的优点。

您也可以考虑阅读（或询问更详细的映射）帖子在gis.stackexchange。整个小组致力于空间分析。给您带来好讨论，看看会

来源

2012-01-19 22:26:12 RyanDalton

谢谢。我也有一位朋友向我推荐gis.stackexchange。速度是我使用映射解决方案的关注点。我必须在这一个小时中至少有4000个。但你是对的可能是最准确的解决方案。 –

地理空间路由

回答

相关问题