qdgc for PostgreSQL / PostGIS

Extended Quarter Degree Grid Cell (QDGC) codes as a pair of PostgreSQL extensions, so that grid generation can happen inside the database next to the data instead of being exported, processed elsewhere and loaded back.

Two extensions, mirroring the way h3-pg splits h3 from h3_postgis:

Extension Requires What it gives you
qdgc nothing — pure SQL, trusted encode, decode, hierarchy, level metrics, bbox fills
qdgc_postgis qdgc, postgis geometry/geography bindings and area fills

Keeping the core free of PostGIS means it installs anywhere, including managed platforms that will not accept a compiled extension.

Encoding is bit-for-bit identical to qdgc_py, which is the arbiter for QDGC behaviour in this repository. That is enforced by a generated fixture, not by hand-written expectations — see Testing.

Install

From PGXN:

pgxn install qdgc

Or from a checkout:

make install
psql -d yourdb -c "CREATE EXTENSION qdgc;"
psql -d yourdb -c "CREATE EXTENSION qdgc_postgis;"   # needs PostGIS

There is nothing to compile. make install only copies the .control files and the generated qdgc--0.1.0.sql / qdgc_postgis--0.1.0.sql into the server’s extension directory.

Requires PostgreSQL 13 or newer — trusted = true in the control file is a PostgreSQL 13 feature. qdgc_postgis additionally requires PostGIS. CI runs the full suite against PostgreSQL 13 through 17.

Both extensions are relocatable, but the functions call each other by unqualified name, so install them into a schema that is on your search_path (the default, public, is fine).

API

Encoding

Function Returns Notes
qdgc_encode(lon, lat, level) text primary form, (lon, lat) order
qdgc_latlng_to_cell(lat, lng, level) text h3-style alias, reversed order
qdgc_latlng_to_cell(geometry, level) text transforms non-4326 input
qdgc_latlng_to_cell(geography, level) text
qdgc_degree_prefix(lon, lat) text the level 0 code, e.g. E031N02

Decoding

Function Returns
qdgc_cell_to_bounds(cell) (min_lon, min_lat, max_lon, max_lat)
qdgc_cell_to_lonlat(cell) point — x = lon, y = lat
qdgc_cell_to_latlng(cell) (lat, lng), h3-style
qdgc_cell_to_geometry(cell) POINT geometry, EPSG:4326
qdgc_cell_to_boundary_geometry(cell) POLYGON geometry, EPSG:4326
qdgc_cell_to_geography(cell) / ..._boundary_geography(cell) geography forms
qdgc_get_level(cell) integer, NULL if the code is invalid
qdgc_is_valid_cell(cell) boolean

Hierarchy

Function Returns
qdgc_cell_to_parent(cell [, parent_level]) text
qdgc_cell_to_children(cell [, child_level]) setof text

QDGC codes are strings, and the hierarchy is plain prefix containment. A descendant test is child LIKE parent || '%', so a btree index on the code column already serves ancestor range scans — no custom operator class needed.

Areas of interest

Function Returns
qdgc_polygon_to_cells(geometry, level [, predicate]) setof text
qdgc_bbox_to_cells(min_lon, min_lat, max_lon, max_lat, level) setof text
qdgc_estimate_cell_count(geometry, level) bigint
qdgc_bbox_cell_count(min_lon, min_lat, max_lon, max_lat, level) bigint

predicate is 'intersects' (default), 'centroid' (cell centre inside the geometry) or 'contains' (cell wholly inside), matching qdgc_py.polygon_to_cells.

qdgc_polygon_to_cells is a pruning quadtree descent, not a grid over the bounding box: it starts from the degree squares that meet the AOI and splits only cells that still meet it. Cost scales with the AOI boundary rather than with the area of its envelope, which is what makes deep fills of a coastline practical. Cells found to be wholly inside stop being tested at all.

Always guard a fill with qdgc_estimate_cell_count — a level 12 fill of a large country is hundreds of millions of cells.

Metrics

Function Returns
qdgc_level_degrees(level) side length in degrees
qdgc_get_num_cells(level) cells covering the globe
qdgc_average_cell_area(level [, lat [, unit]]) spherical estimate, 'km^2' or 'm^2'
qdgc_cell_area_km2(cell) true area on the WGS84 spheroid
qdgc_version() extension version

Levels

Level Side Approx. at equator Cells on the globe
0 1° 111 km 64 800
1 0.5° 55.6 km 259 200
2 0.25° 27.8 km 1 036 800
3 0.125° 13.9 km 4 147 200
5 0.031 25° 3.5 km 66 355 200
7 0.007 812 5° 869 m 1 061 683 200
10 ~0.000 98° 109 m 67 947 724 800
12 ~0.000 24° 27 m 1 087 163 596 800

Usage

-- Encode
SELECT qdgc_encode(31.4, 2.7, 5);                      -- E031N02ADBAC
SELECT qdgc_latlng_to_cell(geom, 7) FROM observations; -- straight from a geometry

