A boundary that two features share

A tolerance is a promise about the picture sets out exactly what Douglas–Peucker guarantees: no vertex it discarded is further than ε from the line drawn in its place. It says nothing about the enclosed area, nothing about which side of the boundary a point ends up, and nothing about whether the curve still fails to cross itself — and that essay measures all three failing.

Every one of those is a property of one curve. Almost no boundary in a real dataset belongs to one curve.

A county’s edge is the next county’s edge. A lake’s shore is the land’s edge. A catchment’s divide is the neighbouring catchment’s. Such a boundary is stored twice — once in each feature’s own ring — and it is therefore simplified twice, independently, by an operation that has no idea the other copy exists.

The promise a coverage makes #

A set of features that partitions a region is a coverage, and its whole promise is that every place belongs to exactly one feature. That promise is what makes an area sum add up, a point-in-polygon query return one answer, a choropleth colour each place once, and a spatial join produce one match.

Nothing in a simplification tolerance protects it.

Two places are being created here and they fail differently. A place in both features is double-counted by every area sum and returns two answers to a containment query. A place in neither falls through: it is in no county, its population is in no total, and a point that lands there gets a null.

And the sliver is not bounded by the tolerance #

The instinct is that a tolerance of ε bounds the damage: two curves each within ε of the truth are within 2ε of each other, so the sliver is a strip of width at most 2ε.

That is true and it is the wrong quantity. The strip’s area is 2ε times the length of the shared boundary, and a shared boundary between two counties is hundreds of kilometres long. The bound on the deviation is a small number and the bound on the area is not.

The erratic behaviour is the finding, not a defect of the measurement. A quantity that jumps by a factor of twenty between neighbouring tolerances cannot be estimated from ε, cannot be budgeted for, and cannot be checked by testing at one tolerance and assuming the others are similar. It is decided by a discrete choice — which vertex the recursion kept — and discrete choices do not vary smoothly.

It is worth putting the arithmetic in ground units, because the two numbers sound alike and are four orders of magnitude apart. A tolerance of ten metres on a county whose shared edge with its neighbour runs two hundred kilometres bounds the strip at twenty metres wide and four square kilometres in area. The county itself might be fifteen hundred square kilometres, so the ambiguous band is a quarter of a per cent of it — and a quarter of a per cent of a county is several thousand people, several hundred buildings, and every parcel that happens to straddle the line. The deviation bound is the number in the specification and the area is the number that decides whether anything breaks.

And the two halves of the failure hide each other from the obvious check. The membership probe above finds 22 points in both features and 19 in neither, out of the 4,788 that land inside the coverage at all. Those are nearly equal, and they have opposite signs in an area sum: an overlap adds to the total of the parts and a gap subtracts from it. A gate that compares the sum of the feature areas against the area of their union would therefore see a net of three probes where the actual disagreement is forty-one, and would report the coverage as sound to within six hundredths of a per cent.

That near-cancellation is not a coincidence of this pair. Two simplified curves that both stay within ε of the same original cross each other repeatedly, and the regions between two crossings alternate in sign by construction — one lobe on each side of the true boundary. So a shared boundary produces overlaps and gaps in roughly equal measure whenever the two simplifications are equally good, which is the normal case. The area sum is the check that costs nothing and it is the check that is systematically blinded by the geometry it is meant to detect. The band probe is the one that works, and the reason is that it counts disagreements rather than netting them.

Where the sliver comes from, and where it does not #

Two things could be causing it and they can be separated.

The two copies of the boundary might differ before anything is simplified. Two agencies tracing the same river, or one agency tracing it twice, produce curves that agree as curves and not as point sets. That is a digitising difference and it is stated as an input here, in the same units as the tolerance.

Or the simplification might diverge even from identical inputs. Two features hold the same vertex list for the shared arc, and each simplifies it inside its own ring, so the recursion sees different neighbouring geometry.

The measurement says both matter and the first matters more. With the two copies identical the sliver is small and sometimes exactly zero; with them 0.01 apart it is an order of magnitude larger.

