Chapter 16. Temporal Tessellations

A discrete global grid system (DGGS) partitions the Earth into a hierarchy of cells, each identified by a 64-bit integer, so that a position becomes a cell identifier and a containment test becomes an integer comparison. MobilityDB supports three of them, and a temporal cell index type records the movement of an object as the sequence of cells it occupies over time. Each grid tessellates the Earth, and these three tessellate it globally: a cell identifier names a cell of one of them wherever it is read, which is what lets a temporal type carry cells and nothing else.

Figure 16.1, “An AIS vessel track leaving Frederikshavn on the three grids, with the cells the track passes through shaded and a marine protected area in green. The upper row states the whole track at the resolutions whose cells are closest in area and outlines in black the excerpt the lower row states, one resolution finer in each grid. Vessel track and protected areas from the Danish AIS data; basemap © OpenStreetMap contributors.” shows one AIS vessel track leaving Frederikshavn on the three grids, at the resolution of each whose cells are closest in area — 0.57 km² for H3, 0.43 km² for QUADBIN and 0.32 km² for S2 at this latitude — with the cells the track passes through shaded and a marine protected area in green. A temporal cell index records that shaded sequence, so the track is one and the same and each grid states it as a different sequence of identifiers. Asking whether the vessel entered the protected area then becomes an integer test between two sets of identifiers rather than a test between two geometries. The lower row states the excerpt outlined in black above, one resolution finer in each grid, where an H3 cell has about a seventh of the area of its parent and a QUADBIN or S2 cell about a fourth, and the sequence follows the track closely enough to stand for it.

Figure 16.1. An AIS vessel track leaving Frederikshavn on the three grids, with the cells the track passes through shaded and a marine protected area in green. The upper row states the whole track at the resolutions whose cells are closest in area and outlines in black the excerpt the lower row states, one resolution finer in each grid. Vessel track and protected areas from the Danish AIS data; basemap © OpenStreetMap contributors.

The three differ in the shape of a cell and in how the hierarchy branches. Uber's H3 tessellates the sphere into 122 base cells at resolution 0 and subdivides each into 7 children at every finer resolution, up to 15, so a cell is a hexagon on an icosahedron and its identifier encodes the base cell, the resolution and the hierarchical position. CARTO's QUADBIN is built on the slippy-map (Web-Mercator) tile scheme: a single world cell at resolution 0 subdivides into four equal children at every finer resolution, up to 26, and the identifier encodes a header tag, the resolution and the tile coordinates. Google's S2 projects the six faces of a circumscribed cube onto the sphere and subdivides each face into four children, up to level 30, so a cell is a spherical quadrilateral and the identifier encodes the face, the position along a Hilbert curve and the level.

Each shape buys something. A hexagon has six neighbours all at the same distance from its centre, so an H3 step is the same move in every direction, which is what a flow or a density surface wants. A QUADBIN square is a slippy-map tile, so a cell IS the tile a map server already serves and the identifier converts to the (x,y,z) triple and the quadkey string of that ecosystem. An S2 cell is a quadtree cell of a cube face projected onto the sphere, so the descendants of a cell occupy one contiguous interval of the Hilbert curve and an ancestor test is a pair of integer comparisons. The grids are documented by their authors at h3geo.org, CARTO and s2geometry.io, and the family they belong to at Discrete global grid.

They answer the same questions, so this chapter states each operation once and names the grid only where the answer depends on it. S2 calls a resolution a level; the two words denote the same quantity.

A cell index type shares its on-disk representation with tbigint: both store a temporal 64-bit integer. Not every integer is a cell, since each grid gives its cells the structure its specification defines, QUADBIN its header, resolution and unused bits, S2 its face and the one bit ending its position, and H3 its mode bits. The distinct SQL type exists so that the type-checker rejects a cell-specific function applied to an arbitrary tbigint trajectory, and the reverse, and an integer entering a cell type is checked as the text input of the type checks its string: an S2 value is a cell of its grid, a QUADBIN value a well-formed index of any mode, and an H3 value a cell, a directed edge or a vertex.

As with other temporal types, a cell index type has four subtypes: Instant, discrete sequence, continuous sequence with step interpolation, and SequenceSet. Cell identifiers are discrete, so linear interpolation between two of them has no meaning and step interpolation is always used.

A raster is a tessellation of its own: a grid of pixels laid over a footprint, whose cell is a pixel. It stands in this chapter beside the three global grids, and differs from them in what a cell carries. An H3, QUADBIN or S2 cell carries identity, so what a trajectory over one of them makes is a temporal cell index; a raster cell carries a value, so what a trajectory read against a raster makes is a tfloat of the values it passes over, and there is no temporal raster type. The sections below therefore state a raster wherever it answers the operation a cell answers, and state the reading of one along a trip on its own.

The PostGIS raster extension stores gridded coverage data (elevation, temperature, satellite imagery, …) in the raster type. Each raster has one or more bands; a band holds a 2D array of pixel values, a spatial extent, a pixel size, and an optional nodata sentinel value.

Raquet is a cloud-native raster format that stores raster tiles as rows in an Apache Parquet file. Each row holds the pixel bytes for one Web-Mercator tile together with its QUADBIN cell identifier, a 64-bit integer that encodes the tile's zoom level and Morton-interleaved x/y coordinates. No separate spatial metadata is required: the bounding box and pixel-to-coordinate mapping are fully determined by the QUADBIN value. The specification names that column block and keeps one more row, at block = 0, whose metadata column states in JSON the tile size, the type and nodata value of each band, and the compression of the band bytes.

The two differ in what a value carries. A raquet value holds its pixels and its QUADBIN cell in one value, so its extent and its pixel grid follow from the cell and it answers the Web-Mercator grid alone. A PostGIS raster states an arbitrary spatial reference system and an arbitrary affine georeferencing, and it is the one the processing functions of the section called “Raster-Specific Operations” take: clip, transform, rescale, reclass, summaryStats and dumpAsPolygons. MEOS computes both, so neither needs PostgreSQL to evaluate.

A multi-spectral coverage is read band by band on either path. The RaQuet specification gives each band of a tile a column of its own, band_1, band_2 and so on, so such a coverage is a set of single-band tiles sharing one QUADBIN cell and rasterTileValue samples the band it is given, while on the PostGIS raster path the band argument names it. What a raquet value does not carry is the interleaved layout the specification offers for RGB imagery, which packs the bands of a tile into a single JPEG- or WebP-compressed column.