我有一些地理数据（下面的图片显示了一条河红点的路径），我想用多段三次Bezier曲线近似。通过对计算器here和这里我发现从图形宝石的算法，由菲利普·J.施奈德。我成功地实现了它，并可以报告说，即使有千点的速度非常快。不幸的是速度自带的一些缺点，即装配是做得比较草率。请看下图：

I have some geo data (the image below shows the path of a river as red dots) which I want to approximate using a multi segment cubic bezier curve. Through other questions on stackoverflow here and here I found the algorithm by Philip J. Schneider from "Graphics Gems". I successfully implemented it and can report that even with thousands of points it is very fast. Unfortunately that speed comes with some disadvantages, namely that the fitting is done quite sloppily. Consider the following graphic:

红点是我的原始数据和蓝线是由算法施耐德创建的多段贝塞尔。正如你所看到的，输入的算法是一个宽容至少是一样高的绿线表示。不过，该算法创建它有太多的急转弯Bezier曲线。你看到过这些不必要的急转弯图像中。这是很容易想象的少急转弯的同时仍保持最大耐受状态（只是把贝塞尔曲线有点入洋红色箭头的方向）显示数据的贝塞尔曲线。这个问题似乎是，该算法选取的数据点从我的原始数据作为单独的贝塞尔曲线（品红色箭头指向指示某些犯罪嫌疑人）的终点。通过限制这样的贝塞尔曲线的端点，很显然，该算法有时会产生相当尖锐的曲率。

The red dots are my original data and the blue line is the multi segment bezier created by the algorithm by Schneider. As you can see, the input to the algorithm was a tolerance which is at least as high as the green line indicates. Nevertheless, the algorithm creates a bezier curve which has too many sharp turns. You see too of these unnecessary sharp turns in the image. It is easy to imagine a bezier curve with less sharp turns for the shown data while still maintaining the maximum tolerance condition (just push the bezier curve a bit into the direction of the magenta arrows). The problem seems to be that the algorithm picks data points from my original data as end points of the individual bezier curves (the magenta arrows point indicate some suspects). With the endpoints of the bezier curves restricted like that, it is clear that the algorithm will sometimes produce rather sharp curvatures.

我所寻找的是一种算法，接近我的数据与多段贝塞尔曲线有两个约束：

What I am looking for is an algorithm which approximates my data with a multi segment bezier curve with two constraints:

多段贝塞尔曲线绝不能超过一定的距离的数据点的（这是由算法施耐德提供） 多段贝塞尔曲线绝不创建曲率过于尖锐。检查此标准的一种方法是将滚动沿多段贝塞尔曲线的最小曲率半径的圆，并检查是否倒是沿其路径曲线的所有部分。虽然它似乎有一个更好的涉及cross在第一和第二导数的的产物 the multi segment bezier curve must never be more than a certain distance away from the data points (this is provided by the algorithm by Schneider) the multi segment bezier curve must never create curvatures that are too sharp. One way to check for this criteria would be to roll a circle with the minimum curvature radius along the multisegment bezier curve and check whether it touches all parts of the curve along its path. Though it seems there is a better method involving the cross product of the first and second derivative

我发现这可悲的是创造出更好的适合或者只针对单个贝塞尔曲线的工作（而忽略了如何找到好的起点和终点在多段贝塞尔曲线的每个贝塞尔曲线的问题），或者不允许最小的解决方案曲率约束实现的。我觉得，最小曲率约束实现是很棘手的情况在这里。

The solutions I found which create better fits sadly either work only for single bezier curves (and omit the question of how to find good start and end points for each bezier curve in the multi segment bezier curve) or do not allow a minimum curvature contraint. I feel that the minimum curvature contraint is the tricky condition here.

下面另一个例子（这是手工绘制的，而不是100％precise）：

Here another example (this is hand drawn and not 100% precise):

