Adobe Illustrator中的折线简化是如何工作的？

Question

我正在开发一个应用程序，可以记录使用指向设备绘制的笔画。

在上图中，我画了一条包含453个数据点的单一笔画。我的目标是大幅减少数据点数量，同时仍保持原始笔画的形状。

对于那些感兴趣的人，上面图片中的笔画坐标可在GitHub上的gist中找到。

事实上，Adobe Illustrator具有我想要实现的很好的功能。如果我在Illustrator中使用类似的笔画（使用书法笔刷），则生成的形状将简化为下面我们看到的内容。在绘制笔画时，它会与我的应用程序中的笔画非常相似。释放鼠标按钮后，曲线将简化为以下形式：

如我们所见，该笔画只有14个数据点。尽管还有其他控制点来定义贝塞尔样条（或他们使用的任何样条）的倾斜度。这里我们可以看到其中一些控制点：

我查看了像Ramer-Douglas-Peucker算法这样的算法，但是它们似乎只从输入集中删除点。如果我没有弄错，我要寻找的方法也必须向输入集中引入新点才能实现所需的曲线。

我看到了类似iPhone光滑素描绘图算法的问题，但这些问题似乎专注于从少量输入点创建平滑曲线。我感觉我正好相反。

- Oliver Salzburg

---

前者。它实际上是一个List<Point>，其中按记录顺序填充了坐标。 - Oliver Salzburg

这可能无法回答你的问题，因为它依赖于MatLab库，但它可能会提供一些见解：http://stackoverflow.com/q/12674532/21727。 - mbeckish

请参见此处。 - mbeckish

所以听起来你知道B样条是正确的选择，只是想知道如何计算结点应该是什么？我建议研究一下使用Chebyshev多项式。 - Seth Moore

@smoore你知道是否有更易懂的参考资料，不像Chebyshev多项式的维基百科页面那样堆积着公式吗？ - Ivo Flipse

Answer 1

我遇到了一个问题(平滑手绘曲线)（这个问题可能是重复的），其中有一个答案提出使用Ramer-Douglas-Peucker算法，然后根据Philip J. Schneiders的方法进行曲线拟合。

将所提供的示例代码快速适应我的绘图方法，得到以下曲线：

来自问题的输入数据已被缩减为28个点（使用Bezier样条曲线进行绘制）。

我不确定Adobe具体使用的是哪种方法，但这个方法迄今为止对我非常有效。

适应

因此，Kris提供的代码是针对WPF编写的，并基于这方面的一些假设。为了适应我的情况（并且因为我不想调整他的代码），我编写了以下代码片段：

private List<Point> OptimizeCurve( List<Point> curve ) {
  const float tolerance = 1.5f;
  const double error    = 100.0;

  // Remember the first point in the series.
  Point startPoint = curve.First();
  // Simplify the input curve.
  List<Point> simplified = Douglas.DouglasPeuckerReduction( curve, tolerance ).ToList();
  // Create a new curve from the simplified one.
  List<System.Windows.Point> fitted = FitCurves.FitCurve( simplified.Select( p => new System.Windows.Point( p.X, p.Y ) ).ToArray(), error );
  // Convert the points back to our desired type.
  List<Point> fittedPoints = fitted.Select( p => new Point( (int)p.X, (int)p.Y ) ).ToList();
  // Add back our first point.
  fittedPoints.Insert( 0, startPoint );
  return fittedPoints;
}

生成的列表将以以下格式呈现：起始点、控制点1、控制点2、结束点。

- Oliver Salzburg

Answer 2

我曾经尝试过使用贝塞尔简化来复制Illustrator的路径简化。最像Illustrator并且效果最好的方法是使用Philip J. Schneider的Graphics Gems简化算法，但需要再加上一个步骤：排除路径上的尖锐/角度点。

对于贝塞尔路径：

在每个尖锐的贝塞尔线段处分割路径。也就是说，任何一个贝塞尔控制点不平滑/共线或者与相邻两条曲线形成“尖点”的线段都要被分割。您可以自定义阈值，确定何时将线段视为“尖锐”。180度为平滑，179.99度或170度以下为尖锐线段的阈值。

对于从原始路径中在其尖锐线段处拆分出来的每个路径，应用曲线拟合算法，然后重新连接它们。

这样可以保留尖锐边缘，同时平滑冗余线段，使曲线沿着路径的其余部分拟合。

我的实现在paper.js中，但是可以使用fitcurve算法利用相同的技术。

C：https://github.com/erich666/GraphicsGems/blob/2bab77250b8d45b4dfcb9cf58cf68f19f8268e56/gems/FitCurves.c

的意思是引用了一个名为“FitCurves.c”的文件，该文件可在上述链接中找到。

JS: https://github.com/soswow/fit-curve

- northamerican