DNGS STANDARD: A PROPOSAL TO ADAPT THE ISO 19170-1 (DGGS) STANDARD TO THE REQUIREMENTS OF NSDIs

We have been invited to present at the 4th Brazilian Symposium on Spatial Data Infrastructure this article that proposes the DNGS standard as an adaptation of the DGGS standard for use in countries. https://www.inde.gov.br/simposio-16-anos

PETER DE PADUA KRAUSS
Telefonica Brasil SA and AddressForAll Geo-Social Technologies Institute
Technical Director
Avenida Paulista, 171, 4th Floor, Bela Vista, São Paulo – SP, 01311-904
https://www.addressforall.org
peter@addressforall.org

THIERRY ALAIN JEAN
AddressForAll Geo-Social Technologies Institute
President
thierry@addressforall.org

MARCO AURELIO PAINELLI MARSITCH
AddressForAll Geo-Social Technologies Institute
Honorary Member
marco.marsitch@alumni.usp.br

National hierarchical grid systems, such as the “Ordnance Survey National Grid” in England, have been used for decades. Some have proven to be more useful, with a wider range of applications, when their cells are identified by short and readable labels, known as “hierarchical geocodes.” In other words, when both the grid and geocodes are developed together, they meet the application requirements.

Since they were conceived before the digital age, these grids lack digital representation of their geocodes, which is crucial for geographic databases that use them as spatial indexers—known as SFCs (space-filling curves) and quadtrees. Hierarchical grids with efficient indexers enable broader digital applications. Spatial indexers replace the continuous two-dimensional coordinate with a discrete coordinate and represent it by a one-dimensional index, typically a 64-bit positive integer.

A first technological advancement in relation to these types of hierarchical grids occurred in the 2000s, driven by “Digital Earth” initiatives, leading to significant academic and industrial investments. However, these advances were only systematized in 2017 by the OGC (Open Geospatial Consortium) in the “Topic 21” specification [1]. Subsequently, after greater consensus around the model, the ISO 19170-1:2021 standard (DGGS – Discrete Global Grid System) [2] emerged, crystallizing the DGGS concept and consolidating the use of equal-area projections in geoprocessing.

The DGGS is an ambitious standard aimed at global grids, but it still lacks a global equal-area projection with satisfactory accuracy in all nations. It is important to note that promising proposals, such as the Disdyakis Triacontahedron [3], still need years of technological maturity and consensus. As a result, the DGGS is not suitable for use by official statistical bodies responsible for national censuses or land demarcation applications.

There is a wide diversity of DGGS-compatible technologies, and they are still very recent, with few being open and patent-free, which amplifies the problem of compatibility between different implementations of this standard. Finally, another obstacle to the use of DGGS solutions concerns the adoption of geocodes: the ISO standard is silent on this matter. Standardized national geocodes are necessary for data visualization, preliminary land demarcation in digital notaries, and for human communication in general (e.g., address points, postal codes, or disaster zoning), as well as interoperability between geocodes and other applications.

Postal codes and old national grids, such as England’s, demonstrate the importance of humans knowing geocodes, as they can write or memorize the corresponding cells. Citizens of each nation need short and readable geocodes to memorize and include them in their written or verbal communications. These geocodes need to be the same or at least interoperable, related to the same national reference grid.

Therefore, we believe that every nation, in its NSDI (National Spatial Data Infrastructure), should also standardize and ensure interoperability with a hierarchical equal-area grid system, with respective standardized geocodes. In Brazil, there is an official equal-area projection, instituted by the IBGE in 2016 to support its Statistical Grid [4]. However, this grid was not designed for other applications, and its function was merely to aggregate the 2010 Census data into square cells. Unfortunately, the IBGE system is incompatible with postal applications (e.g., ZIP codes), and its geocodes are neither hierarchical nor short/mnemonic.

AddressForAll Institute, aware of the relevance of the DGGS standard and the barriers to its use, has developed a new standard tailored to the specific needs of each nation [5]. The DNGS (Discrete National Grid System) standard is a variant of the DGGS standard, where the equal-area projection does not need to be global, but rather satisfactory for national applications, such as censuses and multi-purpose cadastres. The pillars of the DNGS standard are:

Multipurpose: versatility in meeting the main requirements of postal, logistics, census, judicial, environmental, or municipal public databases. The diversity of themes and applications is a mandatory foundation, as in DGGS.
National equal-area projection: replacing the global scale (from DGGS) with the national scale in DNGS allows for the automatic adoption of a national standard, already consolidated and with greater precision to meet multipurpose needs. As in DGGS, the equal-area projection is mandatory to enable statistical operations and broad comparison functionalities.
Hierarchical grid system: from the smallest to the largest cell size, starting with 1 m² area cells and following powers of two (4 m², 16 m², 64 m², and so on), up to the national territory coverage cells. This metric requirement ensures comparability between cells from different nations.

The powers of two are more suitable for the digital environment, with bit-by-bit hierarchy (quadtree). This also ensures flexibility in compact human representation, using base 4, 8, 16, 32, or 64, adhering to RFC-4648 and its extension [8].

Congruence: child cells fully congruent with parent cells.
This ensures the possibility of multi-scale polygon representation (quadtree) and consistency in land demarcation applications.
Readable geocodes: human-readable cell identifiers, short enough to be memorized and compatible with their hierarchical representation. Cell congruence guarantees digit-by-digit hierarchy, allowing named polygons (e.g., municipalities) to support alternative representations based on nominal prefixes.

Since in the DNGS standard the grids may contain information that links cells to the representation of geo-fields and geo-objects [9], this allows for the implementation of powerful systems and tools for the registration and dissemination of official information.

