31

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

Community
  • 1
  • 1
tkw954
  • 940
  • 2
  • 10
  • 16

7 Answers7

9

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.

las3rjock
  • 8,612
  • 1
  • 31
  • 33
  • While the data shown *does* have an underlying curve (a rose function), this was just because it was easy to make a plot. I need to fit a curve to any arbitrary data. – tkw954 Jun 15 '09 at 00:12
  • 4
    You have to know something about the underlying data in order to any kind of useful curve fitting. From your example above, there's no particular reason (for a naive algorithm) to choose to go straight at the intersection, rather than making two sharp right turns. You can fit any curve to any set of points, it just becomes a matter of "fitness". You need a heuristic to select what curve you're going to use, then any standard error-minimization routine will fit the curve to the points. – Mark Bessey Jun 15 '09 at 00:44
  • 2
    I think if you included a regularization term (such as minimizing the curvature) it would sort out the ambiguity at the intersection. – tkw954 Jun 15 '09 at 00:50
1

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,

shabbychef
  • 1,940
  • 3
  • 16
  • 28
1

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

Eugene Katrukha
  • 21
  • 2
1

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.

Jason
  • 2,950
  • 2
  • 30
  • 50
1

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)

Charles Ma
  • 47,141
  • 22
  • 87
  • 101
0

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.

Ray
  • 2,974
  • 20
  • 26
0

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.

duffymo
  • 305,152
  • 44
  • 369
  • 561