Cells that are rectangles in no coordinate

The previous rung moved a field from one cell scheme to another and back, and found the two halves of the answer that this ladder had been heading towards: the total is conserved exactly and nothing else is, with a per-cell error of 39 per cent of the field’s own standard deviation after one round trip — which is what an address being an area costs once the areas are different areas.

It also recorded a limitation, in one sentence, and the sentence matters more than it looks. Both schemes in that measurement have cells that are longitude–latitude rectangles. Their overlaps are therefore rectangles too, and a rectangle’s area on the sphere has the closed form R²Δλ(sin φ₂ − sin φ₁) that this collection has used since its decision not to buy a coastline.

The schemes anybody argues about are not like that, because a cell system trades area for shape and the ones that win the trade are the ones whose cells are not rectangles. HEALPix, H3, the equal-area cube and the geodesic grids have cells that are rectangles in no coordinate system on the sphere, and computing their overlaps needs a clipper.

Clipping against planes, not against lines #

The clipper is Sutherland–Hodgman with the half-planes generalised, and the generalisation is the trick that makes one routine handle both kinds of boundary.

Every boundary this needs is the intersection of the sphere with a plane, p · n = c. A meridian is such an intersection with c = 0. A cube cell’s edge, being a great circle, is one with c = 0. A parallel at latitude φ is one with n = ẑ and c = sin φ — a plane that does not pass through the origin, which is exactly what makes a parallel not a great circle.

So the clip is: keep the vertices on the positive side, and where an edge crosses, find the crossing. That last step is the only part with any content. The arc from a to b lies in the plane through the origin with normal m = a × b, so a point on that great circle satisfies three conditions — p · m = 0, p · n = c, and |p| = 1. Working in the two-dimensional basis orthogonal to m, the first is automatic, the second is a line and the third is the unit circle, and a line meets a circle in a closed form.

That is exact. No boundary is approximated by a chain of short segments, and no area is estimated by sampling.

Why a parallel is the awkward one #

The asymmetry between the two schemes’ boundaries is the whole reason a general clipper was needed, and it is worth naming because it inverts the usual intuition about which grid is simple.

A longitude–latitude grid is universally described as the simple case. Its cells are rectangles in the coordinates, its areas have a closed form, and every piece of software can index it in two lines. But two of its four edges are small circles, and a small circle is not a geodesic: it is the intersection of the sphere with a plane that misses the centre.

A gnomonic cube cell, described as the complicated case, has four edges that are all great circles. Every one of them is a geodesic, every one of them is the intersection of the sphere with a plane through the origin, and the polygon they bound is a spherical polygon in the textbook sense with a spherical excess that Girard’s theorem gives directly.

So by the criterion that matters for clipping, the cube is the simple scheme and the lat/lon grid is not — and the reason the lat/lon grid has always looked simpler is that nobody clips it against anything. It is simple to index and awkward to intersect, and the two properties get conflated because the indexing is what a user meets.

The generalisation to planes at an offset is what dissolves the asymmetry. Once a boundary is any plane section of the sphere, a meridian, a parallel and a cube edge are the same kind of object with different values of one constant, and the clipper does not need to know which it is looking at.

The clipper checks itself against the sphere #

The check that matters here has nothing to do with the essay’s argument, which is what makes it a check.

Every overlap the clipper computes is a piece of the sphere. The pieces must therefore add to the sphere — one gnomonic cube of 96 cells against a longitude–latitude grid of 128, twelve thousand two hundred and eighty-eight overlaps, most of them empty and the rest small polygons of four to eight vertices, summing to 4πR².

They do, to fourteen significant figures.

If an arc–plane root were being taken on the wrong side, or a fan triangle in the area formula were getting the wrong sign, or a vertex on a boundary were being counted twice, the pieces would not add up. Every other number in this essay would then be a measurement of that mistake, drawn convincingly. The coverage check is one line and it is the only reason to believe any of the rest — the same role the assertions that must reject play everywhere else in this collection.

What the hard geometry costs #

Two numbers, and each of them says something the previous rung could not.

The conservation is no longer exact to machine precision. It is 1.7 × 10⁻¹², which is four orders of magnitude worse than the rectangular case’s 2.2 × 10⁻¹⁶. That is not a defect: in the rectangular case every overlap area is a closed form evaluated once, and here every one is the output of a clip and a spherical excess, so the conservation is as good as the arithmetic and no better. The distinction is worth keeping because a validation suite that tests conservation to 10⁻¹⁵ will pass one scheme and fail the other for reasons that have nothing to do with either scheme.

