Simplification does not commute with the projection

A line has a length only at a scale, and the scale a map is drawn at is a decision made long before the page. A geometry is generalised somewhere. It has to be: nothing on a page can carry the vertices a survey produced, and no screen can draw them. The question this essay is about is not whether the reduction happens but where in the sequence it happens, and the answer is that nobody writes it down.

There are two places, and both are in daily use. A pipeline can simplify the source geometry — in whatever coordinates it arrived in, which for most exchanged data is degrees of latitude and longitude — and then project the survivors. Or it can project everything and simplify on the page, in the map’s own units, which is what a renderer does because the page is where the tolerance is meaningful. The two orders are given the same instruction and they do not do the same thing.

The tolerance has to be a ground distance before anything can be compared #

Comparing two orders means giving them the same instruction, and the only instruction that means the same thing in both spaces is a distance on the ground. So the experiment is set up that way: ε is metres of ground, and it is converted into each space rather than typed into both.

For the degree-space pipeline, ε becomes a tolerance in degrees, by dividing by the length of a degree of the meridian. That is what “a tolerance in degrees” means in every piece of software that offers one, and it is where the first of the two failures comes from.

For the page-space pipeline, ε is multiplied by the projection’s own point scale factor at the middle of the region. That is more careful than what most pipelines do — a real one types a number of map units and never converts at all — and it is deliberately generous, because the argument is stronger if the page-space route is given its best chance.

The third route is the control: run the same algorithm on the ground coordinates themselves. No pipeline does this, because the geometry is never in ground coordinates; it is the answer both of the others are trying to approximate.

Degree space is stricter east–west, by exactly sec φ #

Douglas–Peucker measures the distance from a vertex to the segment standing in for it. In degree space that distance is computed as if a degree of longitude and a degree of latitude were the same length, and they are not: a degree of longitude is R cos φ, so a given east–west ground distance registers as larger in degree space by 1/cos φ.

The algorithm therefore believes east–west departures are bigger than they are, and keeps vertices it was not asked to keep.

The direction of the error is worth pausing on, because the intuition usually runs the other way. A high-latitude region looks stretched in degree space, and the instinct is that an algorithm working there will over-simplify. It under-simplifies: it treats the stretch as real distance, decides the line is wigglier than it is, and keeps the detail. The output is a file that is larger than asked for and a geometry whose east–west detail has survived while its north–south detail has not — an anisotropy in what was kept, produced by an isotropic instruction.

Page space is exact where the page is conformal #

The other order fails differently, and the difference is the site’s own subject.

A tolerance on the page is a circle: the algorithm asks whether a vertex is within ε of a line, in the page’s own metric, in every direction equally. The ground that circle stands for is the circle’s preimage, which is Tissot’s indicatrix with the axes inverted. Where the map is conformal that preimage is a circle, so the instruction the algorithm carries out is the instruction it was given. Where the map is not conformal it is an ellipse, and the effective tolerance is a different ground distance in every direction — which is distortion having a direction arriving in a place nobody expects it.

The numbers are unambiguous. On Mercator the page-space route keeps 129, 129, 129 and 135 vertices at 15°, 45°, 65° and 80° — the ground answer, until the region is large enough that one scale factor cannot describe it. On the Lambert cylindrical it keeps 171, 255, 367 and 459: more and more, and wrong at the equator, where its anisotropy is already 1.07 to 1.

Conformality is not a nicety here. It is the precise condition under which a tolerance stated on the page is a tolerance on the ground, and it is the reason a rendering pipeline that generalises in Web Mercator is doing something defensible while one that generalises in an equal-area projection is not — a sentence that inverts the usual ordering of those two maps’ reputations.

The projection on which both orders agree #

There is one map in the library on which the two pipelines keep exactly the same vertices, at every latitude, to the vertex.

