Как упрощается полилиния в Adobe Illustrator?

Я работаю над приложением, которое записывает штрихи, которые вы рисуете указательным устройством.

На изображении выше я нарисовал один такт, который содержит 453 точки данных. Моя цель состояла бы в том, чтобы резко уменьшить количество точек данных, сохраняя при этом форму первоначального хода.

Для тех, кого интересуют, координаты для инсульта, изображенные выше, доступны как gist на GitHub.

По сути, Adobe Illustrator имеет отличную реализацию того, чего я пытаюсь достичь. Если я рисую аналогичный штрих (с каллиграфической кистью) в Illustrator, получившаяся форма будет упрощена до того, что мы увидим ниже. При рисовании штриха он будет очень похож на тот, который содержится в моем приложении. Как только я отпущу кнопку мыши, кривая будет упрощена до того, что мы видим здесь:

Как мы видим, инсульт имеет только 14 точек данных. Хотя есть дополнительные контрольные точки, которые определяют наклон сплайна сплайна (или любого другого сплайна, который они используют). Здесь мы видим несколько таких контрольных точек:

Я рассмотрел такие алгоритмы, как алгоритм Рамера-Дугласа-Пиккера, но они, похоже, только удаляют точки из набора ввода. Если я не ошибаюсь, подход, который я ищу, также должен был бы ввести новые точки в набор для достижения желаемой кривой.

Я столкнулся с такими вопросами, как iPhone сглаживающий алгоритм рисования эскиза, который кажется связанным. Но они, похоже, сосредоточены на создании гладкой кривой из небольшого набора входных точек. Я чувствую, что у меня есть противоположный случай.

Ответ 1

Я столкнулся с вопросом Сглаживание рисованной кривой (на этот раз этот вопрос может быть обманом), в котором есть ответ, который предлагает использовать Ramer-Douglas -Peucker, а затем применяя аппроксимацию кривой согласно подход Philip J. Schneiders.

Быстрая адаптация предоставленного образца кода к моим методам рисования приводит к следующей кривой:

Входные данные из вопроса были уменьшены до 28 точек (которые рисуются с использованием сплайнов Безье).

Я не уверен, какой подход использует именно 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.