一尘不染

二维轨迹的路径简化和平滑算法

algorithm

我正在寻找2D轨迹的路径简化和平滑算法。所以我有一个2D点的有序列表。这些点应该简化,例如使用Ramer–Douglas–Peucker算法。但是输出必须是平滑的,因此应使用贝塞尔曲线或样条曲线构建最终路径。是否可以修改Ramer–Douglas–Peucker算法的任何修改?

我在paper.js库中找到了一种路径简化算法,该算法正是我要搜索的内容:http ://paperjs.org/examples/path-simplification/
但我无法从未公开的javascript中理解该算法源代码。


阅读 1572

收藏
2020-07-28

共1个答案

一尘不染

您要进行的工作属于“曲线拟合”类别。曲线拟合有很多不同的算法,但是几乎所有的曲线拟合算法都可以分为两类:插值和逼近。插值算法产生的曲线精确地穿过所有数据点,而近似算法产生的曲线接近数据点。当然,也存在混合算法。

由于您希望对数据点进行平滑处理,因此您应该寻找近似算法。对于您提到的两种算法:RDP算法和Schneider算法(Paper.js中的一种),它们都是近似算法。因此,基本上您可以使用它们中的任何一个。对于RDP,获得简化路径后,可以使用通过简化路径的顶点创建Catmull
Rom样条或Overhauser样条来获得平滑曲线。但是,您无法直接控制所得样条曲线与原始路径中的顶点之间的偏差。

对于Schneider算法,它将首先通过具有最终切线约束的三次方Bezier曲线拟合数据点。如果与所得曲线的偏差太大,则会将数据点分为两个“区域”,并使用具有最终切线约束的三次方贝塞尔曲线拟合数据的每个区域。将重复此过程,直到与所有三次贝塞尔曲线的偏差足够小为止。结果,它产生了一系列三次贝塞尔曲线,这些曲线最好与C1连续性相连(很可能实际上仅是G1)。此外,由于此算法从原始数据点评估末端切线,因此数据点中的噪声将影响末端切线评估,从而影响三次贝塞尔拟合。

如果您可以花时间在曲线拟合主题上,则应研究B样条曲线的最小二乘拟合。这将生成具有高连续性的输出曲线(例如,对于立方B样条曲线为C2)。如果您没有太多时间花费,那么Schneider算法是一个不错的选择,它可以在实现成本(如果必须以特定语言重新实现)与最终曲线质量之间取得平衡。

2020-07-28