# Reumann-Witkam

Instead of using a point-to-point (radial) distance tolerance as a rejection
criterion (see **Radial Distance**), the O(n)
**Reumann-Witkam** routine uses a point-to-line (perpendicular)
distance tolerance. It defines a line through the first two vertices of the original
polyline. For each successive vertex v_{i}, its perpendicular distance to
this line is calculated. A new key is found at v_{i-1}, when this distance
exceeds the specified tolerance. The vertices v_{i} and v_{i+1} are
then used to define a new line, and the process repeats itself. The algorithm is
illustrated below:

The red strip is constructed from the specified tolerance and a line through the first two vertices of the polyline. The third vertex does not lie within the strip, meaning the second vertex is a key. A new strip is defined using a line through the second and third vertices. The last vertex that is still contained within this strip is considered the next key. All other contained vertices are removed. This process is repeated until a strip is constructed that contains the last vertex of the original polyline.

## Interface

template <unsigned DIM, class ForwardIterator, class OutputIterator> OutputIterator simplify_reumann_witkam ( ForwardIterator first, ForwardIterator last, typename std::iterator_traits <ForwardIterator>::value_type tol, OutputIterator result)

Applies the **Reumann-Witkam** routine to the range
`[first, last)`

using the specified perpendicular distance tolerance
`tol`

. The resulting simplified polyline is copied to the output range
`[result, result + m * DIM)`

, where `m`

is the number of
vertices of the simplified polyline. The return value is the end of the output
range: `result + m * DIM`

.

## Input (Type) Requirements

`DIM`

is not 0, where`DIM`

represents the dimension of the polyline- The
`ForwardIterator`

value type is convertible to the value type of the`OutputIterator`

- The range
`[first, last)`

contains vertex coordinates in multiples of`DIM`

, e.g.: x, y, z, x, y, z, x, y, z when`DIM`

= 3 - The range
`[first, last)`

contains at least 2 vertices `tol`

is not 0

In case these requirements are not met, the entire input range
`[first, last)`

is copied to the output range
`[result, result + (last - first))`

, **or** compile errors may
occur.

## Implementation Details

Nothing special, just a single loop over all vertices that calculates their distance against the current strip. As soon as a key is found, it is copied to the output range and the current strip is updated.

## Usage

float tolerance = 10.f; // point-to-line distance tolerance std::vector <float> polyline; // original polyline, assume not empty std::vector <double> result; // resulting simplified polyline // simplify the 4d polyline psimpl::simplify_reumann_witkam <4> ( polyline.begin (), polyline.end (), tolerance, std::back_inserter (result));

This example demonstrates that the value type of the input and output iterators do not have to be the same.