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

我正在开发一个记录笔划的应用程序，您可以使用定点设备来绘制笔划。

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

对于那些感兴趣的人，上图笔画的坐标可以作为GitHub 上的要点 https://gist.github.com/oliversalzburg/5909547.

事实上，Adobe Illustrator 很好地实现了我想要实现的目标。如果我在 Illustrator 中绘制类似的笔画（使用书法画笔），所得形状将被简化为我们下面看到的样子。绘制笔划时，它看起来与我的应用程序中的笔划非常相似。一旦我释放鼠标按钮，曲线将被简化为我们在这里看到的：

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

我看过类似的算法Ramer-Douglas-Peucker 算法 http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm，但这些似乎只从输入集中删除点。如果我没有弄错的话，我正在寻找的方法还必须在集合中引入新点才能实现所需的曲线。

我遇到过类似的问题iPhone平滑草图绘制算法 https://stackoverflow.com/questions/5076622/iphone-smooth-sketch-drawing-algorithm这似乎相关。但这些似乎专注于从一小组输入点创建平滑曲线。我感觉我的情况正好相反。

我遇到了这个问题平滑手绘曲线 https://stackoverflow.com/questions/5525665/smoothing-a-hand-drawn-curve（这个问题实际上可能是一个骗局），它的答案建议使用 Ramer-Douglas-Peucker，然后根据菲利普·施奈德 (Philip J. Schneiders) 方法 http://iut-arles.univ-provence.fr/web/romain-raffin/sites/romain-raffin/IMG/pdf/PSchndeider_An_Algorithm_for_automatically_fitting_digitized_curves.pdf.

将提供的示例代码快速适应我的绘图方法会产生以下曲线：

问题的输入数据已减少到 28 个点（使用贝塞尔样条绘制）。

我不确定 Adob​​e 到底使用的是哪一种方法，但到目前为止，这种方法对我来说非常有用。

适应

So, Kris 提供的代码 https://stackoverflow.com/a/5530600/259953是为 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, 终点.