Grid extension reference

Use these contracts when implementing a grid or optimizing a system. Writing a grid system provides a complete example. User operations remain in The grid interface.

Tree node access

DiscreteGlobalGrids.Engine.node_cell Function

node_cell(cursor) -> Union{AbstractCellIndex,Nothing}

The cell this node stands for, or nothing at the synthetic whole-sphere root.

source

DiscreteGlobalGrids.Engine.node_indices Function

node_indices(cursor) -> AbstractVector{Int}

Return the ascending grid indices owned by this node. A window cursor returns an O(1) range; a selection cursor returns its materialized vector.

source

Hierarchy traits

These declarations let generic algorithms use a system's hierarchy, cell ordering and point-location methods efficiently.

DiscreteGlobalGrids.has_sorted_subtrees Function

has_sorted_subtrees(::A5System) -> Bool

false: no descendant_range contract is asserted across the level-0 to level-1 quintant fan-out.

• treeify uses selection mode and materializes root indices; prefer a PartialGrid for deep grids — a complete one is O(cells) in memory and not viable past about level 12.

• MultiOrderCellSet orders by (level, index) rather than by curve interval, and level_ranges on one raises an ArgumentError.

• descendants is overridden to avoid level-by-level expansion.

source

has_sorted_subtrees(sys::AbstractHierarchicalGridSystem) -> Bool

Whether the descendants of any cell, at any fixed deeper level, occupy a contiguous interval of that level's canonical dense order.

false by default. A system opting in must implement descendant_range. The property enables range-based subtree membership and traversal.

