c# - Adobe Illustrator 中的多段线简化是如何工作的？

Question

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

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

对于那些感兴趣的人，上图中笔划的坐标可以作为 gist on GitHub 获得。 .

事实上，Adobe Illustrator 很好地实现了我想要实现的目标。如果我在 Illustrator 中绘制类似的笔触(使用书法画笔)，生成的形状将简化为我们在下面看到的形状。绘制笔划时，它看起来与我的应用程序中的非常相似。松开鼠标按钮后，曲线将简化为我们在此处看到的样子:

正如我们所见，笔划只有 14 个数据点。尽管还有其他控制点可以定义贝塞尔样条曲线的倾斜度(或他们正在使用的任何样条曲线)。在这里我们可以看到其中的几个控制点:

我看过像 Ramer–Douglas–Peucker algorithm 这样的算法，但那些似乎只从输入集中删除点。如果我没记错的话，我正在寻找的方法还必须在集合中引入新点以实现所需的曲线。

我遇到过类似 iPhone smooth sketch drawing algorithm 的问题这似乎相关。但是那些似乎专注于从一小组输入点创建平滑曲线。我觉得我的情况正好相反。

Answer 1

我遇到了这个问题 Smoothing a hand-drawn curve (这个问题实际上可能是一个骗局)，它有一个建议使用 Ramer-Douglas-Peucker 然后根据 Philip J. Schneiders approach 应用曲线拟合的答案。 .

根据我的绘图方法快速调整提供的示例代码会产生以下曲线:

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

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

适应

所以，the code provided by 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、终点.