Each algorithm that psimpl provides, is based on a STL-style like interface with input and output iterators that iterate over vertex coordinates, e.g.: x1, y1, z1, x2, y2, z2, ... They all support n-dimensional polylines defined with either floating point or signed integer data types.
For more information about an individual algorithms, click on its name in the sidebar on the left.
psimpl consists of a single header file:
psimpl.h. This header file in turn relies only on a
handfull of standard C++ headers. No additional libraries or files
All code in
psimpl.h is organized in the following
dot <unsigned, InputIterator>
- function ...
PolylineSimplification <unsigned, InputIterator, OutputIterator>
simplify_nth_point <unsigned, ForwardIterator, OutputIterator>
All the code is contained within the root namespace
scoped_array, similar to
is a smart pointer for holding a dynamically allocated array.
is a namespace containing all functions related to computing statistics
and squared distances between various geometric entities. The class
PolylineSimplification provides the implementation for each
simplification algorithm. The top-level functions are for convenience as
they provide template type deduction for their corresponding member
psimpl itself does not throw exceptions. The reason for this is that I consider exception handling to be rather rare within C++ applications. Unlike the .NET world, a lot of developers just don't use nor even think about exception handling.
psimpl also provides a 32-bit Windows demo
application, that allows you to experiment with the different simplification
algorithms. It can generate pseudo random 2D-polylines of up to 10,000,000
vertices in various types of containers. The bounding-box of the generated
polyline is always n x n/2, where n is the amount of vertices of the generated
polyline. Use this fact to specify a proper tolerances. Comparing the various
algorithms can be done visually and by using the computed positional error
statistics. These statistics are only available when the
of the chosen container is
Internally, the generated and simplified polylines are always stored in
QVector<double>. Just before simplification, it is
converted to the selected container type. Afterwards, this temporary container
is destructed. Normally, you won't notice this, but it seems that creating
and destructing a
std::list(10.000.000) can take a rather long
time. The resulting performance measurements never include these conversion
steps. I chose this approach as it allowed me to quickly add new container
Note that the entire application is single threaded (sorry for being lazy), meaning it could go 'not responding' during a long-running simplification.
The demo application was made using Qt 4.7.3, Qt Creator 2.1.0, and Visual Studio 2008 Express. Complete source code is included.
The following algorithms are planned for upcomming versions:
- Random Point routine
- Jenks simplification
- Visvalingam-Whyatt simplification
- Zhao-Saalfeld simplification
- Computing Length errors due to simplification
- Computing Area errors due to simplification
Other things that I want to look into include:
- Make the input tolerance type a template parameter: currently the tolerance type is the same as the value type of the input iterators. This means that when using integer coordinates, all distance calculations will be performed using integers.
- Split Douglas-Peucker into two algorithms: a vanilla implementation and one that uses Radial Distance as a pre-processing step
- A seperate version that operates on point containers instead of coordinate containers
- Error calculations that works for situations where the data type of a simplification differs from the original polyline