Systems whose canonical order is a space-filling curve (nested HEALPix, Z7, H3's resolution-major order) have this property; it is a fact about the ordering, and declaring it falsely produces silently wrong subtree answers.

source

DiscreteGlobalGrids.has_congruent_refinement Function

has_congruent_refinement(sys::AbstractHierarchicalGridSystem) -> Bool

Whether a cell's children tile the cell: no part of the parent is left uncovered and no child reaches outside it.

false by default, and declaring it falsely is a correctness bug rather than a performance one. The quad-face family refines an aligned lattice per face and qualifies; aperture-7 rosettes (IGEO7, H3) and A5's Hilbert children do not, which is why a coverage there can leave slivers.

What it buys the traversals is REACHABILITY: children inside their parent means a cell that meets a target has a parent that meets it too, so a descent through cells that meet the target reaches every cell that does. Without it a covering must also descend through cells that miss.

source

DiscreteGlobalGrids.has_direct_location Function

has_direct_location(sys::AbstractHierarchicalGridSystem) -> Bool

Whether cellat on a complete level grid of sys is answered from the query point's coordinates alone, rather than by the generic search over the grid's cells.

• false by default. A system opting in must implement cellat for its complete level grids; declaring it without one leaves every caller on the generic search while claiming otherwise.

• What it buys is location on a subset of a level: a PartialGrid over such a system asks the complete level and keeps the answer only when it is a member, instead of building a spatial tree over its own cells.

• A system whose location IS the generic search must leave this false: searching the whole level and discarding everything outside the subset is strictly more work than searching the subset.

source

DiscreteGlobalGrids.node_extent Function

node_extent(sys::AbstractHierarchicalGridSystem, c::AbstractCellIndex) -> GO.UnitSpherical.SphericalCap

Return a spherical cap containing the geometry of every descendant of c, at every level through maxlevel(sys). Query engines use it to prune subtrees.

The cap need not contain child caps or child node_extent results. Bounds along a branch are not required to be nested or to have decreasing radii. A cell's own bounding cap is not a substitute for its subtree extent.

The default inflates the cell cap by cap_inflation. Implementors must validate the full descendant-geometry guarantee, including between sampled vertices. See Collection and traversal contracts for the complete pruning contract.

source

Geometry and traversal hooks

These helpers support grid implementations: coordinate transforms, boundary rings, spatial bounds and traversal engines.

DiscreteGlobalGrids.one_ring Function

one_ring(grid, c, connectivity) -> ordered neighbours of `c`

The k == 1 primitive: c's immediate neighbours, in the order winding(grid, connectivity) declares. An internal hook, not part of the public API.

A system implements this one method and inherits neighbors, ring, and the shell walk behind both from Fallbacks.adjacency_shells. The generic method is the geometric one — Fallbacks.adjacent_cells wound about the cell's centroid — and a system with native adjacency overrides it.

A system that overrides this owes a matching winding declaration. The order is stated once, there, rather than in prose here: it is what the shell walk reads to carry rotational order outward to k >= 2 without measuring it, so a wrong declaration is a wrong answer rather than a slow one. Declaring nothing leaves the default Unordered(), which is always safe — the walk then measures azimuth instead.

Where the turn starts is the system's own business and is not part of that declaration: the shell walk pins the starting cell of each outer ring separately, and nothing here promises a relationship between the start of one cell's ring and the start of its neighbour's.

The return may be any ordered, indexable collection with the grid's cell-index eltype; a fixed-capacity SmallVector sized by maxneighbors is what keeps the one-ring sweeps allocation-free.

source

DiscreteGlobalGrids.cap_inflation Function

cap_inflation(::A5System) -> Float64

1.75.

A5's four Hilbert children cover their parent's area but can extend beyond its footprint. The measured descendant-to-cell-cap ratio reaches 1.45363, with an extrapolated bound of 1.47078; 1.75 preserves the node_extent covering invariant.

source

cap_inflation(::H3System) -> Float64

1.2, the generic default.

Children overhang their parents, so node_extent must be inflated. The measured maximum ratio of a descendant boundary vertex's distance from an ancestor's cell-cap centre to that cap's radius is 1.0522; 1.2 preserves the covering invariant. Descendant caps are not the quantity bounded and may exceed it.

source

cap_inflation(sys::AbstractHierarchicalGridSystem) -> Float64

The factor by which the default node_extent inflates a cell's own bounding-cap radius so that the cap covers the cell's entire subtree.

Defaults to 1.2.

The value bounds how far descendant geometry extends beyond a cell's bounding cap — the ratio of the farthest descendant boundary point's distance from the cap centre to the cap radius — and must be validated for the system's refinement geometry. It is not a bound on how far a descendant's own cap extends; caps are bounds in their own right and may exceed it. Systems overriding node_extent ignore it.

Raising it costs query time (looser pruning). Setting it too low is a correctness bug — see the covering law in node_extent.

source

DiscreteGlobalGrids.authalic_sphere Function

authalic_sphere(x) -> GeometryOpsCore.Spherical

Return the spherical compute manifold whose cell areas equal the corresponding ellipsoidal areas. x may be a GeometryOpsCore.Manifold or Helpers.AuthalicTransform.

A Geodesic resolves to Spherical(; radius=R_A). A Spherical is returned unchanged.

Not Spherical()

GO's default Spherical() uses the WGS84 mean radius, 6371008.8 m, not the area-preserving authalic radius, 6371007.180918474 m. Do not substitute a bare Spherical() for this result.

Planar and AutoManifold throw, for the reason given in AuthalicTransform.

source

DiscreteGlobalGrids.Fallbacks.authalic_stretch Function

authalic_stretch(t::Helpers.AuthalicTransform) -> Float64

Lipschitz constant of the authalic-to-geodetic warp Φ on the sphere: d(Φp, Φq) ≤ authalic_stretch(t) · d(p, q) for every pair of points, with d the great-circle distance. It equals 1 + Σ 2j|C'_j| (1 + 4.4886e-3 for WGS84), obtained by bounding the north and east components of the warp differential. It is exactly 1 when e² = 0.

Multiplicative rather than additive is what keeps it usable: inflating by authalic_shift instead puts a 0.13° floor under every node extent, which swamps the cell itself from about level 8 down.

source

DiscreteGlobalGrids.Fallbacks.authalic_shift Function

authalic_shift(t::Helpers.AuthalicTransform) -> Float64

Upper bound in radians on the authalic-to-geodetic displacement, max_ξ |φ(ξ) - ξ|, computed as Σ|C'_j| for φ(ξ) = ξ + Σ C'_j sin(2jξ). For WGS84 the bound is 2.2421e-3 radians.

source

DiscreteGlobalGrids.Helpers.AuthalicTransform Type

AuthalicTransform{T}

Precomputed forward and inverse authalic-latitude series and authalic radius for one ellipsoid of revolution. Latitude conversions evaluate the stored coefficients without recomputing ellipsoid constants.

Constructors

AuthalicTransform{T}(; semimajor_axis, flattening)
AuthalicTransform{T}(; semimajor_axis, inverse_flattening)
AuthalicTransform{T}(; semimajor_axis, eccentricity_squared)

T and semimajor_axis default to Float64 and the WGS84 semi-major axis; semimajor_axis affects only authalic_radius, as the latitude transforms are scale-free. Exactly one shape parameter is required; otherwise construction throws EllipsoidShapeError. Coefficients are evaluated in at least Float64 before conversion to T.

Fields

• semimajor_axis — a.

• eccentricity_squared — e² = f(2 − f), the canonical shape field.

• authalic_radius — R_A, precomputed (see authalic_radius).

• fwd, inv — the geodetic→authalic and authalic→geodetic sine-series coefficients C_j, in radians, j = 1…AUTHALIC_SERIES_ORDER.

julia> geodetic_to_authalicd(WGS84_AUTHALIC, 45.0)
44.871702873433939

source

DiscreteGlobalGrids.Helpers.authalic_radius Function

authalic_radius(t::AuthalicTransform) -> T
authalic_radius(semimajor_axis, eccentricity_squared) -> T

Radius of the sphere with the same area as the ellipsoid, Snyder eq. (3-13):

R_A = a · √(q_p / 2),    q_p = q(90°) = 1 + (1 − e²)·atanh(e)/e

For WGS84 this is 6.371007180918474e6 m. It equals a when e² = 0. The one-argument form returns the precomputed field.

source

DiscreteGlobalGrids.Helpers.EllipsoidShapeError Type

EllipsoidShapeError(count)

Thrown when an AuthalicTransform is asked for from anything other than exactly one shape parameter. Carries only the count; the message is built lazily in showerror.

source

DiscreteGlobalGrids.Fallbacks.closed_ring Function

closed_ring(points) -> AbstractVector{UnitSphericalPoint{Float64}}

Return a 1-based, explicitly closed copy of a boundary. An already repeated closing vertex is not duplicated. A Helpers.SmallList boundary closes into a SmallList one longer, so inline storage survives; anything else copies into a Vector.

source

DiscreteGlobalGrids.border_engine Function

border_engine(sys, c, target::Int, connectivity)
interior_engine(sys, c, target::Int, connectivity)
halo_engine(sys, c, target::Int, connectivity)

Return the iteration engine used by EdgeCellIterator, InnerCellIterator, or SubtreeHaloIterator. A system may override these methods with an O(border) or O(halo) traversal; eager operations collect the same engine.

An engine is any iterator over cellindextype(sys). All three methods own their level validation, so their ArgumentErrors are the ones the eager verbs raise.

Engine selection uses private dispatch on the system type and is not part of the public compatibility surface.

The generic border and interior engines scan descendant_range, or materialize descendants when has_sorted_subtrees is false. The generic halo engine walks cells outside the subtree because a halo is not a single descendant interval.

Specializations may enumerate conservative candidates, but must filter them by the requested adjacency. If their preconditions cannot be verified, they must return generic_halo_engine(sys, c, target, connectivity).

source

DiscreteGlobalGrids.lattice_decode Function

lattice_decode(sys, c) -> (ix, iy, face)
lattice_cell(sys, level::Int, ix, iy, face) -> cell
face_orientation(sys, face) -> UInt8

Define the face-lattice operations used by the shared square halo traversal. Only systems with an aligned square lattice per face implement these methods.

lattice_decode and lattice_cell convert between cell ids and face-local coordinates, with face 0-based and (ix, iy) in 0:2^level - 1. face_orientation is the curve state a face's root uses before consuming position bits.

The traversal derives seam rectangles by decoding neighbours of border cells.

SquareBandEngine also requires these invariants:

1. cellindextype(sys) === LevelIndex. The engine emits LevelIndex and declares it as its eltype, unconditionally.

2. Ids follow face * faceside^2 + curvecode, with 0-based face and curve code. The emit step constructs ids with this arithmetic.

3. Interior face adjacency is the 3×3 lattice, so an in-face band requires no additional adjacency check.

A fourth square system holding all three subtypes AbstractQuadFaceGridSystem and writes only the three methods above. One that does not writes its own halo_engine instead.

source

ConservativeRegridding.Trees.AbstractCurvilinearGrid Type

abstract type AbstractCurvilinearGrid{M <: GOCore.Manifold}

Abstract supertype for all curvilinear grid types, parameterized by the manifold M (e.g. Planar, Spherical) the grid lives on, so algorithms can dispatch on the manifold — see the generic spherical Trees.cell_range_extent. The type itself should store the representation of the "base" of the quadtree, which should fit into the QuadtreeCursor type.

The QuadtreeCursor type is a cursor that can be used to traverse the quadtree. It should be able to traverse the quadtree in a depth-first manner, and should be able to get the child nodes of the current node.

Since the quadtree structure is the same, you would broadly need to provide:

getcell(grid, i, j) -> GI.Polygon
ncells(grid, dim::Int) -> Int
cell_range_extent(grid, irange::UnitRange{Int}, jrange::UnitRange{Int})

, i.e., provide an implementation for Trees.getcell, Trees.ncells, and Trees.cell_range_extent.

and then you may also want to specialize on STI.node_extent(::QuadtreeCursor{<: YourQuadtreeType}) -> GO.UnitSpherical.SphericalCap{Float64}

source

ConservativeRegridding.Trees.cell_range_extent Function

cell_range_extent(grid::AbstractCurvilinearGrid, irange::UnitRange{Int}, jrange::UnitRange{Int}) -> GO.UnitSpherical.SphericalCap{Float64}

Get the extent of the cells in the given range of indices.

source