4

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

我的例子

到目前为止，我的算法采用内部部分，并为每个点找到最接近的部分，但这不起作用，因为（查看第一个角）。

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

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

}

谢谢

4

1 回答 1

2

我会尝试最小二乘算法。您有许多点：分别用于第一条和第二条曲线的 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==0 dS/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 )))

于 2013-11-03T20:52:08.687 回答