How to determine path from noisy X, Y data

Question

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.

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?

Q&A:

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...

Do the points lie near, but not on, some ideal but complicated path which you seek to approximate? Yes.

Do you have any a priori information about he shape of the path? Any other way to get such information? Unfortunately not.

Answer 1

Bezier Interpolation may fit your problem.

This does not address the ordering of the points into a path, however; there are a number of approaches to consider:

• Any "optimal" type of path (e.g. smallest direction change at each point on the path, * Shortest path through all points) will likely boil down the NP complete Travelling Salesman Problem (TSP).
• A "reasonable" path to cluster the nodes and then route between clusters, and within clusters. Of course, the larger the cluster, or the larger the number of clusters the more this smaller problem looks like a large n TSP.
• Ordering the points by one axis. If there are much more than 2 axes, some dimensional reduction strategy may be useful. e.g. Independent Component Analysis.

Answer 2

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.

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.

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.

Answer 3

If your points are close to each other, you can normal "straight" lines (orthogonal lines). Using the normal smoothing algorithms. You can see the world as being flat.

If they are far apart, you need to compensate for the rounding of the earth, by using great circles to navigate from point to point. Otherwise your straight lines will make a longer way.

It is your choice if a point is too far to create straight lines.

Further you have to know if you need to "visit" each point, or just need to go near, and how near that near is.

If you need to send the course(s) to a plane, ship or other traveller, you probably need to visit each point. If you get the GPS data from an object, you probably just want to plot a course on a screen, and remove the noise.

---

After seeing your edits: If this is an object moving some traject you want to plot, you might want to smooth the direction and speed instead of the x/y values. (Making your measured values (x) have a fixed and increasing Y-interval makes smoothing a lot easier.)