Concept

Douglas peucker — where it appears

The recursive line-simplification rule that keeps the point furthest from a chord and discards the rest. It guarantees that no discarded vertex lies further than the tolerance from the line drawn in its place, and it guarantees nothing about length, area or self-intersection.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

Two features, one shared boundary, simplified apart. Two neighbouring areas whose common boundary is a curve with structure at every scale — a river or a ridge, in effect — each stored with its own copy of that boundary and each simplified on its own at a tolerance of 0.01. The faint outlines are the originals and the solid ones what came back. The two copies of the shared boundary were within 0.01 of each other before the simplification and are not afterwards: 144 probe cells of 40000 now lie inside both features and 0 inside neither.

A boundary that two features share

Three rungs simplify one curve and price what a tolerance covers. Almost no boundary in a real dataset belongs to one feature: a county's edge is the next county's edge, it is stored twice, and it is simplified twice. What opens between the two answers is a region belonging to both features or to neither, and its area is not bounded by the tolerance.

applied · Generalise

Twenty-four versions of one shape, and not one of them gains area. The same closed boundary rotated twenty-four times and simplified at the same tolerance. If the area error were noise the values would straddle zero and their mean would fall towards it; they do not. Every one is negative, the mean is -0.4644 per cent, and the mean is 71 standard errors from zero. A bias of that size cannot be removed by averaging over more boundaries, which is the only defence anybody has against a rounding error.

A thousand features are wrong in the same direction

The area a simplification costs is unpredictable in sign for one feature. Over a population it is not: twenty-four presentations of one shape all lose area, the mean is seventy standard errors below zero, and no amount of aggregation removes it.

applied · Generalise

How far the two routes end up apart. The distance between a line simplified directly at the final tolerance and the same line simplified through two intermediate products, as a multiple of the final tolerance, with a stated extra step applied to each intermediate. With nothing in between the two are the same line to the last bit, because Douglas–Peucker's outputs are nested. Rounding the intermediate to half the tolerance, smoothing it for legibility, or running it through a moving average each break that, and the last of them puts the final product 0.142 away from where a direct route would have put it — nine times the tolerance the product is published under.

Two routes to one scale

A national series is cascaded — the million is derived from the quarter-million, which was derived from the fifty — and the folklore is that the errors accumulate. They do not: Douglas–Peucker and Visvalingam both cascade to the same line the direct route produces, bit for bit, because both output a sublevel set of a per-vertex number. What breaks it is anything else in the chain, and a moving average puts the product nine tolerances away.

applied · Generalise

Named alongside it

The objects these essays reach for when they reach for this one.

Generalisation Tolerance Area Simplification Verification Aggregation Bias Closed form Composition Containment Convention Convergence

All concepts