将附近的点与路径关联

Question

给定一组有序点和由有序纬度和经度点组成的路径（以纬度/经度坐标表示），我希望将这些点与路径关联起来，最好具有良好的算法复杂度（n * log（n））或更好，但也许这可能不现实。

下面的图示更好地说明了我的问题。蓝线是提供的有序路径，红色点按照与蓝线相同的顺序排列。绿色路径是我的期望结果，它将红色点和蓝线合并为一个新的有序路径。

需要为红点与蓝线路径的距离设定某个阈值，假设红点距蓝线路径最多50米。

所以，这绝对是我在Stack Overflow上提出的最数学化和不寻常的问题。任何解决方案的想法都将是有益的。我计划将其用于合并GTFS形状数据与描述停靠时间的行程数据，并将其构建到开源项目Depart App中。

谢谢您的帮助！

- Russell

---

我理解的对吗：您想要绿色路径，即连接包含红点和蓝色路径节点的有序集合的路径？ - carlpett

没错，绿线必须按顺序包含所有的红点和蓝点。 - Russell

Answer 1

在其他提供的建议基础上，我认为我找到了一个O(n)算法，可以有效地解决问题。

这个想法是首先选择第一个红点作为起始点（或者也可以选择第一个蓝点）。然后比较从这个点到下一个红点和下一个蓝点的距离，选择更近的那个。重复此过程，直到两个列表都被用完。这在Translink数据集上似乎非常有效。如果我对这个想法进行调整，我会更新一下。

- Russell

Answer 2

在我看来，您有两组点，即纬度/经度点和红点。其中一个纬度/经度点是您的起始点。现在将所有其他点视为一组，使用（近似？）最近邻算法找到下一个点。现在重复这个过程。唯一的问题是，最近邻算法往往是O(n)，这使得您想要做的变成了O(n^2)。

- andrewdski

---

这似乎是一个不错的、简单的想法。需要注意的一点是，得到的有序点集必须按顺序包含所有蓝色点和所有红色点（交替排列）。因此，如果公交路线沿着一条街道前进，然后在同一次旅行中返回（虽然不太可能，但很有可能），最近邻算法将失败，因为结果点将是无序的。然而，也许只需比较每个有序集合中的下两个点，就可以做出正确的决策。 - Russell

这个想法的修改效果很好。取形状和停止点，假设其中一个是线条中的第一个点。然后查看下一个形状点和下一个停止点之间的距离，并选择更近的一个。重复n次，进行log(n)操作！我敢打赌，这种简单的方法可能会有一些问题，但到目前为止，它似乎还不错。 - Russell

这不是一个小修改，而是一个重大的改进。你可以将其发布为自己的答案 - 我会投票支持它。（因为这就是我要建议的内容。） - AShelly

但这不是O(N)，而是lg(N)吗？ - AShelly

但是看着你的图片，如果我将第一个蓝色腿和前两个红点逆时针围绕红点#2和#3之间的经纬度点旋转。在我看来，我可以将红点#2和#3靠近，这样您就可以直接从#2到#3。现在，根据蓝色腿#2的长度，您可能永远不会更靠近下一个蓝色点。那可以吗？（实际上，我的解决方案也可能跳过一个蓝色点，但它可以恢复并开始再次使用它们。） - andrewdski

好的观点，我也很担心这个问题，但幸运的是，使用Translink的数据集，这似乎不是一个问题。问题是我真的不想错过任何站点（虽然错过形状点是可以的）。所以我宁愿让它失败而不是跳过点。不过，我可能需要在这方面添加一些智能，例如查看几个即将到来的站点（红点），而不仅仅是一个。 - Russell

Answer 3

也许你可以使用自定义的扫描线算法，这应该可以降低查找最近线段的复杂度。

- Igor Brejc

---

是的，这个也好像是个不错的主意。我觉得我可能得做类似的事情（限制搜索范围），但现在只是看列表中的下一个并选择最接近的工作。顺便说一下，Maperitive很棒！ - Russell

Answer 4

对于每个红点，迭代蓝色线段并找到最佳的线段。什么是“最佳”的取决于任务，但好的度量似乎是“路径变长了多少”。如果A是一个红点，BC是一个线段，那么最佳的线段将使这个值最小：f(A,BC)=(|BA|+|AC|-|BC|)。

当找到最佳的线段时，应该用BA和AC替换它。同样地，其他点也应该被处理。

没有优化的话，这将给出O(N^2)。

如果点分布比较均匀，线段长度显著小于整个图形的大小，则一些空间划分可能会有所帮助。

- maxim1000

---

虽然我不完全理解您所说的嵌入点，但您的想法似乎与第一个回答者非常相似，尽管空间划分是个好主意。 - Russell

我所说的“嵌入点A”，意思是用两个线段：BA和AC，替换最近的线段BC。可能我误解了第一个回答，因为我以为他建议搜索最近的点而不是线段... - maxim1000

不，实际上我是指点数。（有趣的是，当我读到你的时候，我误解了，以为你是指点数！） - andrewdski

经过一些思考，我发现距离点线段和距离点点都不是一个好的度量标准。因此，我稍微改变了算法。 - maxim1000