PolarDB:Geographic grid model

Overview

The geographic grid model is a unified and simple geographic space division and positioning reference system. The model continuously divides the ground area by specified longitude and latitude or ground distance, and controls the spatial uncertainty to an acceptable extent to form regular polygons. A polygon is called a grid cell and is used to form a hierarchical multi-level grid system. This helps achieve the discretization and unified encoding of ground space.

GanosBase GeomGrid is a spatio-temporal engine extension of PostgreSQL (PolarDB for PostgreSQL). GanosBase GeomGrid is used to express and process geographic grids. This model provides the spatial operation functions and spatial relationship identification functions for the geographic grid and geographic grid array data types, and the conversion functions for other data types in GanosBase.

GeomGrid refers to the geographic grid data type in GanosBase. A geographic grid is a set of polygonal grid cells that reproduce the surface of the earth. It can be used to represent the location information of ground features in geographic space and integrate other types of spatio-temporal data. Each grid cell is encoded to provide one-to-one mappings. The 3D geographic grid subdivides and encodes not only the latitude and longitude, but also the height dimension.

GanosBase GeomGrid supports GeoSOT and H3 geographic grids. GeoSOT is a Chinese-developed Earth subdivision theory, based on which a discrete, multi-scale location identification system is developed. H3 is a two-dimensional geographic grid developed by Uber to cover the global surface. H3 uses hexagonal grid cells.

Features

GeomGrid supports the import and export, spatial operations, and spatial relationship identification of geographic grids.

• GeomGrid supports converting data types such as Text, Bytea, Geometry, Meshgeom, Sfmesh, and Vomesh to the GeomGrid type.

• GeomGrid supports spatial query operations such as obtaining grid levels and coordinates, calculating parent and child nodes, merging grids, and dividing grids.

• GeomGrid supports identifying the spatial relationship between GeomGrid and other data types such as Geometry, Meshgeom, Sfmesh, Vomesh, and GemoGrid.

For more information, see GeomGrid SQL reference.

Scenarios

GanosBase GeomGrid is applicable to the following business scenarios:

• Grid query

  GanosBase GeomGrid can be used to query whether a specific grid or grid array intersects with the grids stored in the database. Degenerated grids are supported. You can query the parent grid or child grid of a specific grid. For example, when you park a shared bicycle, your position is converted into the grid code that is used to query the database that stores the grid codes of parking areas to identify the nearest parking area. Grid query can also be used to associate different layers and store the objects of different layers in the grid. Then you can query the objects of all associated layers based on a specific grid.

• Grid aggregation

  In industries such as logistics and delivery service, spatial and temporal elements are often calculated based on grids. For example, the trajectory data of ships or vehicles can be aggregated into grids to generate a heatmap. The trajectories are converted into grids, and then the number of trajectories in each grid is used as heat to generate the heatmap. You can also distribute the population data of each street to grids for visualization.

  

• Grid pathfinding

  You can use 3D grids for path planning in complex environments for unmanned aerial vehicles (UAVs). You can set the traversing cost of spatial obstacles in the grids and obtain the path based on pathfinding algorithms.

  

Overview

Based on the theoretical framework of GeoSOT and H3, GanosBase GeomGrid supports GeoSOT by using the GeomGrid data type and H3 as the H3Grid data type.

Encoding

GeoSOT

GeoSOT transforms the Earth into a plane by using simple projection. The size of the plane is expanded from 180°×360° in the Earth surface space to 512°×512°, which is the 0th layer of the spatial division. The center point of the layer coincides with the intersection of the equator and the prime meridian. By using the quad-tree recursive subdivision, the 0th layer is subdivided to level 32. In this way, integer bisections can be performed on the latitude and longitude of the Earth. The entire Earth space is divided into multilevel grids of whole degrees, whole minutes, and whole seconds. The size of the grids ranges from the entire globe to several centimeters.

The code of a GeoSOT 2D grid is a quaternary number that can be up to 32 bits. The 1st to 9th bits describe the degree of the grid. The 10th to 15th bits describe the minute of the grid. The 16th to 21st bits describe the second of the grid. The 22nd to 32nd bits describe the levels of the grid that are lower than second. The code length indicates the grid level.

Longitude and latitude values follow the A°B'C.D" format. The degree value is converted from a decimal number to an 8-bit binary number A2. The minute value is converted from from a decimal number to a 6-bit binary number B2. The second value is converted from a decimal number to a 6-bit binary number C2. The fractional part of the second value is converted from a decimal number to a 11-bit binary number D2. The binary numbers A2, B2, C2, and D2 are sequentially concatenated to form a 31-bit binary number. The latitude value is placed before the longitude value to generate a 62-bit Morton code. G0, G1, G2, or G3 is added before the Morton code to form the grid code. G0 indicates the northeast hemisphere. G1 indicates the northwest hemisphere. G2 indicates the southeast hemisphere. G3 indicates the southwest hemisphere.

The GeoSOT 3D grid adds the height dimension based on the 2D grid. To ensure that the division of the height dimension is consistent with that of the longitude and latitude, each height grid corresponds to a 1° ground surface grid. The height dimension is divided into 256 grids from the ground surface up to the air and another 256 grids from the ground surface down to the Earth's core. Then integer bisections are performed to obtain the number of levels at the vertical direction. The number is converted into a binary string that is used together with the latitude and longitude values to generate a Morton code, which is the 3D grid code.

H3

H3 uses a sphere-circumscribed icosahedron for projection. The icosahedron in the following figure contains 20 spherical triangles and 12 vertices. It is called a spherical icosahedron.

As shown in the following figure, H3 creates hexagon grids on each triangular surface in the same arrangement and divides the globe into 122 base cells. H3 then creates higher precision hexagon grids in each cell.

