Simplifying a Polyline - Example
While reading the last section, you may have wondered just how you determine how far a point is from a line. I struggled a bit with how much detail to go into in this tutorial. My solution uses vector math to determine the distance and to determine the angle that is create by three points. I decided against discussing the math behind my implementation because it would have either turned this tutorial into a vector math tutorial (which might be nice to have on this site) or I might not have covered the math deeply enough potentially causing confusion. It is my hope that the example in this section will fill in the gaps not covered in this tutorial. However, if there is a desire to see a tutorial on vector math on this site, please feel free to let me know.
To use the example, simply draw a shape by pressing the mouse button and dragging around. Release the mouse button when you are done and then the curve will be simplified.
Each vertex on the drawn curve is displayed using SVG markers. The vertices can be quite close together, so I had to keep the markers small so they wouldn't interfere with the appearance of the curve. You will definitely need to zoom-in on the curve to see the detail.
The light blue polyline shows the current tolerance within which the simplified polyline must be constrained. The slightly transparent grey line shows the simplified polyline and allows you to see the underlying vertices that were dropped from the original polyline. Be sure to zoom-in and pan around the curve to convince yourself that the simplified polyline does indeed stay within the tolerance.
The slider is used to dynamically adjust the tolerance. This allows you to see the effects different tolerances have on the simplified curve. Also, the number of points in the original polyline and the number of points in the simplified polyline are displayed above the slider. You can see the effect on point count as you adjust the tolerance value. I find it interesting that a value or zero still reduces the point count even though the two polylines will appear to be identical. So, it seems that this approach would be useful as a first step for reducing the memory footprint of a hand-drawn image.
Double-click-drag to draw a new shape. There's no need to reset your current zoom level and panning as the current view will be reset before drawing begins.
Click the image below to open the example in another window.
Many drawing applications will smooth a hand-drawn curve to reduce some of the jaggedness that's inherent when drawing with the mouse. This algorithm would be a good first step in a smoothing algorithm as it reduces the number of points needing processing.
Special thanks go out to Doug Schepers. He and I have been discussing this topic and curve smoothing off and on for over a year now (yikes!). Unfortunately, it has taken me that long to get this tutorial online, but I do hope that others will benefit from the fruit of our discussions.