Two routes to one scale

A national mapping series is not made at every scale from the source. It is cascaded: the 1:250,000 is derived from the 1:50,000 and the 1:1,000,000 from the 1:250,000, because deriving each from the source would be more work and because the intermediate products have to exist anyway.

The folklore about that is confident and it is wrong. Each step is a simplification with a tolerance, so — the reasoning goes — the departures accumulate, and a product three steps down is within the sum of the three tolerances rather than the last one.

The measurement, which comes out at zero #

A stated Koch curve of 16,385 points, simplified directly at a tolerance of 0.016, and simplified through 0.004 and 0.008 first.

Not nearly the same. The same line, vertex for vertex, to the last bit of the last coordinate. The same is true of Visvalingam’s rule on its own ladder of area thresholds: 252 vertices both ways, zero apart.

The sum-of-tolerances bound is 0.028 and the cascade does not approach it. It meets the final tolerance, exactly as the direct route does.

Why, and it is a property worth having a name for #

Both rules assign every vertex a single number, and output the vertices whose number exceeds the requested threshold.

Douglas–Peucker’s recursion, unrolled, gives each vertex the distance at which it first gets kept — the width of the band its own recursion step was tested against. Visvalingam’s gives each vertex its effective area at the moment it would have been removed. In both cases the output at threshold t is

$$\{v : \text{value}(v) \ge t\},$$

which is a sublevel set of a fixed function on the vertices. That has an immediate consequence: the outputs at two thresholds are nested, so simplifying at 0.004 and then at 0.016 selects the vertices whose value is at least 0.004 and then at least 0.016, which is the vertices whose value is at least 0.016. Composing the two takes the maximum of the thresholds and accumulates nothing whatsoever.

The property is the same one that makes progressive transmission possible — send the vertices in order of their value and every prefix is a valid simplification — and it is usually presented as a feature of the data structure rather than as a statement about composition. It is the same statement.

So a cascaded national series is exact, in the specific sense that the sheet at each scale is the sheet the source would have produced, provided nothing else happens to the intermediates.

What breaks it #

Something else always happens to the intermediates, because an intermediate product is a published sheet rather than a temporary array.

Each of the last four is an operation that does not have the sublevel-set form, and each one costs the chain its exactness. Two of them cost it more than the tolerance the product is published under, which means the cascaded sheet does not meet the specification the direct one meets.

The rounding is the interesting one #

Smoothing is an obvious suspect: it moves every vertex, it is not a selection at all, and nobody would expect it to compose with a simplification.

Rounding is not obvious, and it is unavoidable. A published product has a stated coordinate precision — a metre on a topographic sheet, a decimetre in a database — and the next stage in the chain reads the published numbers rather than the ones in memory.

Rounding to a tenth of the final tolerance moves the product by 6.5 per cent of a tolerance, which is invisible. Rounding to half of it moves the product by more than a whole tolerance, so the cascaded sheet violates the promise it is published under, from an operation that is smaller than the tolerance at every individual vertex.

The mechanism is the same one throughout: rounding moves vertices, moving a vertex changes its Douglas–Peucker value, and a changed value moves the vertex across a threshold. The per-vertex numbers were the thing that made the cascade exact, and rounding perturbs them.

What the check has to reject #

A measurement whose answer is zero needs the sharpest control the collection has, because a bug that made the cascade skip its intermediate steps would produce exactly the same zero.

Three things run alongside. The direct route’s deviation must be inside its tolerance, which is the property Douglas–Peucker guarantees and which a broken implementation would break. The cascaded route must produce the same vertex count, not merely a line at the same distance — two lines can be zero apart under a separation measure and have different vertices if the measure is sampled. And at least three of the four extra steps must break the exactness, which is the check that the comparison can see a difference at all.

The last of those is the one that earns its place. If a step as violent as a moving average had also come out at zero, the zero above would have been a fact about the comparison rather than about the composition.

The condition, stated #