The plate carrée is degree space. Its forward map is x = λ, y = φ, so a distance measured on its page is a distance measured in degrees, and the two orders are one operation. That is a real property and it is the reason the plate carrée is what pipelines fall back to when nobody chose a projection — but it buys agreement rather than correctness, and this collection has an essay about exactly that habit.

It also makes a useful control. If the two orders disagreed on the plate carrée, the disagreement measured everywhere else would be an artefact of the experiment rather than of the projections.

What was computed, and how #

The region is a curve built to have a stated fractal dimension, 400 km across, at depth 5 — 1,024 segments whose finest is 1,296 m, comfortably above the tolerance so that the algorithm has real decisions to make. It is placed on the sphere through the local tangent plane at the anchor point, so a displacement of x metres east is x metres east before any projection appears, and the ground truth is defined before the experiment starts.

Both pipelines return a subset of the original vertices — Douglas–Peucker only ever discards, never invents — so each answer can be traced back to ground coordinates by index and the two can be compared as ground polylines. The separation reported is the symmetric Hausdorff distance between them, in metres of ground.

The separation between the two orders reaches 1,883 m against a tolerance of 2,000 — 94 per cent of it. That is not larger than the tolerance, and the essay is not claiming it is. What it is, is additional to the tolerance: each route is within ε of the original in its own reckoning, and the two are nearly another ε apart from each other, so a consumer comparing two vendors’ generalisations of the same feature sees a discrepancy of about twice what either vendor’s specification suggests.

The tolerance nobody converts #

The experiment above was generous to the page-space route: ε was converted into map units using the projection’s own scale factor. Real pipelines type a number.

This is the same object as a grid metre not being a ground metre and as the written precision of a coordinate, arriving in a third place. A quantity in the projection’s units is a quantity on the ground only where the scale factor is one, and a generalisation tolerance is a quantity in the projection’s units in almost every pipeline that has one.

The practical shape of it: a dataset generalised for a world map at a single tolerance carries far more detail in high latitudes than in low ones, at a cost in bytes that is invisible in the specification and shows up in the tile sizes.

Which order a reader can detect, and which they cannot #

A file of generalised geometry does not say what was done to it. What it does carry is the vertices, and the vertices carry a trace of the order — sometimes.

The degree-space route leaves a signature that is readable: its retained vertices are denser in the east–west direction than in the north–south, by about 1/cos φ, because that is exactly what its metric mistook. Measure the ratio of retained-vertex spacing along the two axes as a function of latitude and the sec φ comes out. It is not proof, since a real boundary can be anisotropic on its own account, but it is evidence, and it is the only evidence there is.

The page-space route on a conformal projection leaves nothing to find, because it did the right thing. The page-space route on a non-conformal projection leaves the projection’s own anisotropy in the retained vertices — which means, awkwardly, that the trace of the mistake looks like the trace of the correct answer computed for a different map.

The practical advice that follows is short and is the reason this rung exists: generalise on the ground, or on a conformal projection of the region, and record which. The first is what the control in these measurements does and it is easy — the coordinates are available, and the tolerance is already in metres. The second is what a renderer does anyway. What no pipeline should do is generalise in degrees, which is what the default in most exchange formats invites.

Where the model stops #

One region, one shape. The numbers are for a boundary of one roughness at one size. A smoother boundary has fewer decisions to make and the two orders will agree more often; a rougher one will disagree more. The direction of every effect here is a property of the geometry rather than of the example — degree space is stricter east–west by sec φ whatever the shape is — but the magnitudes are the example’s.

Douglas–Peucker only. Visvalingam’s rule has an area threshold rather than a distance, so “the same tolerance in both spaces” does not even parse for it, and the comparison would need a different setup. What can be said is that its threshold is an area, so it picks up the square of the scale factor rather than the first power, and its two orders will disagree more rather than less.

And the region is small enough for one tangent plane. Four hundred kilometres at 80° is a region across which the meridian scale changes by a few parts in a thousand, so the ground truth is exact to that. A continent-sized feature has no single ground tolerance for the same reason it has no single scale, and the question of what ε even means there is not answered here.