H3 recursively divides each of the 122 base cells into 7 cells. The following figure shows how the base cell 20 is divided.

An H3 code can be up to 63 bits and can be represented by a long integer. The code is usually serialized as a hexadecimal string. The bit layout of the H3 encoding provides a compact structure for storing information about a given index and defining its geographic location. See the following example:

Indexes

Indexes are used to accelerate queries by organizing data into a search tree to avoid the latency caused by global sequential scans when querying a large amount of data. GanosBase GeomGrid supports the following types of index:

Overview

This section describes how to use the GanosBase GeomGrid engine, including extension creation, table creation, data insertion, grid code calculation, index creation, and queries.

Syntax

• Create an extension.

  CREATE EXTENSION Ganos_GeomGrid CASCADE;

  Note

  • Create the extension in the public schema to avoid permission issues.

    CREATE EXTENSION Ganos_GeomGrid WITH schema public cascade;

  • If errors indicating dependent extensions (such as ganos_sfmesh) do not exist when you execute the preceding statement, contact us.

• GeoSOT grid operations.

  • Create a table that contains grid codes.

    -- Create a table for a geometry object.
     CREATE TABLE t_grid(id integer,
                         geom geometry,  -- A geometry object.
                         grid1 geomgrid[], -- A grid code with a precision of 1.
                         grid2 geomgrid[], -- A grid code with a precision of 2.
                         grid3 geomgrid[] -- A grid code with a precision of 3.
                        );

  • Insert data into the table.

    -- Insert point data.
     INSERT INTO t_grid(id, geom)
     VALUES (1, ST_GeomFromText('POINT(116.31522216796875 39.910277777777778)', 4490)),
            (2, ST_GeomFromText('POINT(116.31522217796875 39.910277776777778)', 4490)),
            (3, ST_GeomFromText('POINT(116.31522217797875 39.910277776787778)', 4490)),
            (4, ST_GeomFromText('POINT(116.31522227796875 39.910277776775778)', 4490));
    
     -- Insert surface data.
     INSERT INTO t_grid(id, geom) VALUES(5, 'SRID=4490;POLYGON((-0.08077 -0.02814, 0.0482 -0.03, 0.07426 0.03724, -0.08077 -0.02814))'::geometry);
    
     -- Insert 3D data.
     INSERT INTO t_grid(id, geom) VALUES(6, 'SRID=4490;CIRCULARSTRING Z (-63.597471 44.8071 20,-63.597 44.807 0,-63.5974 44.807 40)'::geometry);

  • Calculate the grid code of the table.

    -- Create grid codes of different precision levels.
     UPDATE t_grid
     SET grid1 = ST_AsGrid(geom, 10),
         grid2 = ST_AsGrid(geom, 15),
         grid3 = ST_AsGrid(geom, 26);
    
     -- Generate a degenerated grid code.
     UPDATE t_grid SET grid1 = st_asgrid(geom, 18, true) WHERE id = 5;
    
     -- Generate a 3D grid code.
     UPDATE t_grid SET grid1 = st_as3dgrid(geom, 25) WHERE id=6;

  • Create an index on the grid code.

    -- Create GIN indexes on grid codes of different precision levels.
     CREATE INDEX idx_grid_gin1
     ON t_grid
     USING GIN(grid1);
    
     CREATE INDEX idx_grid_gin2
     ON t_grid
     USING GIN(grid2);
    
     CREATE INDEX idx_grid_gin3
     ON t_grid
     USING GIN(grid3);

  • Query data

    -- Query data that is included in a grid.
     SELECT id
     FROM t_grid
     WHERE grid2 = ARRAY[ST_GridFromText('G001310322230230')];
    
     -- Query data that intersects with a grid.
     SELECT id
     FROM t_grid
     WHERE grid3 @> ARRAY[ST_GridFromText('G00131032223023031031033223')];
    
     -- Query data that intersects with more than one grid.
     SELECT id
     FROM t_grid
     WHERE grid3 && ARRAY[ST_GridFromText('G00131032223023031031211001'),
                              ST_GridFromText('G00131032223023031031211111')];
    
     -- Query data that intersects with more than one geometry in a grid.
     SELECT id
     FROM t_grid
     WHERE grid3 &&
     ST_AsGrid(
       ST_GeomFromText('LINESTRING(116.31522216796875 39.910277777777778, 116.31522217797875 39.910277776787778)', 4490), 26);

• H3 grid operations.

  • Create a table.

     CREATE TABLE h3_grid(
      id integer,
      geom geometry,  -- Create a table for a geometry object.
      h3 h3grid[] -- H3 object type.
     );

  • Insert data into the table.

     INSERT INTO h3_grid VALUES (1, 'POINT(102.5 25.7)'::geometry);
     INSERT INTO h3_grid VALUES (2, 'POLYGON((-0.08077 -0.02814, 0.0482 -0.03, 0.07426 0.03724, -0.08077 -0.02814)'::geometry);

  • Calculate the H3 grid code.

    -- Regular grid code.
     UPDATE h3_grid SET h3 = ST_AsH3Grid(geom, 7);
    
     -- Degenerated grid code.
     UPDATE h3_grid SET h3 = ST_AsH3Grid(geom, 7, true);

  • Create an index.

    CREATE INDEX h3_grid_btree ON h3_grid(h3);

  • Query data.

    -- Display H3 code.
     SELECT st_astext(h3[1]) FROM h3_grid;
    
     -- Query data.
     SELECT * FROM h3_grid WHERE h3 > ARRAY[ST_H3FromText('884a126689fffff')];

• Delete the extension (optional)

  DROP EXTENSION Ganos_GeomGrid CASCADE;

SQL statements

For more information about SQL statements, see GeomGrid SQL reference.