Nth Point

The nth point routine is a naive O(n) algorithm for polyline simplification. It keeps only the first, last, and each nth point. All other points are removed. This process is illustrated below:

Nth Point simplification example

The illustration shows a polyline consisting of 8 vertices: {v1, v2 ... v8}. This polyline was simplified using n = 3. The resulting simplification consists of vertices: {v1, v4, v7, v8}.

The algorithm is extremely fast, but unfortunately, it not very good at preserving the geometric features of a line.

Interface

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_nth_point (
    ForwardIterator first,
    ForwardIterator last,
    unsigned n,
    OutputIterator result)

Applies the nth point routine to the range [first, last) using the specified value for n. 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. n 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

Algorithms don't get much simpler than this. A loop is used to copy the first point and each following nth point of the input polyline to the simplification result. After the loop, I make sure that the last point is part of the simplification.

Usage

unsigned n = 10;              // reduce to 10%
std::vector <float> polyline; // original polyline, assume not empty
std::vector <float> result;   // resulting simplified polyline
 
// simplify the 2d polyline
psimpl::simplify_nth_point <2> (
    polyline.begin (), polyline.end (),
    n, std::back_inserter (result));