The generalisation #

Two operations that are each defined in their own coordinates do not commute unless one of them is an isometry in the other’s metric. That is the whole of it, stated without any cartography, and the cartographic case is the vivid one because the map is exactly the non-isometry.

The pattern recurs wherever a reduction and a transformation are both applied to the same data. Resampling and reprojecting an image is the same question — and the collection has measured that one too. Rounding and unit conversion is the arithmetic version: converting to feet and rounding is not rounding and converting. Filtering and resampling a signal is the version every textbook on the subject opens with.

What cartography adds is that the transformation’s non-isometry is quantified — the scale factor and the angular deformation are tabulated for every projection in use — so the question of how far apart the two orders can get has an answer rather than an anecdote.

Who found it, and when #

The generalisation algorithms are older than the pipelines that misuse them. Douglas and Peucker published theirs in 1973 in The Canadian Cartographer, and it is one of the most-cited papers in the subject; Urs Ramer had published the same recursion in 1972 for image processing, which is why the algorithm carries three names and no consensus about the order of them.

The commutation question is younger and has mostly been discussed as an implementation detail rather than as a property. It surfaces in the standards literature as advice — generalise in the target projection — usually without the reason, and it surfaces in bug reports as complaints that a dataset “looks different” after a projection change. The observation that the plate carrée is the fixed point of the question, being the projection for which page space is degree space, is a two-line consequence that seems not to be written down anywhere, probably because nobody wants to draw attention to how often it is the projection in use.

The $\sec\varphi$ bias is a defect against the ground and a correction for one page #

The most-used pipeline in the world simplifies in degrees, and the essay’s arithmetic says that pipeline applies a tolerance that is $\sec\varphi$ tighter east–west than north–south. That is worth following through, because the bias turns out to be wrong and right in a way that explains why nobody notices it.

Against the ground it is plainly wrong. A degree of longitude is 111 kilometres at the equator and 19 kilometres at 80°, so a fixed tolerance in degrees is a ground tolerance that shrinks polewards by $\sec\varphi$: a factor of two at 60°, 5.8 at 80°, 11.5 at 85°. A global coastline simplified this way keeps roughly six times the vertex density in the Arctic that it keeps in the tropics, for no reason anybody chose. The Canadian archipelago and the Norwegian fjords come out heavy, the Indonesian coast comes out light, and the difference is a property of the storage units rather than of either coastline.

Against a plate carrée page it is exactly right, and that is the uncomfortable half. A plate carrée sheet stretches east–west by $\sec\varphi$ — that is the whole of its distortion — so a feature at 80° is drawn 5.8 times wider on the page than its ground extent warrants. A tolerance that is $\sec\varphi$ tighter on the ground in that direction is a tolerance that is constant on the page, which is precisely what a simplification for display should be.

So degree-space simplification is not a mistake in the one case where it happens to be the identity. It is a correctly-scaled page simplification for the plate carrée, and the fixed point this essay identifies is the reason.

And it is a mistake everywhere else, in whichever direction the target’s distortion runs. Feed the same degree-simplified data to a Mercator page and the polar over-retention is compounded, because Mercator stretches north–south by $\sec\varphi$ as well and the vertices that survived are already crowded. Feed it to an equal-area page and the bias runs the other way: the polar detail is retained and then squeezed into a page area that cannot show it, so the vertices are paid for and not seen.

The general statement is the one the whole rung is about. A tolerance is meaningful only in the space it is applied in, and degree space is a space — it is the plate carrée’s page. A pipeline that simplifies in degrees has therefore chosen a target projection, silently, whatever it goes on to draw with the result.

Where the ladder goes next #

Both orders in this essay honour their tolerance: no vertex either discarded is further than ε from the line drawn in its place. The next rung asks what that promise actually covers, and finds that it covers the picture and nothing else — not the enclosed area, not which side of the boundary a point is on, and not whether the curve still fails to cross itself.