给定一组有序点，以及一条由靠近这些点的有序纬度、经度点组成的路径(在纬度/经度坐标中)，我想将这些点与路径相关联，理想情况下具有良好的算法复杂性( n*log(n)) 或更好，但这可能不现实。
下图更好地说明了我的问题。蓝线是提供的有序路径，红点与蓝线的顺序相同。绿色路径是我想要的结果，它将红点和蓝线合并为一个新的有序路径。
必须为红点与蓝色路径的距离设置一些阈值，我们假设红点与蓝色路径的距离最多为 50 米。
所以，这绝对是我在 Stack Overflow 上问过的最数学和最不寻常的问题。任何想法都会很好地解决这个问题。我计划使用它将 GTFS 形状数据与描述停止时间的行程数据合并，并将其构建到开源项目中，Depart App .
感谢您的帮助!
最佳答案
在我看来，您有两组点，纬度/经度点和红点。纬度/经度点之一是您的起点。现在将所有其他点视为一个集合，使用(近似？)最近邻算法找到下一个点。现在重复。唯一的麻烦是，最近邻算法往往是 O(n)，这使得你想做的事情是 O(n^2)。
关于algorithm - 将附近的点与路径相关联，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6605834/