And the reason identical copies are nearly safe is worth stating, because nobody states it. Douglas–Peucker is sub-chain independent: once the two ends of a run of vertices are anchors, what it keeps in between depends only on that run and on ε. So two features that both retain the shared arc’s endpoints simplify the arc identically, and the coverage survives. That is not part of the method’s stated guarantee, it is not true of every simplification method — Visvalingam removes the vertex whose triangle with its two neighbours is smallest, so a vertex at the junction between the shared arc and the feature’s own boundary has different neighbours in the two rings and the removal orders diverge — and a pipeline that relies on it is relying on an accident.

The fix is a data model, not an algorithm #

The bottom row of that figure is the answer and it is old.

Store the boundary once. Keep the shared arc as a single object, let both features reference it, and simplify it once. Then there is nothing for the two features to disagree about, and the sliver is exactly zero — not small, not bounded, zero — at every tolerance and every level of digitising disagreement.

That is the arc–node topological model, it was the basis of the earliest serious GIS data structures, and it fell out of fashion because storing independent polygons is simpler, parallelises better, and matches how almost every modern file format works. A shapefile has no way to say that two polygons share an edge. Neither does GeoJSON.

So the profession solved this problem, then adopted formats that cannot express the solution, and now handles it with sliver-removal tools that find thin polygons after the fact and delete them. The measurement above is what those tools are cleaning up.

What it costs to store it once #

The fix is not free and the cost is the reason it keeps being abandoned.

A feature cannot be simplified on its own. The operation needs the whole coverage, so a pipeline that generalises one county at a time has to be rewritten to generalise a county boundary network instead. That is a different program.

And a feature cannot be re-simplified without its neighbours. A tile server that simplifies each feature as it is requested — which is what almost every vector tile pipeline does — has no access to the neighbour at that moment, so the guarantee cannot be maintained at serving time. It has to be built into the data before the tiles are cut, which is where the tolerance a tile actually needs has to be decided anyway.

The same failure, three ways #

This site has now measured three ways a coverage stops being one, and they are worth putting side by side because the causes are completely different and the symptom is identical.

Inside is a claim about the edges finds that whether a point is inside a polygon depends on the plane the edges were understood to be straight in, and that between two readings of the same stored coordinates there is a band of disagreement — 29 per cent of one triangle’s area, four million square kilometres. Nothing was simplified there and no boundary was shared; the file itself is ambiguous.

Simplification does not commute with the projection finds that simplify-then-project and project-then-simplify keep different vertices — 129 on the ground against 367 in degree space at 80° — so two features handled by two pipelines diverge even if both are simplified at the same ground tolerance and both copies of the boundary were identical.

And this rung finds that two copies of one boundary, simplified independently at the same tolerance in the same pipeline, diverge anyway.

Three mechanisms, one symptom, and no way to tell them apart from the output. A sliver in a delivered dataset could be an edge-straightness convention, a pipeline-order difference, or an independent simplification, and the thin polygon on the map looks the same in all three cases. That is the practical reason sliver-removal tools exist and are used blind: the repair is cheap and the diagnosis is not available.

What a coverage-aware pipeline has to know #

The requirement, stated once, is short and it is a constraint on the whole system rather than on the simplification step.

Every shared boundary has to be identifiable as shared. Not inferable — a tool that finds shared edges by comparing coordinates has to decide a matching tolerance, and two copies that differ by a digitising error will not match exactly. It has to be recorded.

Every shared boundary has to be simplified once. Which means the simplification has to run over the boundary network, not over the features, and its output has to be reassembled into features afterwards.

And every node has to survive. A vertex where three features meet must be kept by the simplification, or the three disagree about where they meet, which is a failure the two-feature case does not have.

What the tolerance would have to be to be safe #

There is one more question worth putting numbers to, because it is the one a pipeline owner asks: how small does the tolerance have to be before the sliver stops mattering?

The answer is that it depends on what “mattering” means, and the two natural thresholds give very different answers.

