Positional Errors

Simplifying a polyline introduces shape distortion. The higher the degree of simplification the higher the amount of distortion. One way of measuring this error induced by simplification, is by looking at the location difference between the original and the simplified line.

For each original point the positional error is calculated as the perpendiculer difference between that point and the corresponding line segment of the simplification. Better performing simplification algorithms consistently produce lower positional errors.

Interface

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator compute_positional_errors2 (
    ForwardIterator original_first,
    ForwardIterator original_last,
    ForwardIterator simplified_first,
    ForwardIterator simplified_last,
    OutputIterator result,
    bool* valid=0)

For each point in the range [original_first, original_last) the squared distance to the simplification [simplified_first, simplified_last) is calculated. Each positional error is copied to the output range [result, result + (original_last - original_first)). Note that both the original and simplified polyline must be defined using the same value_type.

template <unsigned DIM, class ForwardIterator>
math::Statistics compute_positional_error_statistics (
    ForwardIterator original_first,
    ForwardIterator original_last,
    ForwardIterator simplified_first,
    ForwardIterator simplified_last,
    bool* valid=0)

Computes statistics (mean, max, sum, std) for the positional errors between the range [original_first, original_last) and its simplification the range [simplified_first, simplified_last). All statistics are stored as doubles.

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 (only for compute_positional_errors2)
3. The ForwardIterator value type is convertible to double (only for compute_positional_error_statistics)
4. The ranges [original_first, original_last) and [simplified_first, simplified_last) contain vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3
5. The ranges [original_first, original_last) and [simplified_first, simplified_last) contain a minimum of 2 vertices
6. The range [simplified_first, simplified_last) represents a simplification of the range [original_first, original_last), meaning each point in the simplification has the exact same coordinates as some point from the original polyline.

Implementation Details

The algorithm is implemented using two nested loops. The outer loop processes each line segment from the simplification. The inner loop processes each point of the original polyline, computing the perpendicular distance to the current line segment. The inner loop ends when a point exactly matches the coordinates of the end point from the line segment.

When the outer loop has finished processing all line segments from the simplification, the last point from that simplified polyline should exactly match the last processed point from the original polyline. Only if this condition holds are the calculated positional errors considered valid. This means I can only say if the results are valid after I am done computing and copying errors to the output range. So I needed some way of letting the caller know this. One option would be to throw an exception. However, I designed psimpl to not itself throw any exceptions (see documentation section The code). Instead I opted for the optional boolean argument valid.

Usage

std::vector <double> original;   // original polyline, assume not empty
std::vector <double> simplified; // simplified polyline, assume not empty
std::vector <double> errors;     // calculated errors
bool valid = false;              // indicates if the calculated errors are valid

// compute the squared positional error for
// each point of the original 2d polyline
psimpl::compute_positional_errors2 <2> (
    original.begin (), original.end (),
    simplified.begin (), simplified.end (),
    std::back_inserter (errors), &valid);

// compute positional error statistics for
// all points of the original 2d polyline
psimpl::math::Statistics stats =
    psimpl::compute_positional_error_statistics <2> (
        original.begin (), original.end (),
        simplified.begin (), simplified.end (),
        &valid);