允许假设图1示出了两个，曲率约束（圆必须适合沿整个曲线），以及任何数据点的从曲线的最大距离（这恰好是在绿色的圆的半径） 。在图二红色路径的成功近似以蓝色显示。这近似荣誉的曲率条件（圆圈可以滚动整个曲线内，处处触动吧）以及距离条件（以绿色显示）。图3显示了不同的近似路径。而它荣誉的距离条件很清楚的是，圆不适合曲率任何更多。图4示出了这是不可能对具有给定的约束来近似，因为它太尖的路径。本实施例假定以说明，为了正确地近似一些尖尖转动路径中，这是必要的，该算法选择的控制点不属于所述路径的一部分。图3表明，如果被选择沿着路径控制点，曲率约束不能再被满足。这个例子也显示了该算法必须退出上一些输入作为它不可能对具有给定约束近似它

Lets suppose that figure one shows both, the curvature constraint (the circle must fit along the whole curve) as well as the maximum distance of any data point from the curve (which happens to be the radius of the circle in green). A successful approximation of the red path in figure two is shown in blue. That approximation honors the curvature condition (the circle can roll inside the whole curve and touches it everywhere) as well as the distance condition (shown in green). Figure three shows a different approximation to the path. While it honors the distance condition it is clear that the circle does not fit into the curvature any more. Figure four shows a path which is impossible to be approximated with the given constraints because it is too pointy. This example is supposed to illustrate that to properly approximate some pointy turns in the path, it is necessary that the algorithm chooses control points which are not part of the path. Figure three shows that if control points along the path were chosen, the curvature constraint cannot be fulfilled anymore. This example also shows that the algorithm must quit on some inputs as it is not possible to approximate it with the given constraints.

是否存在一个解决这个问题？溶液不必要快。如果需要，每天要处理1000点，那么这很好。该解决方案也并不必须是最佳的，即它必须产生适合最小二乘

Does there exist a solution to this problem? The solution does not have to be fast. If it takes a day to process 1000 points, then that's fine. The solution does also not have to be optimal in the sense that it must result in a least squares fit.

在最后，我会用C和Python实现这一点，但我可以读取大多数其他语言了。

In the end I will implement this in C and Python but I can read most other languages too.

推荐答案

我发现，满足我的criterea的解决方案。解决的办法是先找一个B样条曲线近似点在最小二乘意义上，然后将这些样条线成多段贝塞尔曲线。 B样条是有，在相对于贝塞尔曲线他们不会通过控制点传递以及提供一种方法指定的近似曲线的所希望的平滑度的优点。所需的功能，产生这样的样条曲线在FITPACK库到SciPy的提供了Python绑定实现的。让我们假设我读我的数据放到表 X 和是，那么我可以这样做：

I found the solution that fulfills my criterea. The solution is to first find a B-Spline that approximates the points in the least square sense and then convert that spline into a multi segment bezier curve. B-Splines do have the advantage that in contrast to bezier curves they will not pass through the control points as well as providing a way to specify a desired "smoothness" of the approximation curve. The needed functionality to generate such a spline is implemented in the FITPACK library to which scipy offers a python binding. Lets suppose I read my data into the lists x and y, then I can do:

import matplotlib.pyplot as plt
import numpy as np
from scipy import interpolate
tck,u = interpolate.splprep([x,y],s=3)
unew = np.arange(0,1.01,0.01)
out = interpolate.splev(unew,tck)
plt.figure()
plt.plot(x,y,out[0],out[1])
plt.show()

然后结果是这样的：

The result then looks like this:

如果我想要的曲线更平滑，那么我就可以增加取值参数 SPL $ P $页 。如果我想近似更接近数据，我可以降低取值参数不太光滑。通过经历多个取值参数编程，我可以找到适合给定的要求，一个好的参数。

If I want the curve more smooth, then I can increase the s parameter to splprep. If I want the approximation closer to the data I can decrease the s parameter for less smoothness. By going through multiple s parameters programatically I can find a good parameter that fits the given requirements.

虽然现在的问题是如何将其结果转换成Bezier曲线。 rel="nofollow">此邮件通过扎卡里·平卡斯在