Lang

The Lang simplification algorithm defines a fixed size search-region. The first and last points of that search region form a segment. This segment is used to calculate the perpendicular distance to each intermediate point. If any calculated distance is larger than the specified tolerance, the search region will be shrunk by excluding its last point. This process will continue untill all calculated distances fall below the specified tolerance, or when there are no more intermediate points. All intermediate points are removed and a new search region is defined starting at the last point from old search region. This process is illustrated below:

Lang simplification example

The search region is constructed using a look_ahead value of 4. For each intermediate vertex, its perpendicular distance to the segment S (v0, v4) is calculated. Since at least one distance is greater than the tolerance, the search region is reduced by one vertex. After recalculating the distances to S (v0, v3), all intermediate vertices fall within the tolerance. The last vertex of the search region v3 defines a new key. This process repeats itself by updating the search region and defining a new segment S (v3, v7).

Interface

template <unsigned DIM, class BidirectionalIterator, class OutputIterator>
OutputIterator simplify_lang (
    BidirectionalIterator first,
    BidirectionalIterator last,
    typename std::iterator_traits <BidirectionalIterator>::value_type tol,
    unsigned look_ahead,
    OutputIterator result)

Applies the Lang simplification algorithm to the range [first, last) using the specified perpendicular distance tolerance and look ahead values. 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 BidirectionalIterator 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
  6. look_ahead 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

The Lang simplification algorithm has the requirement that its input iterators model the concept of a bidirectional iterator. The reason for this is that a search region S (vi, vi+n) may have to be reduced to S (vi, vi+(n-1)). The easiest way to do this is by decrementing the iterator pointing to vi+n. Although it would be possible to just increment a copy of vi n-1 times, it requires extra bookkeeping. It also complicates the code somewhat, as we would only want to take this approach for forward iterators.

Usage

float tolerance = 10.f;       // point-to-segment distance tolerance
unsigned look_ahead = 7;      // search region size
std::vector <float> polyline; // original polyline, assume not empty
std::vector <double> result;  // resulting simplified polyline

// simplify the 5d polyline
psimpl::simplify_lang <5> (
    polyline.begin (), polyline.end (),
    tolerance, look_ahead,
    std::back_inserter (result));

Using a look_ahead value of 7, means that the resulting simplification will always contain at least 1/7 or 14% of the original points. The look_ahead value constrains the simplification.