A chain of operations composes exactly when every step is a filter by a per-vertex scalar that the step does not itself change.

That is a checkable property, and running it over the steps of a real production line divides them cleanly:

• Composes: Douglas–Peucker, Visvalingam, a size threshold on features — which is what selection by size is, one rung down, and it is nested for the same reason.
• Does not compose: any smoothing, any rounding, any displacement, any merge, any reprojection — and simplification does not commute with the projection is the same statement about the last of those, made two rungs down about a pair rather than a chain.

The useful form of the condition is negative. A production line is exact only if every step in it is of that form, so a single non-composing step anywhere makes the whole chain inexact, and it does not matter how small that step is: a rounding at half a tolerance is a rounding nobody would think to mention.

The bound nobody needs #

The sum-of-tolerances bound is worth a paragraph of its own, because it is the thing the folklore is actually about and it is correct.

Douglas–Peucker guarantees that its output is within the requested tolerance of its own input. Applied to a chain, that gives: the first product is within ε₁ of the source, the second within ε₂ of the first, the third within ε₃ of the second. The triangle inequality then bounds the third against the source by ε₁ + ε₂ + ε₃, and nothing in the guarantee says better.

So the reasoning is valid and the bound is true. It is simply not tight, by the whole of the gap between it and the tolerance: measured here the cascade sits at 0.0107 against a bound of 0.028 and a final tolerance of 0.016. The bound is what a guarantee can prove without knowing the rule’s structure; the zero is what the structure gives.

That is a distinction this collection meets often enough to be worth naming. The bound the net heuristic is measured against is the same shape — a bound that is correct, that is derived from less than the whole of what is known, and that is beaten by the actual construction. A measurement against a loose bound reports the bound rather than the construction.

Where the model stops #

One curve. Everything is measured on a stated Koch curve at depth seven, which is a hard case: it is self-similar, so it has structure at every scale the tolerances visit. A smoother curve would have fewer vertices near any threshold and the rounding effects would be correspondingly smaller. The zero is not affected — nesting is exact for any input.

Two rules. Douglas–Peucker and Visvalingam are the two in general use and both are nested. A rule that is not — one with a target vertex count, or one that re-fits a curve — would fail the composition test on its own, without any extra step.

And a series is not one line. A real cascade generalises a whole map: features are merged, small ones dropped, collisions displaced. The dropping is nested and the merging and displacement are not, so a real chain has non-composing steps in it whatever is done to the coordinates.

What a series actually publishes #

It is worth being concrete about where the rounding in the table comes from, because it is not a hypothetical.

A topographic database publishes coordinates to a stated resolution, and the resolution is chosen against the product’s accuracy rather than against the next derivation’s tolerance. A 1:250,000 sheet with a 125-metre displacement tolerance is commonly stored to the metre, which is 0.8 per cent of the tolerance — comfortably in the invisible band. A vector tile quantises to its own integer grid, which a vector tile has an integer grid prices at a resolution that varies with the zoom, and at the coarse end that quantisation is a substantial fraction of the feature displacement the tile is drawn to.

So the failure is not that anybody rounds carelessly. It is that the rounding is specified against one thing and consumed by another, and the two specifications are written by different people at different times. The rounding that is negligible for the sheet it was chosen for is not negligible for the sheet derived from it, and there is nothing in either specification that connects them.

That is the same shape as the datum chain that does not close: every link is within its own stated accuracy and the composition is not, because no link was specified against the composition.

What this changes about the practice #

The finding cuts two ways and both are worth stating plainly.

The cascade is not the problem people think it is. A chain of simplifications is exact, so the intuition that a derived series drifts from its source with every derivation is wrong for the operation that is doing most of the work. That is worth knowing because it is a common reason given for re-deriving from the source, which is expensive — and which a line has a length only at a scale gives a separate reason to want.

