位置积分：到指定路线的距离

Question

首先让我说明这个想法：

我想检查用户到指定路线的距离。该路线由多个位置点组成（在图中，点a，b，c，d）。两个相邻点描述一个向量（蓝线AB，BC，CD中的图片）

我们应用（机器人特别是，但不是该问题的一部分） 在使用者的位置在沿着路线行驶时被追踪。我想检查每个新的位置，如果用户仍然在路线上（或在距离X内）。

我画了沿线3个可能地点：

• 位置1是没有问题的。我把从点1到矢量ab的垂直线放下。这给了我一个位置点上这个向量，我可以计算两点之间的距离（与android：Location.distanceTo()）

• 位置2因为我正在处理向量，他们没有开始也没有结束。黑线是矢量ab的投影。计算最近的距离会给我与向量ab的距离很近，但距离向量bc很近。事实上，我需要计算与bc的距离，因为路线是如何进行的。但我怎么知道我的算法哪个向量我需要选择计算距离？

• 位置3为我提供了使用向量ab或bc进行计算的可能性。两者几乎同样接近。如何知道选择哪一个？

圆这件事：

我有一个位置点的数组：

{[lat1, lon1], [lat2, lon2],[...]} 

我的应用程序正在跟踪用户位置。我现在想要将新位置与数组中的该轨道进行比较。

有人知道覆盖问题的算法，或有人可以帮助我的算法吗？ （伪代码是足够的）

//编辑：我刚刚读了关于四叉树算法。也许这是除了实施Soonts之外的一个选项。

Answer 1

首先从纬度/经度转换所有的数据（用户位置，点）到X/Y公里，使用下面的公式：

Y = LAT * 111，X = LON * 111 * COS（LAT）

（这会略微失败，航线不再那么千英里，并大幅失败两极附近或者当你的路径穿过180个经络，希望这是确定您的任务）。

然后使用以下公式找到点与每个段之间的距离：https://stackoverflow.com/a/1501725/126995，并搜索最小距离。一些性能优化需要你的路线有超过200段。

P.S.如果你对这种方法的局限性感到不满 - 寻找球体上点和线段之间距离的公式，但我可以向你保证这些包含很多三角函数，我怀疑便宜的Android手机会做到这一点快速路线很长。