如何从嘈杂的 X、Y 数据确定路径 [英] How to determine path from noisy X, Y data

问题描述

我有一个噪声 X、Y 点的未排序列表.然而，它们确实形成了一条穿越世界的路径.我想要一种算法来使用线段绘制此数据的近似值.

I have an unsorted list of noisy X, Y points. They do, however, form a path through the world. I would like an algorithm to draw an approximation of this data using line segments.

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

This is similar to how you would use a line -fitting algorithm to pick an approximation of linear data. My problem is only harder because the path bends and winds around the world. alt text http://www.praeclarum.org/so/pathfinder.png

有没有人知道任何标准/健壮/易于理解的算法来实现这一点?

Does anyone know of any standard / robust / easy to comprehend algorithms to accomplish this?

问答:

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

What do you mean by noisy? If I had an ideal realization of the path, then my set of points would be sampled from that ideal path with gaussian noise added to the X and Y elements. I do not know the mean or standard deviation of that noise. I may be able to guess at the std dev...

这些点是否位于您试图近似的理想但复杂的路径附近，而不是在这条路径上?是的.

你有关于路径形状的任何先验信息吗?还有其他方法可以获取此类信息吗?很遗憾没有.

推荐答案

对于未排序的列表，您将无法真正知道每个段中包含哪些点，因此我想您可以选择最近的点.

With an unsorted list, you won't really know which points to include in each segment, so I guess you could just go with the closest point.

>

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

One way could be to pick a start point at random, and pick the closest point as the next point in each step. Add the first two points to a set S.

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

Fit a line to the points in S until the RMS exceeds some value, then clear S and start a new line.

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

The intersection of consecutive lines would be the end-points of the segments.

这篇关于如何从嘈杂的 X、Y 数据确定路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！