If the threshold is visibility, the sliver stops mattering when it is thinner than the mark drawn over it — which the screen ladder measures as a ground width of a few tens of metres at ordinary zooms, and which is a much larger tolerance than most pipelines use. A sliver a metre wide under a two-pixel road is invisible and harmless to a reader.

If the threshold is arithmetic, it never stops mattering. An area sum double-counts the overlap whatever its width; a point-in-polygon query near the boundary returns the wrong answer whatever the width; and a spatial join produces a duplicate or a null. Those failures have no threshold at all — they are exact, they are silent, and they are the reason a coverage is a data-quality property rather than a cartographic one.

So a pipeline that produces maps can simplify carelessly and a pipeline that produces answers cannot, and the same dataset is often used for both. That is the same split the simplification tolerance essay reaches from a different direction: a tolerance is a promise about the picture, and it is being read as a promise about the geometry.

What a gate could check #

The failure is silent, which means it needs machinery rather than care, and the machinery is short.

Sum the areas of every feature and compare with the area of their union. For a coverage the two are equal; any difference is overlap, and its sign and size are the measurement above. That is one number per dataset, it needs no reference data, and it is the check nothing in a delivery pipeline currently performs.

And probe the boundary band. Sample points within a stated distance of any shared edge and count how many belong to two features or to none. That is a stronger check because it localises the failure and because it catches gaps, which an area sum reports with the opposite sign to overlaps and can be cancelled by.

Both are the same shape as the checks this collection runs on itself — an assertion that has never rejected anything proves nothing, so both need an input they must refuse, which is a coverage assembled from one copy of each shared boundary and simplified once. That case returns exactly zero, which is what makes the other numbers a measurement.

Where the model stops #

The sliver is measured by probes. A grid of two hundred by two hundred point-in-polygon tests, so the area is quantised to a cell and a sliver thinner than a cell is invisible. That makes every number here a lower bound, and it is why the smallest entries in the ladder are zero rather than very small.

The shared boundary is a Koch curve. It has structure at every scale, which is what makes the choice of which vertex to keep genuinely sensitive — and a real administrative boundary that follows a river has the same property, which is the whole subject of rung one. A boundary that is a straight line or a smooth arc gives no sliver at all, and many administrative boundaries are exactly that.

Only two features. A real coverage has hundreds, junctions where three or more meet, and boundaries that are shared along part of their length and not the rest. The junction is the harder case and it is not measured here: a node where three counties meet has to survive in three rings or all three disagree at once.

And the two copies’ disagreement is a stated input. The digitising difference is put in rather than derived, exactly as a covariance is put in elsewhere on this site, and every number scales with it.

Who found it, and when #

Slivers are the oldest known problem in digital cartography. They were the reason the arc–node model was built, they are why every serious GIS has had a sliver-removal tool since the 1970s, and the literature on topological consistency in generalisation is large — there are published algorithms for simplifying a coverage as a whole, for constrained Delaunay approaches, and for detecting and repairing the failures afterwards.

What this rung adds is the shape of the quantity. The literature treats slivers as an operational nuisance with an operational fix; measuring it shows that the nuisance is not bounded by the parameter everybody sets, that it varies by a factor of twenty between neighbouring tolerances, and that Douglas–Peucker’s near-immunity is an accident of its recursion rather than anything it promises.

The last of those is the one worth carrying away. A method’s stated guarantee and the property a pipeline actually depends on are different things, and this collection has now met that twice: the tolerance promises a deviation and is asked for an area, a containment and a simplicity; and now it is silently relied on for a topological consistency it never mentions.

Where the ladder goes next #

The ladder can now say what a tolerance covers, what it does not, what changes when the order of projecting and simplifying changes, and what happens when a boundary belongs to two features.

The question it opens is the junction. Three features meeting at a node is the case a coverage actually consists of, the node has to survive in three rings for the three to agree, and nothing about a tolerance makes a vertex survive. Whether the failure at a node is worse than the failure along an edge — and whether it is bounded by anything — is a measurement this rung sets up and does not make.