DNGS - osm-codes/BR_new GitHub Wiki

The document appears to be a technical paper discussing a proposed adaptation of the ISO 19170-1 standard for Discrete Global Grid Systems (DGGS) to meet the requirements of National Spatial Data Infrastructures (NSDIs). The proposal introduces the Discrete National Grid System (DNGS) as a variant better suited for national applications, such as census, postal services, and territorial demarcation.

DNGS STANDARD: A PROPOSAL FOR ADAPTING THE ISO 19170-1 (DGGS) STANDARD TO NSDI REQUIREMENTS

Authors: Peter de Padua Krauss

Thierry Alain Jean

Marco Aurelio Painelli Marsitch

  • AddressForAll Institute of Geo-Social Technologies
  • Honorary Member
  • Email: [email protected]

Introduction

National hierarchical grid systems like the "Ordnance Survey National Grid" of England have been in use for decades. Some of these systems have proven to be more versatile when their cells are identified by short, readable labels known as "hierarchical geocodes." When both the grid standard and the geocodes are developed together, they can meet application requirements more effectively.

These systems, however, were created before the digital era and lack the digital representation of their geocodes, which is essential for geographic databases that use them as spatial indexers—known as SFCs (space-filling curves) and quadtrees. Hierarchical grids with efficient indexers enable a broader range of digital applications. Spatial indexers replace the continuous two-dimensional coordinate with a discrete coordinate, represented by a one-dimensional index, typically a positive 64-bit integer.

A significant technological advancement for this type of hierarchical grid occurred in the 2000s, driven by "Digital Earth" initiatives, resulting in substantial academic and industrial investments. These advancements were only systematized in 2017 by the OGC (Open Geospatial Consortium) in the “Topic 21” specification. Later, after gaining wider consensus around the model, the ISO 19170-1:2021 standard (DGGS - Discrete Global Grid System) was established, solidifying 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 precision across all nations. It is important to note that promising proposals, such as the Disdyakis Triacontahedron, still require years of technological development and consensus. As a result, the DGGS is not yet suitable for use by official statistical organizations responsible for national censuses or applications related to land demarcation.

Challenges and Proposals for Adapting DGGS

There is a wide variety of technologies adhering to the DGGS, but these are still quite recent, and few are open and free of patents, amplifying the issue of compatibility among different implementations of this standard. Another obstacle to using DGGS solutions is the adoption of geocodes: the ISO standard is silent on this aspect. Standardized national geocodes are needed for data visualization, preliminary land demarcation in digital registries, general human communication (e.g., address points, postal codes, or disaster zoning), as well as interoperability between geocodes and other applications.

Postal codes and traditional national grids, like that of England, highlight the importance of people being familiar with geocodes, allowing them to write or memorize the corresponding cells. Citizens in each nation need short, readable geocodes to memorize and include them in written or verbal communications. These geocodes should be the same or at least interoperable with a common national reference grid.

For this reason, we believe that every nation, within its NSDI (National Spatial Data Infrastructure), should also standardize and ensure interoperability with a hierarchical equal-area grid system, complete with standardized geocodes. In Brazil, there is an official equal-area projection instituted by the IBGE (Brazilian Institute of Geography and Statistics) in 2016 to support its Statistical Grid. However, the grid was designed solely to aggregate data from the 2010 Census 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.

The AddressForAll Institute, aware of the relevance of the DGGS standard and the barriers to its use, developed a new standard tailored to the specific needs of each nation. 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; it only needs to be suitable for national applications such as census and multi-purpose registries. The pillars of the DNGS standard are:

  1. Multi-purpose: Versatility to meet the main requirements of postal, logistical, census, judicial, environmental, or municipal public databases. The diversity of themes and applications is a core feature, similar to the DGGS.
  2. National Equal-Area Projection: By replacing the global scale (from the DGGS) with the national scale in the DNGS, automatic adoption of an already established national standard with greater precision is possible. This ensures versatility, similar to the DGGS, and makes statistical operations and broad comparison functionalities feasible.
  3. Hierarchical Grid System: From the smallest to the largest grid sizes, starting with 1 m² cells and progressing by powers of two (4 m², 16 m², 64 m², and so on) until covering the entire national territory. This metric requirement ensures comparability between cells from different nations. Powers of two are more suitable for digital environments with bit-by-bit hierarchy (quadtree). This also allows compact human representation through bases 4, 8, 16, 32, or 64, compliant with the RFC-4648 standard and its extension.
  4. Congruency: Child cells are fully congruent with parent cells, enabling multi-scale polygon representation (quadtree) and consistency in land demarcation applications.
  5. Readable Geocodes: Human-readable cell identifiers, short enough to be memorized and compatible with their hierarchical representation. Cell congruency ensures digit-by-digit hierarchy, allowing named polygons (e.g., municipalities) to support alternative representations based on nominal prefixes.

As in the DNGS standard, grids can include information linking cells to representations of geofields and geo-objects, enabling powerful systems and tools for the registration and dissemination of official information.

