Tho*_* W. 7 algorithm computational-geometry
我正在寻找一种路径简化和平滑2D轨迹的算法.所以我有一个2D点的有序列表.这些点应该简化,例如使用Ramer-Douglas-Peucker算法.但输出必须是平滑的,因此生成的路径应该由贝塞尔曲线或样条曲线构造.是否可以对Ramer-Douglas-Peucker算法进行任何修改？
我在paper.js库中找到了一个路径简化算法,它正是我正在搜索的内容:http://paperjs.org/examples/path-simplification/ 但是我无法从未记录的javascript中理解算法源代码.
fan*_*ang 11
您想要做的工作属于"曲线拟合"类别.曲线拟合有很多不同的算法,但几乎所有的曲线拟合算法都可以分为两个不同的类别:插值和近似.插值算法产生的曲线精确地通过所有数据点,而近似算法生成靠近数据点的曲线.当然,也存在混合算法.
由于您希望平滑数据点,因此您应该寻找近似算法.对于您提到的两种算法:RDP算法和Schneider算法(Paper.js中的算法),它们都是近似算法.所以,基本上你可以使用它们中的任何一个.对于RDP,在获得简化路径后,您可以使用通过简化路径的顶点创建Catmull Rom样条曲线或Overhauser样条曲线来获得平滑曲线.但是,您无法直接控制生成的样条线与原始路径中的顶点之间的偏差.
对于施耐德算法,它将首先通过具有末端切线约束的三次贝塞尔曲线拟合数据点.如果与得到的曲线的偏差太大,则它将数据点分成两个"区域",并使用具有末端切线约束的三次贝塞尔曲线拟合每个数据区域.将重复该过程,直到对所有三次贝塞尔曲线的偏差足够小.结果,它产生一系列立方贝塞尔曲线,最多连接C1连续性(很可能它实际上只是G1).此外,由于该算法从原始数据点评估末端切线,因此数据点中的噪声将影响末端切线评估,因此影响三次贝塞尔拟合.
如果你可以花时间在曲线拟合的主题,你应该研究与B样条曲线的最小二乘拟合.这将生成具有高连续性的输出曲线(例如,对于立方B样条曲线,C2).如果你没有太多时间花在上面,那么施耐德的算法是一个很好的选择,可以在实现成本(如果你必须用特定的语言重新实现它)与产生的曲线质量之间取得平衡.