Author - Elmar de Koning Support - firstname.lastname@example.org@m.@email@example.com@m.m Website - http://psimpl.sf.net Article - http://www.codeproject.com/KB/recipes/PolylineSimplification.aspx License - MPL 1.1
'psimpl' is a c++ polyline simplification library that is generic, easy to use, and supports the following algorithms:
Simplification + Nth point - A naive algorithm that keeps only each nth point + Distance between points - Removes successive points that are clustered together + Perpendicular distance - Removes points based on their distance to the line segment defined by their left and right neighbors + Reumann-Witkam - Shifts a strip along the polyline and removes points that fall outside + Opheim - A constrained version of Reumann-Witkam + Lang - Similar to the Perpendicular distance routine, but instead of looking only at direct neighbors, an entire search region is processed + Douglas-Peucker - A classic simplification algorithm that provides an excellent approximation of the original line + A variation on the Douglas-Peucker algorithm - Slower, but yields better results at lower resolutions
Errors + positional error - Distance of each polyline point to its simplification
All the algorithms have been implemented in a single standalone C++ header using an STL-style interface that operates on input and output iterators. Polylines can be of any dimension, and defined using floating point or signed integer data types.
28-09-2010 - Initial version 23-10-2010 - Changed license from CPOL to MPL 26-10-2010 - Clarified input (type) requirements, and changed the behavior of the algorithms under invalid input 01-12-2010 - Added the nth point, perpendicular distance and Reumann-Witkam routines; moved all functions related to distance calculations to the math namespace 10-12-2010 - Fixed a bug in the perpendicular distance routine 27-02-2011 - Added Opheim simplification, and functions for computing positional errors due to simplification; renamed simplify_douglas_peucker_alt to simplify_douglas_peucker_n 18-06-2011 - Added Lang simplification; fixed divide by zero bug when using integers; fixed a bug where incorrect output iterators were returned under invalid input; fixed a bug in douglas_peucker_n where an incorrect number of points could be returned; fixed a bug in compute_positional_errors2 that required the output and input iterator types to be the same; fixed a bug in compute_positional_error_statistics where invalid statistics could be returned under questionable input; documented input iterator requirements for each algorithm; miscellaneous refactoring of most algorithms.