Information Systems and DNGS Implementation

In the DNGS standard, grids can contain information linking cells to representations of geofields and geo-objects, which allows for the implementation of robust systems and tools for the registration and dissemination of official information:

  1. Geofield-based Information System: Vectors of values are linked to all grid cells to model various attributes such as population density, temperature, etc.
  2. Geo-object-based Information System: Attributes are associated with sets of pre-shaped cells (representing points, lines, or polygons). This allows modeling buildings, plots, addresses, watersheds, municipalities, etc.

The data openness is much simpler and more controlled in the DNGS standard than in conventional geoprocessing systems, mainly because the hierarchy allows for selecting the most appropriate aggregation level. The national themes and applications highlighted by the Open Data Index serve as references for DNGS applications.

Mathematical Constraints and Innovations in DNGS

From the requirements mentioned above, mathematical constraints emerged that complement the DNGS definition. For example, due to the need for multi-purpose applications, congruency between levels (for cadastral and territorial demarcation applications) makes the use of hexagonal grids unfeasible, while neighborhood calculations (for logistical applications) exclude triangular grids, leaving only quadrilateral grids. Consequently, innovations emerged that became part of the standard:

  1. Generalized-Geohash: Algorithms for encoding/decoding cells of the hierarchical quadrilateral grid system, similar to Geohash, but generalized enough to offer more alternatives for geocoding and space-filling curves (SFCs such as Hilbert and Morton) with efficient internal 64-bit representation. The internal representation ensures quadtree spatial indexing with bit-by-bit hierarchy and lexicographic ordering (compatible with the grid's bit-string hierarchy). Note: The 2-by-2 bit geometric representation through square cells degenerates to rectangular cells when intermediate quantities of bits (1, 3, 5, ...) are used to satisfy bit-by-bit hierarchy. These intermediate grids allow doubling the number of grid refinement levels (e.g., from 20 to 40 levels in Brazil).

  2. Base 16h: An extension of the hexadecimal numeric representation system that also allows for the expression of leading zeros, making variable-length bit string codes feasible. In practice, this enables humans to view quadtree identifiers in a readable and compact way, facilitating the interpretation of geocodes. Optionally, countries with large territories, like Brazil, can represent geocodes in base 32 (5 bits per digit) using a subset of the complete grid.

Current Implementation and International Proposal

As of 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

In the DNGS standard, the grid is composed of standardized-size cells, ensuring precision down to one square meter. This structure is illustrated in the table of powers of two, covering levels from 0 to 20 for Brazil and from 0 to 18 for Colombia, allowing for an 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 a few cases, limited to situations where the DGGS refers to the concept of a global domain ("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. Using the normative text from the 2017 OGC, few requirements undergo adaptation, and consequently, few elements of the DGGS API are modified in the DNGS API: “Requirement 1 - Core Data Model” is partially modified; “Requirement 2 - Reference Frame - Global Domain – Surface Area Equivalence” is partially modified by explicitly substituting “Global Domain” with “National Domain.” All other "requirements" are maintained. Where the term “initial discrete global” is used, it can be rewritten without loss of generality, as in version 2 of the OGC standard, using the term “Domain” instead of "global."

Conclusion

In conclusion, the DNGS standard allows each country to define the best grid system with the optimal geocode system to suit its needs. Once the national equal-area projection, the type of space-filling curve (SFC), and the type of geocode are chosen as a sovereign decision of the country, the resulting DNGS system will be effective, interoperable, multi-purpose, open, and still compatible with other countries.

References

  1. “Topic 21: Discrete Global Grid Systems Abstract Specification" version 1 of 2017. Requirements in “Annex A.” Available at OGC Documentation.
  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 ISO.
  3. “Disdyakis Triacontahedron DGGS” ISPRS Int. J. Geo-Inf. 2020, 9(5), 315; DOI.
  4. “Grade Estatística IBGE em Representação Compacta” IBGE Documentation.
  5. “Grade estatística do Brasil: uma proposta de melhora orientada a geocódigos hierárquicos e multifinalitários” Proceedings of the 2nd Brazilian Symposium on Spatial Data Infrastructures 2020. INDE.
  6. “Open Data Index” Open Knowledge Foundation (2016). Open Data Index.
  7. “OGC Testbed-16: DGGS and DGGS API Engineering Report” OGC Documentation.
  8. “Sfc4q classes” AddressForAll version 1.0.0 published in 2018. DOI, interface available at Git AddressForAll.
  9. “Towards a General Field model and its order in GIS” Y. Liu, M. F. Goodchild, Q. Guo, Y. Tian, L. Wu (2008). DOI.

Figures and Tables

  • Figure 1: Scientific and logistical geocodes and their characteristics.

image2

  • 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.

artigo-tab1-En

Implementation Note: As of now (2024), the AddressForAll Institute is advancing the official implementation of the DNGS standard in Cameroon and actively proposing its adoption to other nations.