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

Question

我正在寻找一种用于简化和平滑 2D 轨迹的路径的算法。所以我有一个二维点的有序列表。这些要点应该简化，例如使用 Ramer-Douglas-Peucker 算法。但输出必须是平滑的，因此生成的路径应该由贝塞尔曲线或样条曲线构建。 Ramer-Douglas-Peucker 算法是否有任何修改可以处理这个问题？

我在 paper.js 库中找到了一个路径简化算法，它正是我正在搜索的：http://paperjs.org/examples/path-simplification/ 但是我无法从未记录的 [=16] 中理解该算法=] 源代码.

Answer 1

您要执行的操作称为 Curve Fitting.

虽然 Ramer-Douglas-Peucker 算法基本上通过移除不必要的点来平滑 'noise' 多段线 - 曲线拟合算法将通过这些点拟合贝塞尔曲线。

Here is a pretty nice example on Youtube and here 是描述算法本身的原始论文。

至于 Paper.js 示例：

This 是该特定功能的 Github link 你提到了，这是很好的评论。研究论文认为使用的是this.
此外 here 是关于邮件列表的非常简短的讨论使用了什么，没有使用什么（显然使用了 Ramer-Douglas-Peucker 但后来删除了)

Answer 2

您想做的工作属于"curve fitting"的范畴。曲线拟合算法有很多种，但几乎所有的曲线拟合算法都可以分为两类：插值法和近似法。插值算法生成的曲线恰好通过所有数据点，而近似算法生成的曲线靠近数据点。当然，混合算法也存在。

既然你想让数据点平滑，你应该寻找近似算法。你提到的两个算法：RDP算法和施耐德算法（Paper.js中的那个），都是近似算法。所以，基本上你可以使用它们中的任何一个。对于RDP，在获得简化路径后，可以通过简化路径的顶点创建Catmull Rom样条或Overhauser样条以获得平滑曲线。但是，您无法直接控制生成的样条曲线与原始路径中的顶点之间的偏差。

对于 Schneider 算法，它将首先通过具有端切线约束的三次贝塞尔曲线拟合数据点。如果与结果曲线的偏差太大，那么它会将数据点分成两个 "regions" 并用具有端切线约束的三次贝塞尔曲线拟合每个数据区域。将重复此过程，直到所有三次贝塞尔曲线的偏差都足够小。结果，它产生了一系列最多与 C1 连续性相连的三次贝塞尔曲线（很可能实际上只是 G1）。此外，由于该算法从原始数据点评估端切线，数据点中的噪声将影响端切线评估，从而影响三次贝塞尔曲线拟合。

如果你能花时间在曲线拟合的主题上，你应该研究一下 B 样条曲线的最小二乘拟合。这将生成具有高连续性的输出曲线（例如，三次 B 样条曲线的 C2）。如果你没有太多时间可以花，那么施耐德的算法是一个很好的选择，它在实现成本（如果你必须用特定语言重新实现它）和结果曲线的质量之间取得平衡

Answer 3

就我而言，我发现 Catmull-Rom Splines 最容易应用。 Smooth Paths Using Catmull-Rom Splines 来自 Mika 的 Coding Bits 的文章非常有帮助。我用它在我的 Unity3D 项目中用 C# 实现样条插值脚本。这是脚本：

public static Vector2 CatmullRomInterpolation(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float t, float alpha = .5f, float tension = 0)
{
    float t01 = Mathf.Pow(Vector2.Distance(p0, p1), alpha);
    float t12 = Mathf.Pow(Vector2.Distance(p1, p2), alpha);
    float t23 = Mathf.Pow(Vector2.Distance(p2, p3), alpha);
    Vector2 m1 = (1.0f - tension) * (p2 - p1 + t12 * ((p1 - p0) / t01 - (p2 - p0) / (t01 + t12)));
    Vector2 m2 = (1.0f - tension) * (p2 - p1 + t12 * ((p3 - p2) / t23 - (p3 - p1) / (t12 + t23)));
    return (2.0f * (p1 - p2) + m1 + m2) * Mathf.Pow(t, 3) + (-3.0f * (p1 - p2) - m1 - m1 - m2) * Mathf.Pow(t, 2) + m1 * t + p1;
}

p0 和 p3 是控制点，它们应该不同于 p1 和 p2，它们是路径中的起点和终点。

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

Algorithm for path simplification and smoothing of 2D trajectories

algorithm

bezier

computational-geometry