Skip to main content

Index Encoding

A5 uses a 64-bit unsigned integer to uniquely identify each cell on Earth. This encoding scheme is carefully designed to efficiently store the location and resolution information while maintaining useful properties like spatial locality and hierarchical relationships.

Terminology​

Generally the term cell is used to describe the pentagonal region that the A5 grid is made up of, but in addition cells at resolutions 0 and 1 have special names as they are stored differently in the index:

  • Resolution 0 cells are also called origins
  • Resolution 1 cells correspond to quintants, one cell per fifth of a dodecahedron face
  • Resolution 2+ cells are just cells
  • There is a world cell which can be thought of as having resolution -1

See Teohedron for how the cells are constructed.

64-Bit Structure​

The 64 bits are organized into several distinct sections:

┌────────────────────────────────────────────────────────┐
│ 6 bits │ Variable bits │ 2 bits │ Trailing zeros │
│ Origin/ │ Curve index │ resolution │ │
│ Quintant │ │ tag │ │
└────────────────────────────────────────────────────────┘
63 - 58 57 - ... .. ... - 0

Components​

  1. Bits 63-58 (6 bits): origin or quintant

    • Encodes which of the 12 pentagonal faces (origins) and/or which of the 60 quintants the cell is in
    • For resolution 0: directly encodes origin ID (0-11)
    • For resolution ≥ 1: encodes quintant 5 × origin_id + k (0-59), where k (0-4) is the segment's position within its origin
  2. Curve Position: Variable length, 0 to 58 bits

    • For resolution ≥ 2: encodes position along the teohedral curve, A5's space-filling curve
    • Length = 2 × (resolution - 1) bits
    • Not present for resolution 0 and 1
  3. Resolution Tag (2 bits): The right-most 01 or 10 bitpair

    • A tag is the bit pattern read first when processing an index: it says how to interpret the remaining bits (see Bit Tags)
    • The position of these bits encodes the resolution level
    • For resolution 0: 10, resolution 1: 01 (1 shifts by one bit)
    • For resolution ≥ 2: shifts by 2 bits per resolution (two bits per curve level)
  4. Trailing Zeros: All remaining bits

    • Pads the integer to 64 bits
    • Allows efficient computation of parents (right-shift) and children (left-shift)
    • Unambiguously determines which bits are the resolution tag bits

Examples​

Let's look at how different cells are encoded. Using London -0.1276, 51.5074 as our example location:

Resolution 0: Origin only​

At resolution 0, there are only 12 cells covering the entire Earth. The top 6 bits directly encode the origin (000100 = 4).

Notice how all bits are zeros after the '10' resolution tag.

Cell ID (binary): 0001001000000000000000000000000000000000000000000000000000000000
Cell ID (hex): 0x1200000000000000
Longitude: -0.1276, Latitude: 51.5074, Resolution: 0

Resolution 1: Quintant (Origin & segment)​

At resolution 1, each pentagon is divided into 5 segments, giving 60 total cells. The top 6 bits encode both origin and segment as (011000 = 24). This can be decomposed into 5 x 4 + 0 = 24, thus like with resolution 0, we are in origin 4, and in the first of its 5 quintants (as the count starts with 0).

The resolution tag is now '01', again followed by zeros.

Cell ID (binary): 0110000100000000000000000000000000000000000000000000000000000000
Cell ID (hex): 0x6100000000000000
Longitude: -0.1276, Latitude: 51.5074, Resolution: 1

Resolution 5: Curve Subdivision​

From resolution 2 onwards, cells are subdivided along the teohedral curve. At resolution 5, the top 6 bits encode the quintant, just like in resolution level 1.

They are followed by the 8-bit curve value 11101100 encoding position along the space-filling curve.

Finally, there is again the '10' resolution tag, followed by zeros.

Cell ID (binary): 0110001110110010000000000000000000000000000000000000000000000000
Cell ID (hex): 0x63b2000000000000
Longitude: -0.1276, Latitude: 51.5074, Resolution: 5

Index explorer​