The per-cell error is smaller, not larger — 18.4 per cent against 39. That is the opposite of what the shortfall predicted, and the reason is the cell counts rather than the geometry: 96 cube cells against 128 rectangles is a gentler resampling than the 648-against-450 of the earlier measurement, because the ratio of cell sizes is closer to one. The honest statement is that this measurement does not isolate the effect of the hard geometry, because changing the geometry changed the cell counts too.

What can be said is that the round trip through a genuinely non-rectangular pair loses a fifth of the field’s variation per cell while conserving the total to twelve figures — and that the quantity a validation check looks at is precisely the one that cannot detect any of it. That is the previous rung’s finding, surviving the removal of its easiest assumption.

Where the four orders of magnitude went #

The conservation falling from 2.2 × 10⁻¹⁶ to 1.7 × 10⁻¹² is reported as as good as the arithmetic and no better, and the factor of eight thousand between them can be accounted for rather than shrugged at, which turns a caveat into a rule for setting a tolerance.

It splits into two.

Accumulation over the overlaps. The rectangular case evaluates a handful of closed forms; the clipped case sums twelve thousand two hundred and eighty-eight independently computed pieces. Rounding errors that are independent add in quadrature, so the total inherits a factor of about √12,288 = 111.

The length of the arithmetic chain per overlap. A rectangle’s area is one expression. A clipped polygon’s is a cross product, a plane–arc root, a membership test, a fan of spherical triangles and an arctangent apiece — a dozen operations, each contributing its own rounding, and the intermediate quantities are differences of nearly equal numbers where two boundaries nearly coincide. That is worth another factor of about seventy.

Multiplied, 111 × 70 ≈ 7,800, against a measured 7,700. The degradation is bookkeeping rather than a defect in the clipper, and the two factors have different behaviour under refinement, which is the part a validation suite needs.

The chain length is fixed and the accumulation is not. Refining both schemes by one level quadruples the cell counts and multiplies the overlap count by sixteen, so the conservation residual grows by four. Two more levels and it is at 10⁻¹⁰; four more and it is at 10⁻⁸.

That gives the tolerance rule the essay’s own generalisation asks for and does not supply: a conservation tolerance for a clipped rebinning has to scale as the square root of the overlap count, which is proportional to the product of the two schemes’ cell counts. A suite written with a fixed absolute tolerance against a level-2 pair will pass, will pass at level 3, and will start failing at level 5 or 6 — on an implementation that has not changed and is not wrong.

And it decides which of the two questions the tolerance answers, which is the choice the generalisation says has to be made explicitly. A tolerance set as k√Nε is a statement about the algorithm and travels between geometries; a fixed 10⁻¹⁵ is a statement about the rectangular geometry and fails everywhere else. The first needs the overlap count, which the rebinning already computes, so it costs nothing to write.

What was computed, and how #

The cube cells’ four corners are computed from the solid’s own geometry and the gnomonic projection onto each face; the lon/lat cells are given to the clipper as four half-spaces rather than as a vertex list, because their north and south edges are not arcs and cannot be given as one.

Areas come from a fan of spherical triangles by the Van Oosterom–Strackee formula, which is the numerically stable signed form of Girard’s theorem. Signed matters: a fan that leaves the polygon and comes back cancels correctly, which a naive sum of unsigned triangle areas does not.

The field is a stated function of longitude and latitude, sampled at each cell’s centre, and the rebinning is area-weighted in both directions — each target cell gets the overlap-weighted mean of the sources it intersects. That is the operator that conserves the integral, and conserving the integral is the entire justification for using it.

Neither of those says why anybody moves a field between two schemes in the first place, and the answer is not that somebody prefers a different mesh.

One scheme is deliberately out of reach here, and it is the one most readers would reach for. The equal-area cube gives every cell the same area, which is the whole reason a cube scheme is used at all, and its cell edges are not great circles — so the exact clipper this rung is built on cannot cut against them. The trade is therefore in the direction opposite to the one a user would make: the scheme that can be clipped exactly is the scheme whose cells vary in area, and the scheme worth holding a field on is the one that has to be rebinned approximately. Saying so is not a caveat at the end. It is the reason the residuals below are quoted for the gnomonic cube and not for the mesh anybody would rather have.

