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:
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.
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
result + m * DIM.
Input (Type) Requirements
DIMis not 0, where
DIMrepresents the dimension of the polyline
ForwardIteratorvalue type is convertible to the value type of the
- The range
[first, last)contains vertex coordinates in multiples of
DIM, e.g.: x, y, z, x, y, z, x, y, z when
- The range
[first, last)contains at least 2 vertices
tolis 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
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.
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.