How does polyline simplification in Adobe Illustrator work?

Question

I'm working on an application that records strokes, which you paint with a pointing device.

In the image above, I've drawn a single stroke, which contains 453 data points. My goal would be to drastically reduce the amount of data points while still maintaining the shape of the original stroke.

For those interested, the coordinates for the stroke pictured above are available as a gist on GitHub.

As a matter of fact, Adobe Illustrator has a great implementation of what I'm trying to achieve. If I draw a similar stroke (with a calligraphic brush) in Illustrator, the resulting shape will be simplified to what we see below. While drawing the stroke, it will look very similar to the one in my application. Once I release the mouse button, the curve will be simplified to what we see here:

As we can see, the stroke only has 14 data points. Though there are additional control points which define the inclination of the bezier spline (or whatever spline it is they're using). Here we can see a few of those control points:

I have looked at algorithms like Ramer–Douglas–Peucker algorithm, but those seem to only remove points from the input set. If I'm not mistaken, the approach I'm looking for would also have to introduce new points into the set to achieve the desired curve.

I have come across questions like iPhone smooth sketch drawing algorithm which seem related. But those seem to focus on creating a smooth curve from a small set of input points. I feel like I have the opposite case.

Snakeroot

Are your data points stored as a sequence (preserving the order they were drawn), or a set (just a cloud of points, with no defined order)? – Martellato

@mbeckish: The former. It's actually a List<Point> which gets filled with the coordinates in the order they were recorded. – Snakeroot

This probably doesn't answer your question, because it relies on MatLab libraries, but it might provide some insight: https://mcmap.net/q/664572/-fitting-data-to-a-b-spline-in-matlab/21727. – Martellato

See also here. – Martellato

@mbeckish: Interesting. Thanks, I'll have a look – Snakeroot

So it sounds like you know B-Splines are the way to go, you're just wondering how to calculate what the knots should be? I'd look into using Chebyshev polynomials. – Formic

@smoore would you happen to know a more accessible reference that isn't a wall of formula's, like the Wikipedia page for Chebyshev polynomials? – Visually

@IvoFlipse: I can't find anything better at the moment but if I do I will post it. – Formic

Not related to Chebyshev at all, but this looks like a more useful reference: tom.cs.byu.edu/~455/bs.pdf – Formic

Well, don't know what exact algorithm used by Adobe, but this one: en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm is wide-known. Also you'll get tons of info by google "curve smooth algorithm" – Demise

@Tommi: I mentioned that algorithm (and Wikipedia article) in my question. – Snakeroot

Answer 1

I came across the question Smoothing a hand-drawn curve (which this question might actually be a dupe of), which has an answer that proposes using Ramer-Douglas-Peucker and then applying curve fitting according to Philip J. Schneiders approach.

A quick adaptation of the provided sample code to my drawing methods results in the following curve:

The input data from the question has been reduced to 28 points (which are being drawn using Bezier splines).

I'm not sure which approach exactly Adobe is using, but this one serves me extremely well so far.

Adaptation

So, the code provided by Kris is written for WPF and makes some assumptions in that regard. To work for my case (and because I didn't want to adjust his code), I wrote the following snippet:

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

The resulting list will be in the format Start Point, Control Point 1, Control Point 2, End Point.

Snakeroot

Answer 2

I've played with bezier simplification extensively in attempt to replicate Illustrator's path > simplify. What works best and most like Illustrator is Philip J. Schneider's Graphic's Gems simplification but with an additional step. That step being excluding sharp/angled points on the path.

With a bezier path:

Split the path at each sharp bezier segment. So any segment where its bezier handles are not smooth/collinear or where it creates a 'sharp point' in relation to the segment's two adjacent curves. You can set a threshold of your own defining when a segment is considered 'sharp'. 180 degrees being smooth, and anything from 179.99 or 170 degrees or less being the threshold of what is considered a sharp segment.

With each of these paths that have been split from the original at its sharp segments, apply the curve fitting algorithm to each of the paths, then rejoin them.

This retains sharp edges but smooths out redundant segments, fitting the curve along the rest of the path.

My implementation is in paper.js but the same technique could be leveraged using the fitcurve algorithm:

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

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

Ambulator