Best path between two curves

Question

My aim is to find a smooth best fit line between this two circuit curvy shapes. Is there any algorithm betten than mine that can find a set of points (or a curve) between two lines like this example?

The algorithm I have so far takes the inner part and for each point finds the closest, however this doesnt work because (look at the first corner).

(Red is the inner part, green is the outer part, blue is the optimised dots I have 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 least-squares-algorithm. You have a number of points: y0 and x0 and y1 and x1 for the first and the second curve respectively. You want to find a curve y(t) and x(t) which is smooth and in-between the two given curves. So there is the distance between the first curve(x0(t), y0(t)) to your to be 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 sums:

S=S0+S1

You will have a set of parameters which you want to determine. E.g. if you use polynomials:

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

y(t)=ay+by*t+cy*t^2+dy*t^3....

You will then calculate

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

for all parameters to be calculated

and set these derivatives to zero:

dS/dax==0 dS/dbx==0 ....

This will give you a set of linear equations which can be attacked by the gauss algorithm or whatever method to solve a system of linear equations.

If you're using polynomials it might happen that the curve calculated oscillates strongly. In this case I would suggest to try 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 of I vs. some additional parameters which you did not use for above system of equation -- adding a parameter rx and calculating dI/drx==0 -- thus you have one more parameter and one more equation.

Anybody with a PHD in mathematics please advice me on any stupidity I mentioned above.

Also search the internet for:

• Curve fitting
• Spline approximation

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

• the 0 derivative
• the first derivative
• the second derivative

is continuous. Look up or buy Numerical recipes to find code which does exactly this.

For spline approximation you would have a set of 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....

Every polynomial would only be used to cover the matching t=t0..t1 between two given points.

You would then add equations to make certain that the value, first and second derivatives are identical for two neighboring polynomials. And set the 2 derivative for the first and last polynomial to zero.

Potentially you could calculate two splines -- one for every of the two input curves you have:

x0(t)

y0(t)

x1(t)

y1(t)

And then you could derive the middle of the two splines:

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

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

make certain that the distance between any of the given curves and you resulting curve is never zero so that they don't cross each other

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