给定一组有序的点，并提出了有序的纬度，经度点的路径去接近那些点（在纬度/经度坐标），我想点的路径相关联，地理位置优越，具有良好的算法的复杂性（的n * log（n））的或更好的，但也许这可能是不现实的。

Given a set of ordered points, and a path made up of ordered lat,lon points that goes near those points (in lat/lon coordinates), I want to associate the points with the path, ideally with good algorithmic complexity (n*log(n)) or better, but maybe that might not be realistic.

下面的图显示了更好的我的问题。蓝线是所提供的有序路径，红色点都在相同的顺序的蓝线。绿色路径是我想要的结果，它融合了红点，蓝线进入一个新的有序的道路。

The below diagram illustrates my question better. The blue line is the ordered path that is provided, and the red points are in the same order as the blue line. The green path is my desired result, which merges the red points and the blue line into a new ordered path.

某些阈将对从蓝色路径红色点之间的距离来进行设置，让我们假设红色点是在从蓝色路径至多50米。

Some threshold would have to be set for the distance of the red points from the blue path, let's assume that the red points are at most 50 meters from the blue path.

所以，这绝对是最工科数学和不寻常的问题，我也问过的堆栈溢出。任何想法将是巨大的解决这一点。我打算用它来合并与描述停止时间旅行数据GTFS形状数据，并打造成为开源项目，出发应用。

So, this is definitely the most mathmatical and unusual question I have asked on Stack Overflow. Any ideas would be great on solving this. I am planning to use it to merge GTFS shape data with trip data which describes stop times, and build it into the open source project, Depart App.

感谢您的帮助！

推荐答案

建立在此处提供的其他建议，我想我已经找到了一个O（n）的算法，有效地运作。

Building on the other suggestions provided here, I think I have found a O(n) algorithm that works effectively.

我们的想法是先挑头红点为出发点（或者可以选择的第一个蓝点）。然后比较从这点到下一个红点，下一个蓝点的距离，挑接近。重复，直到两个列表被耗尽。这似乎是对的Translink数据集相当有效。我举一个更新，如果我做出调整，以这样的想法。

The idea is to first pick the first red point as the starting point (or could choose the first blue point). Then compare the distance from this point to the next red point and the next blue point, pick the closer. Repeat until both lists are depleted. This seems to be quite effective on the Translink data set. I will give an update if I make tweaks to this idea.