CODEWITHSUNDEEP
javascripthtmlcanvasvectorgraphics
Jake Wilson
Jake Wilson

Reputation: 91243

Algorithm to fit polygon lines to drawn pixels in Canvas?

Let's say I create a JS tool that allows freedom to draw whatever I want on a Canvas so I can make a freehand picture using the mouse, something simple like this:

enter image description here

Is there an algorithm that can be used to fit a series of poly-lines to these drawn pixels? You would obviously need to be able to choose how accurate you wanted it to be, for example the polyline could have 20 points or it could have 1000 points, making it quite accurate.

Also I'm not sure how it would work since the drawn "line" is more than 1px in width/thickness. Like if you had a big circle that was 100px diameter, how would an algorithm be able to fit a "line" to this.

Is there a particular name for this type of algorithm, for fitting points to a shape?

Upvotes: 0

Views: 665

Answers (1)

markE
markE

Reputation: 105035

Instead of trying to recompose a polyline from pixels, it would be easier to save each mousemove position as the user is drawing the line. Then those saved positions become your poly-line.

You're looking for path simplification algorithms.

The most common algorithm I've seen used it the Ramer–Douglas–Peucker algorithm which eliminates "extra" points that stray too far from an ideal line.

Mike Bostock (creator of the AMAZING d3 library) has done a nice example showing the effects of eliminating "extra" points on a path: bost.ocks.org/mike/simplify

If you're using nodeJS, Vladimir Agafonkin has a simplification algorithm that's also adapted for NodeJS: https://github.com/mourner/simplify-js

Good luck with your project!

Upvotes: 1

Related Questions