两条曲线之间的最佳路径

Question

我的目标是在这两个曲线形状之间找到一条平滑的最佳拟合直线。 是否有比我的算法更好的算法，可以像这个例子一样找到一组点（或曲线）在两条直线之间？

我目前的算法只取内部部分，对于每个点找到最近的点，但这并不起作用，因为（看第一个角落）。

（红色是内部部分，绿色是外部部分，蓝色是我找到的优化点）

这是我的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);

}

谢谢

- piggyback

---

只是一个想法：我建议首先通过简单的插值来填补红线曲线中的空白部分。然后您的算法也应该适用于图形的左侧。 - ojdo

Answer 1

我建议尝试最小二乘算法来解决问题。 你有一些点：第一个曲线的y0和x0，以及第二个曲线的y1和x1。 你想要找到一条光滑的、介于两个给定曲线之间的曲线y(t)和x(t)。 因此第一条曲线(x0(t), y0(t))到你要计算得出的曲线(x(t), y(t))的距离是：

S0=对所有t求和(x0(t)-x(t))^2 + (y0(t) - y(t))^2

第二条曲线同理：

S1=对所有t求和(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==0 dS/dbx==0 ....

这将给你一组线性方程，可以通过高斯算法或其他解线性方程组的方法来求解。

如果你使用的是多项式，可能会发现计算出的曲线强烈振荡。在这种情况下，我建议尝试最小化二阶导数的平方的积分：

I=integral((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。 然后您需要添加方程，以确保相邻两个多项式的值、一阶导数和二阶导数都相同，并将第一个和最后一个多项式的二阶导数设置为零。 可能您可以计算两个样条曲线——每个输入曲线都有一个： 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)))。

- user678269