Best way between two curves

Question

My goal is to find a smooth line of best fit between these two chain shapes. Is there any algorithm that seems to me that can find a set of points (or curves) between two lines similar to this example?

The algorithm that I still occupy the inside, and for each point finds the closest, however this does not work, because (look at the first corner).

(Red is the inside, green is the outside, blue is the optimized dots that I found)

Here is my jsfiddle: http://jsfiddle.net/STLuG/

This is the algorithm:

for (i = 0; i < coords[0].length; i++) { var currentI = coords[0][i]; j = 0; var currentJ = coords[0][j]; currentDist = dist(currentI,currentJ); for (j=1; j < coords[1].length; j++) { possibleJ = coords[1][j]; possibleDist = dist(currentI, possibleJ); if (possibleDist < currentDist) { currentJ = possibleJ; currentDist = possibleDist; } else { } } b_context.fillRect( (currentI.x+currentJ.x)/2+maxX, (currentI.y+currentJ.y)/2+maxY, 1, 1); } 

thanks

Answer 1

I would try the least squares algorithm. You have several points: y0 and x0 and y1 and x1 for the first and second curves, respectively. You want to find a curve y (t) and x (t) that is smooth and intermediate between two given curves. So there is a distance between the first curve (x0 (t), y0 (t)) to your calculated curve (x (t), y (t)):

S0 = SumOverAllT (x0 (t) -x (t)) ^ 2 + (y0 (t) - y (t)) ^ 2

The same for the second curve:

S1 = SumOverAllT (x1 (t) -x (t)) ^ 2 + (y1 (t) - y (t)) ^ 2

The sum of both amounts:

S = S0 + S1

You will have a set of parameters that you want to define. For instance. if you use polynomials:

x (t) = ax + bx * T + cx * t ^ 2 + dx * t ^ 3 ....

y (r) = ay + c * t + su * t ^ 2 + du * t ^ 3 ....

Then you calculate

dS / dax, dS / dbx, dS / dcx, ....

for all calculated parameters

and set these derivatives to zero:

Ds / DAX == 0 Ds / DBX == 0 ....

This will give you a set of linear equations that can be attacked by a Gaussian algorithm or any other method to solve a system of linear equations.

If you use polynomials, it may happen that the curve computes strongly. In this case, I would suggest trying to minimize the integral of the square of the second derivative:

I = integral ((d ^ 2x / dt ^ 2) ^ 2 + (d ^ 2y / dt ^ 2) ^ 2, dt)

you would calculate the differential compared to some additional parameters that you did not use for the above system of equations - adding the rx parameter and calculating dI / drx == 0 - so you have one more parameter and one more equation.

Anyone who has a PHD in mathematics, consult me ​​for any stupidity that I mentioned above.

Also do an online search for:

• Curve fixing
• Spline approximation

A better approach would be to use splines, piecewise continuous polynomials, so

• derivative 0
• first derivative
• second derivative

continuous. Browse or buy numerical recipes to find a code that does just that.

For spline approximation you will have many polynomials:

x0 (t) = a0x + b0x * (t - t0) + c0x * (t-t0) ^ 2 + d0x * (t - t0) ^ 3 ....

x1 (t) = a1x + b1x * (t - t0) + c1x * (t-t0) ^ 2 + d1x * (t - t0) ^ 3 ....

Each polynomial will be used only to match the correspondence t = t0..t1 between two given points.

Then you added equations to make sure that the value, the first and second derivatives are identical for two adjacent polynomials. And put the derivative 2 for the first and last polynomials to zero.

Potentially, you could calculate two splines - one for each of the two input curves that you have:

x0 (t)

y0 (t)

x1 (t)

y1 (t)

And then you can get the middle of two splines:

x (t) = (x0 (t) + (x1 (t) -x0 (t)) / 2

y (t) = (y0 (t) + (y1 (t) -y0 (t)) / 2

make sure the distance between any of these curves and your curve is not zero, so that they do not intersect each other

To make sure that your calculated line does not intersect one of the given lines, you can minimize (sum (sum (1 / (x0-x) ^ 2)) + sum (sum (1 / (x1-x) ^ 2) )))