Click on the interactive map below to change the location to index, and zoom to change the resolution. Notice how the indices of nearby locations are similar, sharing many bits. Likewise, when zooming in most of the bits remain the same, just more bits are added to the curve S value.

Cell ID (binary): 0110001110010111001001001000000000000000000000000000000000000000
Cell ID (hex): 0x6397248000000000
Longitude: -0.1276, Latitude: 51.5074, Resolution: 10

Special Case: Resolution 30​

At resolution 30 the curve requires 2 × 29 = 58 bits, and combined with 6 quintant bits that's already 64 — leaving no room for the resolution tag.

The solution is a virtual 66-bit layout: when the final 1, 3 or 5 bits of the 64-bit index are set to a special value - before interpreting the index it must be first shifted right and then treated as a 66 bit integer, where the last two bits are 10 as usual.

Depending on the pattern, the quintant value is also offset.

PatternPattern bitsShiftQuintant offsetQuintant range
...111 bit00–31
...10033 bits3232–39
...1000055 bits4040–41

Examples:

  • QQQQQS...S1 (64 bits) becomes 0QQQQQS...S10 (66 bits)
  • QS...S10000 (64 bits) becomes 10100QS...S10 (66 bits). Note static offset of 40 (101000 in binary).

Why this works​

The trick above exploits the fact that the indexing scheme has some unused values, which can be used to represent the final resolution level. In the general case, an index value will have a 1 followed by an odd number of 0s, e.g. ...1000. Thus by choosing patterns that have an even number of 0s, we can be sure to avoid collisions and effectively gain an extra two bits. See Bit Tags for how every tag is assigned.

Quintants beyond 41​

Resolution 30 supports only quintants 0–41, as there isn't room for the remaining quintants in the index space. Any quintant value above 41 falls back to resolution 29, gracefully losing one level of precision rather than failing. See the teohedron example for where the quintants lie.

Special Case: World Cell​

A special cell identifier with value 0n (all 64 bits are zero) represents the entire world. This cell serves as the root of the A5 hierarchy. It is useful for hierarchical operations where you need to represent the root of all cells, such as:

  • Traversing the complete cell hierarchy from the top down
  • Representing "all cells" in a compact form
  • Computing all resolution 0 cells via cellToChildren(WORLD_CELL, 0), or any other resolution

See World Cell Encoding for how it is encoded.

World Cell Boundary​

A general A5 cell boundary is a set of points which enclose the region represented by that cell. As the world cell contains the whole world it is not bounded by any points. Thus the boundary returned by cellToBoundary(0n) is [], an empty array to represent the fact the region is valid, but unbounded.

Note that other libraries may need to handle this case specially as not all systems have a concept of a geometry that is the entire globe

World Cell Location​

Conversely, for completeness cellToLonLat(0n) will return [0, 0]. While this choice is arbitrary, as the world cell covers the whole world and thus has no center - it seems the most natural choice as it is the point at the center of many map projections.

Key Properties​

1. Hierarchical Relationships​

Parent and child relationships can be computed efficiently:

  • Parent: Clear the last two curve bits and move the resolution tag up two positions
  • Children: Append each 2-bit child index and move the resolution tag down two positions

Example (resolution 5 → resolution 4 parent):

Child:  011000 11101100 10 00000...  (res 5)
Parent: 011000 111011 10 00000... (res 4)
└─ Last 2 curve bits removed (one curve level)

2. Spatial Locality​

Cells that are geographically close tend to have similar cell IDs, which is excellent for database range queries and spatial clustering.

3. Fixed Size​

All cell IDs are exactly 64 bits (8 bytes), making them:

  • Efficient to store in databases
  • Fast to compare and sort
  • Compatible with standard integer types in most programming languages

4. High resolution​

By storing the resolution implicitly and effectively using 6 bits for the quintant, A5 dedicates the remaining 58 bits to the curve at its highest resolution. The virtual 66-bit encoding at resolution 30 squeezes every last bit out of the 64-bit integer, achieving cell areas of around 30mm² — better than S2 (~1cm²) and H3 (~1m²).