我在寻找一种算法路径简化和平滑的二维轨迹。所以，我有2D点的排序列表。这些点应该简化，例如与道格拉斯 - 普克算法。但是，输出必须是光滑的，所以得到的路径应该从贝塞尔曲线或样条曲线构成。是否有对道格拉斯 - 普克算法可能处理这些的任何修改？

I'm searching for an algorithm for path simplification and smoothing for 2D trajectories. So I have a ordered list of 2D points. These points should be simplified, e.g. with the Ramer–Douglas–Peucker algorithm. But the output must be smooth, so the resulting path should be constructed from Bezier curves or splines. Is there any modification of the Ramer–Douglas–Peucker algorithm which could handle this?

我发现了paper.js库的路径简化算法，这不正是我在寻找：的 http://paperjs.org/examples/path-simplification/ 但我无法理解从无证JavaScript源$ C ​​$ C的算法。

I found a path simplification algorithm in the paper.js library, which does exactly what I'm searching for: http://paperjs.org/examples/path-simplification/ But I was not able to understand the algorithm from the undocumented javascript source code.

推荐答案

您想要做的工作分为曲线拟合的范畴。有吨不同的算法用于曲线拟合，但几乎所有的曲线拟合算法可以分成两个不同的类别：内插和近似。插值算法产生的曲线穿过所有数据点恰好而近似算法生成一条曲线，它位于靠近数据点。当然，混合算法也存在。

The work you want to do falls into the category of "curve fitting". There are tons of different algorithms for curve fitting but almost all curve fitting algorithms can be divided into two different categories: interpolation and approximation. Interpolation algorithms produce a curve that passes through all the data points exactly while approximation algorithms generate a curve that lies close to the data points. Of course, hybrid algorithms also exist.

由于要进行平滑的数据点，你应该寻找近似算法。对于你提到的两种算法：RDP算法和施耐德算法（一个在Paper.js），他们都是近似算法。所以，基本上，你可以使用其中任一。对于RDP，得到简化的路径之后，就可以使用创建的Catmull Rom样条或奥佛花键通简化路径的顶点，以获得平滑的曲线。但是，你不能直接控制所产生的样条曲线，并在原来的路径中的顶点之间的偏差。

Since you want the data points to be smoothed, you should be looking for approximation algorithms. For the two algorithms you mentioned: RDP algorithm and Schneider algorithm (the one in Paper.js), they are both approximation algorithms. So, basically you can use either of them. For RDP, after obtaining the simplified path, you can use create a Catmull Rom spline or Overhauser spline thru the vertices of the simplified path to obtain a smooth curve. However, you don't have direct control for the deviation between the resulting spline and the vertices in the original path.

有关施耐德算法，它将开始通过三次Bezier曲线与最终相切约束拟合数据点。如果偏差在所得的曲线过大，那么它将数据点分成两个区域，并与三次贝塞尔曲线与端相切约束拟合数据的每个区域。这个过程将被重复，直至偏差所有三次Bezier曲线是足够小。其结果，它产生了一系列的连接充其量与C1连续三次Bezier曲线（很可能它实际上是G1只）。另外，由于本算法评估来自原始数据点的端切线，在该数据点的噪声会影响端切线评价，因此三次Bezier嵌合。

For Schneider algorithm, it will starts with fitting the data points by a cubic Bezier curve with end tangent constraints. If the deviation to the resulting curve is too large, then it will split the data points into two "regions" and fit each region of data with a cubic Bezier curves with end tangent constraints. This process will be repeated until the deviation to all cubic Bezier curves are small enough. As a result, it produces a series of cubic Bezier curves connected at best with C1 continuity (very likely it is actually G1 only). Furthermore, since this algorithm evaluate the end tangents from original data points, the noise in the data point will affect the end tangent evaluation and therefore the cubic Bezier fitting.

如果您能花时间曲线拟合的话题，你应该看看最小二乘法拟合为B样条曲线。这将产生具有高连续性（C2作为三次B样条曲线的例子）的输出曲线。如果你没有太多的时间来度过，那么施耐德的算法是一个不错的选择罢工的实施成本之间的平衡（如果你要在一个特定的语言重新实现它），得到的曲线的质量。

If you can spent time in the topic of curve fitting, you should look into least square fitting with B-spline curves. This will generate an output curve with high continuity (C2 for cubic B-spline curves for example). If you don't have much time to spent, then Schneider's algorithm is a good choice that strikes a balance between the implementation cost (if you have to re-implement it in a specific language) and the resulting curve's quality.