Radial Distance is a brute force O(n) algorithm for polyline simplification. It reduces successive vertices that are clustered too closely to a single vertex, called a key. The resulting keys form the simplified polyline. This process is illustrated below:
The first and last vertices are always part of the simplification, and are thus marked as keys. Starting at the first key (the first vertex), the algorithm walks along the polyline. All consecutive vertices that fall within a specified distance tolerance from that key are removed. The first encountered vertex that lies further away than the tolerance is marked as a key. Starting from this new key, the algorithm will start walking again and repeat this process, until it reaches the final key (the last vertex).
template <unsigned DIM, class ForwardIterator, class OutputIterator> OutputIterator simplify_radial_distance ( ForwardIterator first, ForwardIterator last, typename std::iterator_traits <ForwardIterator>::value_type tol, OutputIterator result)
Applies the Radial Distance routine to the range
[first, last) using the specified radial distance tolerance
tol. The resulting simplified polyline is copied to the output
[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
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 point-point distances. As soon as a key is found, it is copied to the output range.
float tolerance = 10.f; // point-to-point distance tolerance std::vector <float> polyline; // original polyline, assume not empty std::vector <float> result; // resulting simplified polyline // simplify the 2d polyline psimpl::simplify_radial_distance <2> ( polyline.begin (), polyline.end (), tolerance, std::back_inserter (result));
Note that the results container does not need to match the polyline container.
You could, for instance, use a C-style