-- Decode
SELECT qdgc_cell_to_boundary_geometry('E031N02ADBAC');
SELECT qdgc_cell_area_km2('E031N02ADBAC');

-- Establish a geocode layer for an area of interest
INSERT INTO geocode_cells (code, level, geom)
SELECT c, 7, qdgc_cell_to_boundary_geometry(c)
FROM qdgc_polygon_to_cells((SELECT geom FROM areas WHERE name = 'Uganda'), 7) AS c;

-- Check the size first
SELECT qdgc_estimate_cell_count((SELECT geom FROM areas WHERE name = 'Uganda'), 7);

-- Roll observations up to a coarser level
SELECT qdgc_cell_to_parent(code, 3) AS parent, count(*)
FROM observations_qdgc GROUP BY 1;

-- All descendants of a cell, straight off the index
SELECT * FROM observations_qdgc WHERE code LIKE 'E031N02AB%';

Testing

python tools/gen_parity_fixture.py    # regenerate vectors from qdgc_py
python tools/run_tests.py             # run the suite

gen_parity_fixture.py produces ~22 000 encode vectors and ~6 500 decode vectors from qdgc_py.core, deliberately weighted towards the cases that break naive implementations: exact quadrant midpoints, signed zeros, the poles and antimeridian, and the legacy quirk where exactly ±1.0 is not reduced to a fraction. The SQL is then required to match them exactly. If core.py ever changes, regenerate and the suite will tell you what moved.

Test files assert with RAISE EXCEPTION, so there are no expected-output files to drift. tools/run_tests.py loads sql/install/**.sql into a throwaway schema, which needs no write access to the server’s extension directory.

Agreement with qdgc_py

Encoding, decoding and hierarchy are bit-for-bit exact, enforced by the parity fixture. Area fills are also exact: tools/compare_fill.py checks qdgc_polygon_to_cells against qdgc_py.polygon_to_cells over six shapes — an aligned box, a diagonal edge, a 240-vertex blob, a polygon with a hole, a re-entrant notch and a sparse diagonal band — and the selected cell sets are identical at every level tested.

Getting there required matching two rules that pull in opposite directions:

  • The AOI envelope is half-open on its upper edges (qdgc_py derives candidates with ceil(...) - 1), so a cell lying outside the AOI but sharing an edge with it is excluded — even though ST_Intersects reports a zero-area touch as an intersection.
  • A cell touching an interior edge is included, because qdgc_py counts a point lying on a segment as inside.

Both are covered by regression tests in test/sql/04_postgis.sql.

One difference remains, deliberately:

  • Cell count estimates. qdgc_estimate_cell_count measures polygon area on the WGS84 spheroid; qdgc_py uses an equirectangular approximation. Both are estimates used as guards, and both are capped by the exact envelope count.

Performance

Measured on PostgreSQL 17.10 / PostGIS 3.6.4, comparing the quadtree descent against the legacy full-envelope ST_SquareGrid + ST_Intersects:

AOI Fill vs envelope Level 9 speedup
Thin diagonal band sparse 8.5x
Convoluted blob moderate 1.3x
Triangle half 1.2x
Aligned box dense 0.5x

The descent wins when the AOI is sparse within its bounding box — a country, a coastline, a river corridor — and loses roughly 2x when the AOI nearly fills its envelope, because it pays log-depth work per cell that a flat grid does not. Real areas of interest are sparse, which is the case it is tuned for. Run python tools/compare_fill.py to reproduce.

Releasing to PGXN

The distribution is named qdgc and provides both extensions. The archive is built from this directory with a versioned prefix, so living in a monorepo is not a problem — PGXN takes an uploaded archive rather than reading the repo.

python tools/build_sql.py     # regenerate versioned install scripts
python tools/run_tests.py     # must pass
git commit ...                # make_dist refuses a dirty tree
python tools/make_dist.py     # -> dist/qdgc-<version>.zip

make_dist.py checks that the version in META.json, both .control files and the generated SQL filenames all agree, and builds the archive with git archive so only tracked files are included. Upload the result at https://manager.pgxn.org/upload.

Bumping the version means editing META.json, both .control files and VERSION in tools/build_sql.py, then regenerating. Encoding output is stable within a major version; any change to a produced code is a major bump.

Relationship to the rest of the repository

  • qdgc_py/ is the reference implementation and the arbiter when variants disagree.
  • qdgc_delivery/ holds the historical country-GeoPackage production pipeline (the run_qdgc_* batches and the FME export) that used to live here, plus the superseded plpython3u functions it was built on.

Reference

Larsen, R., Holmern, T., Prager, S. D., Maliti, H., and Røskaft, E. (2009). Using the extended quarter degree grid cell system to unify mapping and sharing of biodiversity data. African Journal of Ecology. https://doi.org/10.1111/j.1365-2028.2008.00997.x