Geo-field-based information system: vectors of values are linked to the cells across the entire grid to model population density, temperature, etc.

Geo-object-based information system: attributes are linked to sets of pre-shaped cells (representing points, lines, or polygons [7]). This allows for modeling buildings, plots, addresses, watersheds, municipalities, etc.

Data openness is much simpler and more controlled in the DNGS standard than in conventional geoprocessing systems, mainly because the hierarchy allows for the selection of the most appropriate aggregation level. National themes and applications, highlighted by the Open Data Index [6], are references for DNGS applications.

From the aforementioned requirements, mathematical constraints emerged that complement the DNGS definition. For example, due to the multipurpose requirement, the congruence between levels (for cadastral and territorial demarcation applications) makes the use of hexagonal grids unfeasible, while neighborhood calculation (for logistical applications) excludes triangular grids, leaving only quadrilateral grids. Innovations [8] then emerged and became part of the standard:

Generalized-Geohash: encoding/decoding algorithms for cells in the hierarchical quadrilateral grid system, similar to Geohash, but sufficiently generalized to provide more alternatives for geocoding and space-filling curves (SFCs like Hilbert and Morton), with an efficient 64-bit internal representation. The internal representation ensures quadtree spatial indexing with bit-by-bit hierarchy and lexicographical ordering (compatible with the bit-string hierarchy of the grid).

Note: The geometric representation of 2 by 2 bits, through square cells, degenerates to rectangular cells when intermediate amounts of bits (1, 3, 5, …) are used to satisfy the bit-by-bit hierarchy. These intermediate grids allow for doubling the number of refinement levels of the grid (e.g., in Brazil, from 20 to 40).

Base 16h: an extension of the hexadecimal numerical representation system, which also allows the expression of leading zeros, thus allowing variable-length codes (bit strings). In practice, this enables humans to visualize quadtree identifiers in a readable and compact way, facilitating the interpretation of geocodes.

Optionally, countries with large territorial extensions, like Brazil, can represent geocodes in base 32 (5 bits per digit), using a subset of the complete grid.
At this moment (2024), the AddressForAll Institute is officially implementing the DNGS standard in the Republic of Cameroon and is proposing this standard to other countries. The table below details the characteristics of DNGS through the differences with DGGS:

Table 1: Differences between DGGS and DNGS grid specifications, emphasizing aspects like cell size standardization and the precision level that DNGS achieves compared to DGGS.

In the DNGS standard, the grid is composed of standardized size cells, ensuring accuracy down to the level of one square meter. This structure is illustrated in the powers of 2 table, covering levels 0 to 20 for Brazil and 0 to 18 for Colombia, enabling efficient and organized representation of geocodes.The DNGS standard seeks to incorporate as many definitions from the DGGS standard as possible. Compatibility breaks occur in only a few cases, limited to situations where DGGS relies on the notion of a global domain (or “model of the Earth”). When comparing the two, the constraints presented in Table 1, such as the requirement for a minimum resolution of one square meter, characterize DNGS as a specialization of DGGS. Referring to the normative text [1], OGC from 2017, only a few requirements are adapted, and consequently, only a few elements of the DGGS API [7] are altered in the DNGS API: “Requirement 1 – Core Data Model” is partially changed; “Requirement 2 – Reference Frame – Global Domain – Surface Area Equivalence” is partially changed, explicitly replacing “Global Domain” with “National Domain.” All other “requirements” remain unchanged. In those that use the term “initial discrete global,” it can be rewritten, without loss of generality, as in version 2 of the OGC standard, using the term “Domain” instead of “global.”

Figure 1: Scientific and logistical geocodes and their characteristics:

Finally, the DNGS standard allows each country to define the best grid system with the best geocoding system for its needs. Once the national equal-area projection, the type of SFC curve [8], and the type of geocode are chosen by sovereign decision of the country, the resulting DNGS system will be effective, interoperable, multipurpose, open, and still compatible with other countries.

REFERENCES
[1] “Topic 21: Discrete Global Grid Systems Abstract Specification”, version 1 from 2017. Requirements in “Annex A”. Available at: https://docs.ogc.org/as/15-104r5/15-104r5.html#ats
[2] “Geographic information — Discrete Global Grid Systems Specifications – Part 1: Core Reference System and Operations, and Equal Area Earth Reference System (ISO Standard 19170-1:2021)”, International Organization for Standardization (2021). Available at: https://www.iso.org/standard/32588.html
[3] “Disdyakis Triacontahedron DGGS”, ISPRS Int. J. Geo-Inf. 2020, 9(5), 315; urn:doi:10.3390/ijgi9050315
[4] “IBGE Statistical Grid in Compact Representation”, http://git.osm.codes/BR_IBGE
[5] “Brazilian Statistical Grid: a proposal for improvement oriented to hierarchical and multipurpose geocodes”, PROCEEDINGS OF THE 2ND BRAZILIAN SYMPOSIUM ON SPATIAL DATA INFRASTRUCTURES, 2020. https://inde.gov.br/images/inde/poster1/NovaGradeIBGE-poster-v2.pdf
[6] “Open Data Index”, Open Knowledge Foundation (2016). http://index.okfn.org/dataset.html
[7] “OGC Testbed-16: DGGS and DGGS API Engineering Report”, https://docs.ogc.org/per/20-039r2.html
[8] “Sfc4q classes”, Address For All, version 1.0.0 published in 2018, urn:doi:10.5281/zenodo.7112017 interface available at https://git.afa.codes/Sfc4q.
[9] “Towards a General Field model and its order in GIS”, Y. Liu, M. F. Goodchild, Q. Guo, Y. Tian, L. Wu (2008). urn:doi:10.1080/13658810701587727 (access).