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

Question

我正在研究一个记录笔画的应用程序,你用指点设备绘制它.

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

对于那些感兴趣的人,上面描绘的笔画坐标可以作为GitHub的要点.

事实上,Adobe Illustrator可以很好地实现我想要实现的目标.如果我在Illustrator中绘制类似的笔触(使用书法笔刷),则生成的形状将简化为我们在下面看到的内容.绘制笔划时,它看起来与我的应用程序非常相似.释放鼠标按钮后,曲线将简化为我们在此处看到的内容:

我们可以看到,笔划只有14个数据点.虽然还有其他控制点可以定义贝塞尔样条曲线的倾斜度(或者它们正在使用的任何样条曲线).在这里,我们可以看到一些控制点:

我已经研究过像Ramer-Douglas-Peucker算法这样的算法,但这些算法似乎只从输入集中删除了点.如果我没有弄错的话,我正在寻找的方法也必须在集合中引入新的点来实现所需的曲线.

我遇到过类似iPhone平滑草图绘制算法的问题.但那些似乎专注于从一小组输入点创建平滑曲线.我觉得我有相反的情况.

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;
}

结果列表将采用Start Point,Control Point 1,Control Point 2,End Point格式.