如何从嘈杂的X,Y数据中确定路径

Question

我有一个嘈杂的X,Y点的未排序列表.然而,他们确实形成了通往世界的道路.我想要一种算法来使用线段绘制这些数据的近似值.

这类似于使用线拟合算法来选择线性数据的近似值的方法.我的问题只会更难,因为这条路在世界各地弯曲和蜿蜒. alt text http://www.praeclarum.org/so/pathfinder.png

有没有人知道任何标准/强大/易于理解的算法来实现这一目标？

问答:

吵闹是什么意思？如果我有一个理想的路径实现,那么我的一组点将从该理想路径中采样,并将高斯噪声添加到X和Y元素.我不知道那个噪音的均值或标准差.我或许可以猜到std dev ......

这些点是否靠近,但不是在你想要近似的一些理想但复杂的路径上？是.

你有关于他的路径形状的任何先验信息吗？获取此类信息的任何其他方式？不幸的是.

Answer 1

Bezier插值可能适合您的问题.

然而,这并没有解决将点分配到路径中的问题; 有许多方法需要考虑:

• 任何"最佳"类型的路径(例如,路径上每个点的最小方向变化,*通过所有点的最短路径)都可能归结为NP完整的旅行商问题(TSP).
• 一种"合理的"路径,用于聚合节点,然后在群集之间以及群集内路由.当然,群集越大,或群集的数量越大,这个较小的问题看起来就像一个大的n TSP.
• 按一个轴排序点.如果存在多于2个轴,则某些尺寸减小策略可能是有用的.例如独立分量分析.

Answer 2

对于未排序的列表，您不会真正知道每个段中应包含哪些点，所以我想您可以选择最近的点。

一种方法是随机选择一个起点，并选择最近的点作为每个步骤中的下一个点。将前两个点添加到集合 S 中。

将一条线拟合到 S 中的点，直到 RMS 超过某个值，然后清除 S 并开始一条新线。

连续线的交点将是线段的端点。