The chain’s exactness is destroyed by the cheapest thing in it. Publishing an intermediate to a stated precision — which is not an operation anybody thinks of as an operation — is enough on its own. So the practical rule is not avoid cascading; it is cascade from the unrounded intermediate, which costs nothing and is a data-management decision rather than a cartographic one.

The two together say that the thing to worry about is the plumbing rather than the algorithm, which is not where the literature’s attention is.

The generalisation #

Composition is exact when every step is a filter by a quantity none of the steps changes.

That sentence covers this rung and a good deal outside it. A pyramid of tiles composes because a tile’s contents are decided by geometry that the tiling does not move, which is a tile is drawn without its neighbours read as a composition property. A hierarchy of cells composes when the parent is the union of its children — and it does not, on a hexagonal grid, for exactly the reason that the children are not a sublevel set of anything the parent knows about. A chain of datum transformations does not close, because each one is a fit rather than a filter.

The collection’s usual finding is that two operations do not commute. This one is the other kind, and the rarer kind: two operations that do compose, exactly, with a stated condition for when they stop — which is more useful than a warning, because it says what to check rather than what to fear.

A note on why the zero is worth a rung at all, given that a null result is usually a footnote. The claim it refutes is not a fringe one: the sum-of-tolerances bound is what the algorithm’s own guarantee gives, it is what a careful reader would derive, and it is the reason given in practice for re-deriving a series from its source. Measuring that the bound is loose by a factor of three, and that the true answer is exact rather than merely better, changes a production decision rather than settling a curiosity.

Who found it, and when #

The Douglas–Peucker hierarchy has been used for progressive transmission and multi-scale storage since the 1990s, and the nesting property is explicit in that literature — it is the whole reason the technique works. Visvalingam’s effective-area ordering has the same structure and was presented that way from the start.

What is unusual is putting the property to this use. Nesting is normally invoked to justify storing one line at many scales; the statement that it also makes a cascaded production line exact is the same fact read in the other direction, and it comes with the condition attached — which is the half that matters, because it names the steps that break it.

A guarantee is a bound and a bound is not a measurement #

The defence of the null result is worth generalising, because the gap it exposes between what an algorithm guarantees and what it does is the ordinary situation rather than a special case.

An algorithm’s guarantee has to hold for every input. Douglas–Peucker promises that no discarded vertex lies further than the tolerance from the line drawn in its place, and a cascade of two such steps therefore promises the sum of the two tolerances. That is a correct statement, it is the strongest one available without knowing the data, and it is what a careful reader will derive.

A measurement is about the inputs that occur. Here the answer is not merely inside the bound but exactly zero, because the hierarchy nests and a cascaded selection lands on the same vertices as a direct one. The bound is not loose by a little; it is describing a different situation from the one that obtains.

So a production decision made from the bound is made from the wrong number. Re-deriving a series from its source rather than from the previous scale is a real cost, paid to avoid an accumulation that does not happen — and the guarantee, correctly read, cannot say that, because a guarantee never says what usually happens.

This is not an argument against proving bounds. A bound is what licenses a pipeline to run on data nobody has seen, and it is the only thing that does.

And the way to find out is always the same: compute the quantity the bound bounds, on the cases that arise, and compare. That is cheap, it is rarely done, and the reason it is rarely done is that a proved bound feels like an answer.

The condition is what makes the measurement transferable. A zero with no condition attached would be an anecdote about one dataset; a zero with the hierarchy must nest, and here is what breaks the nesting attached is a statement anybody can check against their own pipeline. The bound applies always and says little; the measurement applies conditionally and says everything, and naming the condition is the whole of the work.

A relation is not a coordinate, so nothing measured on this ladder bounds it.

Where the ladder goes next #

Eight rungs price a line’s length, its simplification, its tolerance, its shared boundaries, its population, its selection and now its chain. What none of them prices is what a generalisation does to a relation — that two features are adjacent, that one contains another, that a road crosses a river rather than running under it. Those are the properties a database is built on and the ones a coordinate tolerance says nothing about.