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 vi, its perpendicular distance to this line is calculated. A new key is found at vi-1, when this distance exceeds the specified tolerance. The vertices vi and vi+1 are then used to define a new line, and the process repeats itself. The algorithm is illustrated below:

Reumann-Witkam simplification example

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

  1. DIM is not 0, where DIM represents the dimension of the polyline
  2. The ForwardIterator value type is convertible to the value type of the OutputIterator
  3. 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
  4. The range [first, last) contains at least 2 vertices
  5. 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.