用多段三次贝塞尔曲线和距离以及曲率约束逼近数据

Question

我有一些地理数据（下面的图像显示了河流的路径为红点），我想用多段三次贝塞尔曲线近似。通过对计算器等问题，在这里和这里我发现由Philip J.施耐德从“图形宝石”的算法。我成功地实现了它并且可以报告即使有数千个点它也非常快。不幸的是，速度带来了一些缺点，即装配非常不合适。请考虑以下图形：

多段贝塞尔曲线

红点是我的原始数据，蓝线是由Schneider算法创建的多段贝塞尔曲线。如您所见，算法的输入是一个容差，至少与绿线表示的一样高。然而，该算法创建了具有太多急转弯的贝塞尔曲线。你也会在图像中看到这些不必要的急转弯。很容易想象，对于所示数据，具有较小急转弯的贝塞尔曲线，同时仍保持最大公差条件（仅将贝塞尔曲线稍微推向品红色箭头的方向）。问题似乎是算法从我的原始数据中选取数据点作为各个贝塞尔曲线的终点（品红箭头指示一些嫌疑人）。贝塞尔曲线的端点受此限制，

我正在寻找的是一种算法，它使用具有两个约束的多段贝塞尔曲线来近似我的数据：

多段贝塞尔曲线绝不能超过数据点一定距离（由Schneider算法提供）

多段贝塞尔曲线绝不能产生过于尖锐的曲率。检查此标准的一种方法是沿多段贝塞尔曲线滚动具有最小曲率半径的圆，并检查它是否沿其路径接触曲线的所有部分。虽然看起来有更好的方法涉及一阶和二阶导数的叉积

我发现可以创造更好拟合的解决方案或者仅适用于单个贝塞尔曲线（并且省略了如何在多段贝塞尔曲线中找到每个贝塞尔曲线的良好起点和终点的问题）或者不允许最小曲率约束。我认为最小曲率约束是这里的棘手条件。

这是另一个例子（这是手绘而不是100％精确）：

一些例子

让我们假设图一显示曲率约束（圆必须适合整个曲线）以及任何数据点与曲线的最大距离（恰好是绿色圆的半径）。图2中红色路径的成功近似显示为蓝色。该近似值符合曲率条件（圆可以在整个曲线内滚动并在任何地方触摸它）以及距离条件（以绿色显示）。图3显示了路径的不同近似值。虽然它符合距离条件但很明显圆圈不再适合曲率。图4显示了一条不可能用给定约束近似的路径，因为它太尖了。该示例应该说明为了正确地近似路径中的一些尖转弯，算法必须选择不属于路径的控制点。图3显示，如果选择沿路径的控制点，则不能再满足曲率约束。此示例还显示算法必须退出某些输入，因为无法使用给定的约束来近似它。

这个问题是否存在解决方案？解决方案不一定要快。如果需要一天时间来处理1000点，那就没问题了。解决方案也不必是最佳的，因为它必须导致最小二乘拟合。

最后，我将用C和Python实现它，但我也可以阅读大多数其他语言。

Answer 1

多边形化数据找到点的顺序，这样你就可以找到彼此最近的点，并尝试连接“按线”。避免回到原点计算沿路径的推导它是“线”的方向变化，你达到局部最小值或最大值就有你的控制点......这样做是为了减少输入数据（只留下控制点）。曲线现在使用这些点作为控制点。我强烈建议两者的插值多项式x和y单独的插值多项式，例如：x=a0+a1*t+a2*t*t+a3*t*t*ty=b0+b1*t+b2*t*t+b3*t*t*t在哪里a0..a3计算如下：d1=0.5*(p2.x-p0.x);d2=0.5*(p3.x-p1.x);a0=p1.x;a1=d1;a2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2;a3=d1+d2+(2.0*(-p2.x+p1.x));b0 .. b3 以相同的方式计算，但当然使用y坐标p0..p3 是三次插值曲线的控制点t =<0.0,1.0>是曲线参数从。p1到p2这确保了位置和第一次推导是连续的（c1），你也可以使用BEZIER，但它不会像这样好。[edit1]过于尖锐的边缘是一个很大的问题要解决此问题，您可以在获取控制点之前从数据集中删除点。我现在可以想到两种方法：选择对你更好的方法从第一个推导过高的数据集中删除点dx/dl或者坐标dy/dl在哪里x,y，l是曲线长度（沿着它的路径）。从曲线推导精确计算曲率半径是棘手的从数据集中删除导致曲率半径太小的点计算相邻线段（黑线）中点的交点。像图像上的垂直轴（红线）它的距离和连接点（蓝线）是曲率半径。当曲率半径小时，你的极限移除那个点......曲率半径现在，如果你真的只需要BEZIER立方体，那么你可以将我的插值立方体转换为BEZIER立方体，如下所示：//&nbsp; ---------------------------------------------------------------------------//&nbsp; x=cx[0]+(t*cx[1])+(tt*cx[2])+(ttt*cx[3]); // cubic x=f(t), t = <0,1>//&nbsp; ---------------------------------------------------------------------------//&nbsp; cubic matrix&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;bz4 = it4//&nbsp; ---------------------------------------------------------------------------//&nbsp; cx[0]=&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (&nbsp; &nbsp; x0) =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (&nbsp; &nbsp; X1)//&nbsp; cx[1]=&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(3.0*x1)-(3.0*x0) =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(0.5*X2)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-(0.5*X0)//&nbsp; cx[2]=&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (3.0*x2)-(6.0*x1)+(3.0*x0) = -(0.5*X3)+(2.0*X2)-(2.5*X1)+(&nbsp; &nbsp; X0)//&nbsp; cx[3]= (&nbsp; &nbsp; x3)-(3.0*x2)+(3.0*x1)-(&nbsp; &nbsp; x0) =&nbsp; (0.5*X3)-(1.5*X2)+(1.5*X1)-(0.5*X0)//&nbsp; ---------------------------------------------------------------------------&nbsp; &nbsp; const double m=1.0/6.0;&nbsp; &nbsp; double x0,y0,x1,y1,x2,y2,x3,y3;&nbsp; &nbsp; x0 = X1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;y0 = Y1;&nbsp; &nbsp; x1 = X1-(X0-X2)*m; y1 = Y1-(Y0-Y2)*m;&nbsp; &nbsp; x2 = X2+(X1-X3)*m; y2 = Y2+(Y1-Y3)*m;&nbsp; &nbsp; x3 = X2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;y3 = Y2;

Answer 2

我不认为它回答了我的问题。为了使我的问题更清楚，我添加了另一个图形示例。更确切地说，我不认为你的解决方案可以遵守曲率约束，因为它选择路径的点作为曲线的控制点。我的例子表明，对于一些非常尖的路径，有必要选择除输入路径之外的控制点。