The same arithmetic reads the coverage check in the other direction, which is worth noticing because the two residuals are not the same size. The coverage sums the same twelve thousand pieces and comes back at 6.6 × 10⁻¹⁵ — two orders of magnitude better than the round trip’s 1.7 × 10⁻¹². The difference is that the coverage adds the areas once and the round trip carries them through a weighting, a division and a second weighting, so the round trip’s chain is three times as long. The strongest check is also the shortest computation, which is not a coincidence and is a good reason to prefer it.

Where the model stops #

The gnomonic cube, not the equal-area cube. The clipper is exact because the cube cells’ edges are great circles, and they are great circles because the face projection is gnomonic. An equal-area cube’s cell edges are not great circles, and clipping against them exactly would need a different construction — probably a parameterised curve intersected numerically, which is a sampled answer with a stated convergence rather than a closed form.

HEALPix and H3 are named and not measured. HEALPix’s cells are bounded by curves in (λ, sin φ) that are straight there and not on the sphere; H3’s are spherical polygons whose vertices are the duals of a subdivided icosahedron, and whose edges are great circles — so H3 is actually in reach of this clipper and was not tried, for time rather than for principle.

And the cell counts confound the comparison, as the essay says above. Isolating the effect of the geometry needs two pairs of schemes with matched cell counts and different overlap shapes, which is a straightforward measurement and is not this one.

The one number that is not a measurement #

Among everything reported here, the coverage figure deserves separate treatment, because it is the only one that is not about cell schemes at all.

One point zero zero zero zero zero zero zero zero zero zero zero zero six six, to the digits it comes out at. Twelve thousand two hundred and eighty-eight clipped polygons, most of them empty, the rest between three and eight vertices, summing to the area of the sphere.

It says nothing about rebinning, nothing about conservation and nothing about the schemes. What it says is that a chain of geometric operations — a plane section, a root selection, an arc-membership test, a signed spherical excess, a fan triangulation — is doing what it claims, and it says so by a route that has no connection to any of the essay’s conclusions.

This collection’s habit is that an assertion which has never rejected anything proves nothing. The coverage check earns its place by the other criterion: it is a quantity with a known value that the machinery does not know, computed by a path that would break under any of a dozen plausible sign errors. Everything else in this essay is downstream of it.

The generalisation #

A method’s cost is usually measured on the case where its assumptions hold, and the assumption that made the measurement easy is often the one that fails in practice. The previous rung’s honesty about which pair of schemes it used is what made this rung possible; a rung that had quietly said “two cell schemes” would have left a general-sounding number resting on a special case.

The general pattern is that an exactness claim has a domain. Conservation is exact when the overlap areas are exact, and the overlap areas are exact when the geometry cooperates. Move to geometry that does not cooperate and the exactness becomes an accuracy, whose value depends on the arithmetic — and a downstream check written against the exact case will now fail for a correct implementation.

Anyone writing such a check has a decision to make and should make it explicitly: is the tolerance a statement about the algorithm or about the geometry? If it is about the algorithm, it has to be loose enough for the hardest geometry the algorithm supports. If it is about the geometry, there have to be two tolerances and a way of knowing which case is running.

Who found it, and when #

Sutherland and Hodgman published their reentrant polygon clipping in 1974 for computer graphics, against half-planes in the plane. The spherical version, clipping against great circles, is standard in the geographic literature; the version that also handles small circles, which is what a parallel needs, is less standard and is usually avoided by densifying the parallel into short arcs.

The Van Oosterom–Strackee formula for a spherical triangle’s area dates from a 1983 paper in IEEE Transactions on Biomedical Engineering, of all places — it was developed for computing solid angles in electrocardiography. It is preferred to Girard’s excess-of-angles form because it needs no inverse trigonometric functions of nearly-degenerate quantities, and it is signed, which Girard’s is not.

The problem of moving a field between discrete global grids is old and has a large literature under the name regridding or remapping, mostly from climate modelling, where it is done every time an atmosphere model talks to an ocean model. The standard tools compute exact conservative remapping weights by clipping, and the reason they are careful about it is that a climate model that does not conserve mass drifts.

Where the ladder goes next #

This rung pays a debt about geometry. The height ladder has one about physics: it measured how far a plumb line drifts between the top and the bottom of a mountain, using one buried mass at one offset, and real mountain country produces deflections ten times larger than that model’s.