   curve extraction
  Hey all. I'm looking for an algorithm which will solve this problem:Input into algorihtm is a list of 2D points. As seen here:Now i'd like to calculate a curve (as a list of points) which would look something like this:I can't use bezier or similar since the data can be "noisy".What else can i use?   
Quote:Original post by NDIRWhat else can i use?That depends on definition of connectedness. For n points, there are n! (and more if restrictions are lessened) paths through it - what is the criteria for connecting them?   ;  Well this curve would be an approximation of a curve this points originally represented before i applied the noise. So i guess the criteria could be some sort of min(distance(a,b)).But if i connect closest points i will not get a smooth curve.   ;  If the points are sorted you can use any of many approximation algorithms that cover the whole range of smoothness vs fidelity tradeoffs between a circle and a polyline, for example NURBS curves with their handy weight parameters.   ;  In general, this is a difficult problem to tackle. You could look into least squares fitting. Although in the end you will probably have to solve a non linear minimization problem and resolve to Non Linear optimization with all sorts of problems such as selecting a good initial solution. Can you give more details about what are you trying to achieve ?   ;  This is (mathematically speaking) a Very Hard Problem. Fitting a curve to an arbitrary set of points is actually pretty difficult. It is tempting to consider the problem fairly straightforward because the human brain can do it so naturally, but as others have noted you're in non-linear territory very quickly.If I interpret your post correctly, you actually already have a curve of best fit, which is the curve pre-noisiness. If that is the case, I'd suggest a simple algorithm something like this:provide the initial set of control points for the curvedepending on your desired noise level, subdivide the curve into n segmentsfor each segment s    based on your curve equation, pick a number of control points p    for each point p   sample the original curve at offset o   displace the point p by your noise function   increment the offset o so that the segment s is evenly divided    given the control points p, construct a new segment    replace the old segment with the newAssuming I've guessed at your intentions correctly, that should work out fairly well [smile]   