javascript - 两条曲线之间的最佳路径

Question

我的目标是在这两个电路弯曲形状之间找到一条平滑的最佳拟合线。有没有比我的更好的算法可以像这个例子一样在两条线之间找到一组点(或曲线)？

我目前使用的算法采用内部部分，并为每个点找到最近的点，但这不起作用，因为(看第一个 Angular )。

(红色是内部，绿色是外部，蓝色是我找到的优化点)

这是我的 jsfiddle: http://jsfiddle.net/STLuG/

这是算法:

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

}

谢谢

Answer 1

我会尝试最小二乘算法。您有许多点:第一条曲线和第二条曲线分别为 y0 和 x0 以及 y1 和 x1。您想要找到一条曲线 y(t) 和 x(t)，它们是平滑的并且介于两条给定曲线之间。所以第一条曲线(x0(t), y0(t))和你要计算的曲线(x(t), y(t))之间的距离是:

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

第二条曲线也一样:

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

两者之和:

S=S0+S1

您将有一组要确定的参数。例如。如果你使用多项式:

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

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

然后你会计算

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

对于所有要计算的参数

并将这些导数设置为零:

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

这将为您提供一组线性方程组，可以通过高斯算法或任何求解线性方程组的方法对其进行攻击。

如果您使用多项式，计算出的曲线可能会剧烈振荡。在这种情况下，我建议尽量减少二阶导数平方的积分:

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

您将计算 I 与您未用于上述方程组的一些附加参数的差分——添加参数 rx 并计算 dI/drx==0——因此你有一个参数和一个参数等式。

任何拥有数学博士学位的人请对我上面提到的任何愚蠢行为提出建议。

也可以在互联网上搜索:

• 曲线拟合
• 样条近似

更好的方法是使用样条曲线——分段连续多项式，这样

• 0导数
• 一阶导数
• 二阶导数

是连续的。查找或购买数值食谱以找到执行此操作的代码。

对于样条近似，您将有一组多项式:

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

每个多项式只会用于覆盖两个给定点之间的匹配 t=t0..t1。

然后您将添加方程式以确保两个相邻多项式的值、一阶导数和二阶导数相同。并将第一个和最后一个多项式的 2 导数设置为零。

可能您可以计算两条样条曲线——一条对应两条输入曲线中的每一条:

x0(t)

y0(t)

x1(t)

y1(t)

然后你可以推导出两条样条曲线的中间:

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

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

确保任何给定曲线与您生成的曲线之间的距离永远不会为零，这样它们就不会相互交叉

为了确保您计算出的线不交叉给定线之一，您可以最小化 (sum(sum(1/(x0-x)^2)) + sum(sum (1/(x1-x)^2)))