Curve fitting unsorted points on a plane

Question

Question: How do you fit a curve to points on a plane if they aren't single valued?

For the example shown, how would one fit a curve (like the black one) to the noisy blue data? It's similar to spline smoothing, but I don't know the order of the data.

Matlab would be preferred, but pseudocode is fine. Or a pointer to what the correct terminology for this problem is would be great.

Thanks

Answer 1

Your data look like a two-dimensional parametric plot of (x,y) as a function of some underlying parameter t. As such, it may be possible to do a least-squares fit of x(t) and y(t) if you can come up with a reasonable model for them. Your data appear to describe a limacon.

Answer 2

Edit: nvm misinterpreted the question. I'll leave this answer here anyway.

Maybe try finding the convex hull of the points first then fit the convex hull on the plain

http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html <--includes java animations of implementation http://en.wikipedia.org/wiki/Convex_hull_algorithms

If you don't want efficiency there are some very simple implementations like the gift wrapping version which is O(n^2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

The divide and conquer version is O(nlogn)

Answer 3

you could try to infer the ordering of the points, then apply the spline procedures. there is an ambiguity where the curve crosses itself, of course.

perhaps the most naive approach would be to compute the Delaunay Triangulation (nlogn time), from which approximate a Euclidian Minimum Distance Hamiltonian Cycle through the points. You would still have to figure out where the 'ends' are. From the ordering you could then apply the spline techniques. For a reference, see Finding Hamiltonian Cycles in Delaunay Triangulations Is NP-Complete, or Reinelt's paper on TSP heuristics, 1992, or EMST at Wikipedia

hth,

Answer 4

For piecewise approximations using B-splines you can use this Matlab package. It works on automatic and half-manual modes.

Answer 5

I'm no expert in this but I found this page, talking about curve reconstruction, which seems to fit your question. Still reading the papers and having a hard time understanding them, so I can't provide a solution yet.

Answer 6

You'll have to do multiple piecewise fitting or splines. Don't expect any algorithm to be able to do all of it in one go. Could be at least three curves: the first one up to the intersection, the loop, and then back from the intersection forward.

Answer 7

This problem is really hard if you don't have an ordering. Doing a least squares on some (x(t), y(t)) is easy -- assuming you know the ordering of t.

You'll probably need some kinda search algorithm. A genetic algorithm might be ok.