Function trySimplifyDouglasPeuckerInto

Simplifies a polyline using the Douglas-Peucker algorithm.

bool trySimplifyDouglasPeuckerInto(T, R)(
  scope Polyline2View!T polyline,
  R tolerance,
  scope Point2!T[] destination,
  scope size_t[] workspace,
  out size_t written
) pure nothrow @nogc @safe
if (isGeoScalar!T && is(R == MetricScalar!T));

Geometry scalars follow the geo-d scalar domain: int, long, float, double, and real. The tolerance type must be MetricScalar!T.

The output consists only of vertices selected from the input, in their original order.

For inputs containing at least two points, the first and last points are always retained.

A section is replaced by its baseline when every intermediate point has computed Euclidean point-to-segment distance less than or equal to tolerance.

Distance decisions use the floating-point metric computation provided by tryPointSegmentDistance(). They are not exact distance predicates. Values near the tolerance threshold are therefore classified according to the computed MetricScalar!T result.

When several intermediate vertices have the same maximum computed distance, the first one in stored order is selected as the split point.

Parameters

polyline = input polyline view tolerance = finite non-negative metric tolerance destination = caller-owned output buffer workspace = caller-owned iterative traversal workspace written = number of output points on success

destination must contain at least polyline.length elements.

workspace must contain at least:

douglasPeuckerWorkspaceSize(polyline.length)

elements.

Input backing storage and destination storage must not overlap. Overlap is not detected.

Returns false when:

- tolerance is negative or non-finite; - an input coordinate is non-finite; - destination is too small; - workspace is too small; or - a required metric computation cannot be represented finitely.

On failure, written is zero. Destination contents after a failure are unspecified.

No topology-preservation guarantee is provided.

No allocation is performed. The caller-provided workspace requires O(n) elements in the worst case; beyond destination and workspace, the algorithm uses O(1) auxiliary storage.

Complexity

O(n^2) time in the worst case for n stored input points.

Example

Example using caller-owned destination and workspace storage. 

import geo;

alias P = Point2!double;
alias V = Polyline2View!double;

P[5] input = [
    P(0.0, 0.0),
    P(1.0, 0.1),
    P(2.0, 0.0),
    P(3.0, 0.1),
    P(4.0, 0.0)
];

P[5] output;
size_t[3] workspace;

size_t written;

assert(
    trySimplifyDouglasPeuckerInto(
        V(input[]),
        0.2,
        output[],
        workspace[],
        written
    )
);

assert(written == 2);
assert(output[0] == input[0]);
assert(output[1] == input[$ - 1]);