# 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:

The search region is constructed using a `look_ahead`

value of 4.
For each intermediate vertex, its perpendicular distance to the segment
S (v_{0}, v_{4}) 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 (v_{0}, v_{3}), all intermediate
vertices fall within the tolerance. The last vertex of the search region
v_{3} defines a new key. This process repeats itself by updating the
search region and defining a new segment S (v_{3},
v_{7}).

## 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

`DIM`

is not 0, where`DIM`

represents the dimension of the polyline- The
`BidirectionalIterator`

value type is convertible to the value type of the`OutputIterator`

- 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 - The range
`[first, last)`

contains at least 2 vertices `tol`

is not 0`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 (v_{i}, v_{i+n}) may have
to be reduced to S (v_{i}, v_{i+(n-1)}). The easiest way to do this
is by decrementing the iterator pointing to v_{i+n}. Although
it would be possible to just increment a copy of v_{i} 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.