Efficient Line Smoothing and/or Simplification

Question

I am creating a painting application in Actionscript (although my question is not Actionscript related). The basic idea is to start painting when the mouse is pressed and tracking the mouse movements. What I want to achieve is:

1. reduce mouse "noise" and
2. create more smoother looking lines.

Right now, (1) is problematic because I get thousands of mouse movements within a few seconds. Due to (1) the line can look jaggy. What current idea: when the user finishes drawing the line, I store all movements in an array and reduce them (median threshold) and then use a spline algorithm to recreate a line.

Any better approaches?

Answer 1

See Efficient Curve Fitting by Sarah Frisken. Also available at the author's page.

Answer 2

(bumped into your question while looking for same, and happened to put together something of our own)

http://willowsystems.github.com/jSignature/#/about/linesmoothing/

(SEO-compatible link to same: http://willowsystems.github.com/jSignature/%2523%252Fabout%252Flinesmoothing%252F.html)

The issue you describe is two-fold. 1. You want to 'simplify' the capture data. 2. You want to draw a nice-looking line ('fit a curve') within the points.

Simplify.js quoted above is indeed good, but it only gives you points. For jSignature we wanted to a super-efficient, non-lagging curve-fitting algorithm.

See link above for explanation of one (our) approach to fitting (Bezier aka 'cubic') curves between points. It allows you to keep the line the user drew and just lag on connecting the last 2 coordinates, or you can simplify and redraw the the whole line like that.

(Our publication of the algorithm was intentional, as to establish "prior art" and preclude petentability of the combined method. This means, we don't put our own patent yoke on the algorithm and, searched hard and did not find it to be patented elsewhere. Of course there can be some patent troll out there that may find an issue with you implementing the method, but, at least, not us. So, enjoy.)

The demo link is using 4-pixel skip on mouse movement. This is crude, but OK for real-time 'simplification' of data. If you have the luxury of capturing the whole stroke and redrawing it all, certainly, use simplify.js.

Answer 3

Mike Bostock has some good examples here Line Simplification. He points out that the Douglas-Peucker algorithm is well know. However Visvalingam appears to be more effective.