Curve fitting unsorted points on a plane

Answer 1

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

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 4

Check this article: Shape-preserving least-squares approximation by polynomial parametric spline curves, it seems to present a solution. Also, see the bibliography at the end.

Answer 5

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.

Answer 6

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,