Scribble Path Smoothing

Some devices don’t report precise touch point readings. This results in noisy(i.e., not smooth) scribble paths. We need to clean up the scribble data.

Firstly, we use the Douglas-Peucker path simplification algorithm to reduce the number of points in a scribble. Douglas-Peucker is able to remove about 80% of points while retaining shape of scribble. It works by removing any points that fall near a line between some other two points. Then when drawing a path with the reduced set of points, a shape very similar to the original scribble path is reproduced.

Secondly, we use spline interpolation to smooth scribble edges which makes them less jagged. Spline interpolation creates cubic bezier curves between points. Cubic bezier curves are defined by two end points and two control points. Each control point is ‘attached’ to an end point. So for a list of scribble points, each scribble point(i.e., end point) is associated with two control points(one control point is on the curve to the previous scribble point, and one control point is on the curve to the next scribble point). A control point determines the direction the curve leaves the end point at. For our purposes, cubic bezier control points are determined from adjacent scribble points. The line between the two control points adjacent to a scribble point should be parallel to the line between the two scribble points adjacent to the scribble point of interest. This allows the independent, adjacent curves to appear smoothly continuous.