将附近的点与路径关联
给定一组有序点，以及由靠近这些点（以纬度/经度坐标表示）的有序纬度、经度点组成的路径，我想将这些点与路径关联起来，理想情况下具有良好的算法复杂性（n * log (n)) 或更好，但这也许不现实。
下图更好地说明了我的问题。蓝线是提供的有序路径，红点与蓝线的顺序相同。绿色路径是我想要的结果，它将红点和蓝线合并成一条新的有序路径。
必须为红点与蓝色路径的距离设置一些阈值，让我们假设红点距离蓝色路径最多 50 米。
所以，这绝对是我在 Stack Overflow 上问过的最数学化、最不寻常的问题。任何想法都会很好地解决这个问题。我计划使用它将 GTFS 形状数据与描述停止时间的行程数据合并，并将其构建到开源项目中，离开应用程序。
感谢您的帮助！
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.
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.
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.
Thanks for your help!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在我看来，你有两组点，纬度/经度点和红点。纬度/经度点之一是您的起点。现在将所有其他点视为一个集合，使用（近似？）最近邻算法来查找下一个点。现在重复一遍。唯一的麻烦是，最近邻算法往往是 O(n)，这使得你想要做的事情变成 O(n^2)。
It seems to me, you have two sets of points, the lat/lon points, and the red points. One of the lat/lon points is your starting point. Now considering all the other points as a set, use an (approximate?) nearest neighbor algorithm to find the next point. Now repeat. The only trouble is, that nearest neighbor algorithms tend to be O(n), which makes what you want to do O(n^2).
基于此处提供的其他建议，我认为我已经找到了一种有效运行的 O(n) 算法。
这个想法是首先选择第一个红点作为起点（或者可以选择第一个蓝点）。然后比较该点到下一个红点和下一个蓝点的距离，选较近的。重复此操作，直到两个列表都耗尽。这在 Translink 数据集上似乎相当有效。如果我对这个想法进行调整，我会提供更新。
Building on the other suggestions provided here, I think I have found a O(n) algorithm that works effectively.
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.
也许您可以使用自定义扫描线算法，这应该会降低查找最近线段的复杂性。
Perhaps you could use a custom sweep line algorithm, this should reduce the complexity of finding the nearest line segment.
对于每个红点，迭代蓝色段并找到最适合它的段。到底什么是“最好”取决于任务，但看起来一个好的衡量标准是“路径变得多长”。如果 A 是红点，BC 是线段，则最佳线段将最小化：f(A,BC)=(|BA|+|AC|-|BC|)。
当找到最佳段时，应将其替换为BA和AC。以同样的方式处理其他点。
如果不进行优化，这将给出 O(N^2)。
如果点分布或多或少均匀，并且线段长度明显小于整个图形的大小，则一些空间分区可能会有所帮助。
For each red point iterate through blue segments and find the best segment for it. What exactly "best" is depends on the task, but it looks like a good measure would be "how much longer path becomes". If A is a red point and BC is a segment, then the best segment will minimize this: f(A,BC)=(|BA|+|AC|-|BC|).
When the best segment is found, it should be replaced with BA and AC. In the same way other points should be processed.
Without optimizations this will give O(N^2).
If points are distributed more or less uniformly and segment length is significantly less than size of entire figure, some space partitioning may help.