# Algorithms

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.: x_{1}, y_{1},
z_{1}, x_{2}, y_{2}, z_{2}, ... 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.

# The code

**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
are needed!

All code in `psimpl.h`

is organized in the following
structure:

- namspace
`psimpl`

- namspace
`util`

- class
`scoped_array <T>`

- class
- namspace
`math`

- struct
`Statistics`

- function
`dot <unsigned, InputIterator>`

- function ...

- struct
- class
`PolylineSimplification <unsigned, InputIterator, OutputIterator>`

- function
`NthPoint`

- function
`...`

- function
- function
`simplify_nth_point <unsigned, ForwardIterator, OutputIterator>`

- function
`simplify_...`

- function
`compute_...`

- namspace

All the code is contained within the root namespace `psimpl`

.
The class `scoped_array`

, similar to `boost::scoped_array`

,
is a smart pointer for holding a dynamically allocated array. `math`

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
functions of `PolylineSimplification`

.

**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.

# The demo

**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 `value_type`

of the chosen container is `double`

.

Internally, the generated and simplified polylines are always stored in
a `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
types.

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.

# Upcomming versions

The following algorithms are planned for upcomming versions:

- Random Point routine
- Jenks simplification
~~Lang 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