给定一组有序点，以及由靠近这些点的有序纬度、经度点组成的路径（在纬度/经度坐标中），我想将这些点与路径相关联，理想情况下具有良好的算法复杂度（n*log (n)) 或更好，但也许这可能不现实。
下图更好地说明了我的问题。蓝线是提供的有序路径，红点与蓝线的顺序相同。绿色路径是我想要的结果，它将红点和蓝线合并成一个新的有序路径。
必须为红色点与蓝色路径的距离设置一些阈值，让我们假设红色点距离蓝色路径最多 50 米。
所以，这绝对是我在 Stack Overflow 上问过的最数学和最不寻常的问题。任何想法都可以很好地解决这个问题。我打算用它来将 GTFS 形状数据与描述停止时间的行程数据合并，并将其构建到开源项目Depart App中。
谢谢你的帮助！
在我看来，您有两组点，纬度/经度点和红点。纬度/经度点之一是您的起点。现在将所有其他点视为一个集合，使用（近似？）最近邻算法来找到下一个点。现在重复。唯一的麻烦是，最近邻算法往往是 O(n)，这使得你想做的事情 O(n^2)。
基于此处提供的其他建议，我想我找到了一个有效的 O(n) 算法。
这个想法是首先选择第一个红点作为起点（或者可以选择第一个蓝点）。然后比较这个点到下一个红点和下一个蓝点的距离，选择更近的。重复直到两个列表都用完。这在 Translink 数据集上似乎相当有效。如果我对这个想法进行调整，我会提供更新。
也许您可以使用自定义扫描线算法，这应该会降低查找最近线段的复杂性。
对于每个红点，遍历蓝色段并为其找到最佳段。究竟什么是“最佳”取决于任务，但看起来一个很好的衡量标准是“路径变得多长”。如果 A 是一个红点而 BC 是一个段，那么最好的段将最小化这个：f(A,BC)=(|BA|+|AC|-|BC|)。
当找到最佳段时，应将其替换为 BA 和 AC。以同样的方式处理其他点。
如果没有优化，这将给出 O(N^2)。
如果点或多或少均匀分布并且段长度明显小于整个图形的大小，则一些空间分区可能会有所帮助。