Algorithms

How each class of operation is computed, and what it costs. None require a spatial index, a lookup table of geometry, or a network call.

Indexing a coordinate

latLngToCell runs five steps:

1. Datum — the coordinate is taken as KSA-GRF17. No transformation is performed.
2. Project — LAEA forward transform to planar x, y in metres from 24°N 45°E.
3. Base cell — determine which Res 0 cell contains the point.
4. Descend — at each level to the target resolution, determine which of the seven children contains the point and record the digit.
5. Pack — assemble mode, resolution, base cell, and digits into the 64-bit index.

Cost is O(resolution) — one descent step per level — and independent of dataset size. Indexing a point at Res 8 costs the same whether the database holds one row or ten billion.

The inverse, cellToLatLng, unpacks the digits to lattice coordinates, converts to planar coordinates, and applies the inverse projection.

Hierarchy

Parent — clear the child digits below the target resolution to the unused marker 7, then rewrite the resolution field. Two masked writes, O(1).

Both writes are required. Changing digits without updating the resolution field produces an invalid cell, and because unused digits are 7 — all bits set — a digit field must be cleared before being written, not OR-ed into.

Children — write the child digit at the next position and increment the resolution, once per child. O(7ⁿ) in the number of children produced, which is the size of the output rather than a cost of the algorithm.

Compaction — group cells by parent; where all seven siblings are present, replace them with the parent; repeat until no group is complete. Produces the smallest mixed-resolution set covering the same ground. Cost is dominated by grouping, O(n log n).

Compaction is worth applying before storing or transmitting any large contiguous cell set. Dense regions collapse dramatically; scattered sets barely compact at all.

Traversal

Traversal works in integer lattice coordinates, which is what makes it exact.

Neighbours — add each of the six unit direction vectors. When a step crosses into another base cell, the lattice coordinate is rebased. O(1).

gridDisk / gridRing — walk the lattice outward from the origin. A disk of radius k contains 3k² + 3k + 1 cells and a ring exactly 6k, with no exceptions, because there are no pentagons.

gridDistance — computed directly from the difference in lattice coordinates, not by search. O(1) within a base cell.

Because the lattice is integer throughout, none of these depend on floating-point tolerance. Two cells are neighbours or they are not.

Region operations

polygonToCells — take the polygon's bounding box in projected coordinates, enumerate candidate cells at the target resolution, then test each against the polygon by the chosen containment mode: centroid-in-polygon, or cell-intersects-polygon.

Cost scales with the bounding box, not the polygon's complexity — so a long diagonal or a sparse multipart polygon costs more than its area suggests. Where that matters, fill at a coarse resolution first and refine only the cells the boundary passes through.

Partial coverage — for cells the boundary crosses, the cell polygon is clipped against the region and the area ratio returned. Only boundary cells need clipping; interior cells return 1.0 without geometric work.

cellsToMultiPolygon — collect boundary edges, discard those shared by two cells in the set, and chain the remainder into rings. Interior edges cancel, leaving the outline.

Terra Grid Code

Encoding — concatenate the base cell and child digits into a payload of 7 + 3 × res bits, encode most-significant-first into Base32 with leading zeros retained, then append the Luhn mod 32 check character.

Decoding — validate the check character first and reject on failure. Only then unpack. A code that fails validation is not decoded, and no correction is attempted — the check detects errors, it does not locate them.

Cost summary

Operation	Cost
latLngToCell	O(res)
cellToLatLng	O(res)
cellToParent	O(1)
cellToChildren	O(7ⁿ) — output size
gridDisk(k)	O(k²) — output size
gridDistance	O(1)
isValidCell	O(1)
compactCells	O(n log n)
polygonToCells	O(bounding box at resolution)

The pattern: identity and hierarchy operations are constant-time bit manipulation; geometry costs scale with resolution; region operations scale with area.

Next

• Coordinate systems — the representations these move between
• Core library overview — how the layers fit together

---

The Terra System is designed and developed by Tec Solution KSA.