Opheim

The O(n) Opheim routine is very similar to the Reumann-Witkam routine, and can be seen as a constrained version of that Reumann-Witkam routine. Opheim uses both a minimum and a maximum distance tolerance to constrain the search area. For each successive vertex v_i, its radial distance to the current key v_key (initially v₀) is calculated. The last point within the minimum distance tolerance is used to define a ray R (v_key, v_i). If no such v_i exists, the ray is defined as R(v_key, v_key+1). For each successive vertex v_j beyond v_i its perpendicular distance to the ray R is calculated. A new key is found at v_j-1, when this distance exceeds the minimum tolerance Or when the radial distance between v_j and the v_key exceeds the maximum tolerance. After a new key is found, the process repeats itself.

The Opheim simplification process is illustrated above. Notice how the search area is constrained by a minimum and a maximum tolerance. As a result, during the second step, only a single point is removed. The Reumann-Witkam routine, which uses an infinite or unconstrained search area, would have removed two points.

Interface

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_opheim (
    ForwardIterator first,
    ForwardIterator last,
    typename std::iterator_traits <ForwardIterator>::value_type minTol,
    typename std::iterator_traits <ForwardIterator>::value_type maxTol,
    OutputIterator result)

Applies the Opheim routine to the range [first, last) using the specified distance tolerances minTol and maxTol. 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. minTol is not 0
6. maxTol 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

All the articles that I found mentioning or discussing the Opheim algorithm, failed to explain how to define the ray that controls the direction of the search area. As far as I can tell, there are three possible ways of determining this ray R(v_key, v_i), where v_key is the current key.

1. The Reumann-Witkam way: i = key + 1
2. The first point outside: key < i and v_i is the first point that falls outside the minimum radial distance tolerance
3. The last point inside: key < i and v_i is the last point that falls inside the minimum radial distance tolerance; if no such v_i exists, fall back to the Reumann-Witkam way

I compared these three approaches using postitional error statistics and found that 'the first point outside' approach, most of the time, produces slightly better results than the 'Reumann-Witkam' approach. Furthermore, there did not seem to be any real difference between the 'last point inside' and 'the first point outside' approaches. I ended up choosing the 'last point inside' approach, because it was a better fit for the loop that I had already implemented.

Usage

float minimum = 10.f;          // minimum distance tolerance
float maximum = 100.f;         // maximum distance tolerance
std::vector <double> polyline; // original polyline, assume not empty
std::vector <double> result;   // resulting simplified polyline

// simplify the 4d polyline
psimpl::simplify_opheim <4> (
    polyline.begin (), polyline.end (),
    minimum, maximum, std::back_inserter (result));