PolarDB:GeoSOT geographic grid model based on GanosBase: UAV path planning

GanosBase geographic grid models

A geographic grid is a collection of polygonal grids that represent 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. This computation method typically employs a hierarchical division to process the surface of the Earth. By approximating the surface with polygonal grids of specified sizes, it combines geographic spatial positioning with feature description, while keeping the error within acceptable limits. Each grid is encoded to provide unique mappings. The 3D geographic grid also meshes and encodes the height dimension, in addition to the latitude and longitude dimensions.

GanosBase geographic grid engine currently supports two types of geographic grids: GeoSOT and H3.

• GeoSOT is a discrete, multi-scale location identification system developed based on a Chinese Earth subdivision theory.

• H3 is a two-dimensional geographic grid developed by Uber to cover the surface of the Earth. It utilizes hexagonal grids. For more information, see H3 geographic grid capabilities and best practices.

GanosBase supports degenerated grid computation, as shown in the following figure. It uses concise grid combinations to effectively represent spatial ranges by leveraging the hierarchical grid structure. In addition, the self-developed geographic grid indexing of GanosBase enables efficient grid encoding queries and accelerated aggregation.

Background information

New energy technologies have spurred the growth of the low-altitude economy and promoted it as a strategic industry. It is a comprehensive economic ecosystem that leverages low-altitude flight activities of manned and unmanned aircraft to foster integrated development across various sectors. Its applications cover traditional general aviation and drone-supported low-altitude production services. It is widely used in industries, agriculture, and services. The low-altitude economy is instrumental in shaping a modern industrial system and offers a very bright future.

Distinct from traditional surface activities, low-altitude activities are characterized by their three-dimensionality, regionality , and integration. These characteristics introduce a range of technical challenges that must be urgently addressed to ensure the safe and orderly conduct of low-altitude operations.

• Three-dimensionality: This is evident in three-dimensionality of activity space. The low-altitude airspace, typically below 1000 meters in true height, is defined by the specific height range designated according to the characteristics and needs of different regions. This enables the transition from a flat economy to a three-dimensional economy.

• Regionality: This is reflected by the regionality of the application scope. The low-altitude economy, which is characterized by small aircrafts, small routes, and small enterprises, exhibits the regional and localized nature. It is in contrast with the large-scale, integrated economies of aviation and high-speed rail.

• Integration: This pertains to the integration of operation modes. Unlike transportation-focused economies, the low-altitude economy emphasizes industry services. It adopts the combined model of industry and aviation to provide aerial solutions and support for related industries and to enhance efficiency and cost-effectiveness.

An analysis of low-altitude activities reveals the absence of a road network in the low-altitude area. The critical elements for the successful implementation of the low-altitude economy and regional safety include: ensuring the safe moving and arrival of low-altitude devices, the rational division of active cycles in low-altitude areas, and aircraft activity planning.

Features

GanosBase geographic grid engine provides grid-based path planning capabilities. It can be used in UAV path planning scenarios in complex environments using data structures such as digital elevation models (DEMs), digital surface models (DSMs), and oblique photography. The following functions can be used:

• ST_SetCost

  This function sets the travel cost for obstacles, which can be physical entities like buildings or spatial ranges such as radar scan areas or wind fields. Before using ST_SetCost, the spatial range of the obstacle must be converted into a grid array. Then, you can use it to set the travel cost.

• ST_3DGridPath

  As the core function of UAV path planning, ST_3DGridPath calculates the optimal three-dimensional grid path based on the start and end points, and passage cost data. It supports various path algorithms, movement methods, and distance calculation methods.

• ST_MatchGridLevel

  This function determines the highest available grid level based on the resolution of your terrain elevation data. In path calculations, do not use a grid level higher than the highest available grid level.

• ST_CostUnion

  This function merges all obstacle grid cost arrays. Merging degenerated grids is supported. It applies the maximum cost to overlapping grids and reserves it as the input for the final planned route.

Technical benefits

GanosBase GeoSOT geographic grid engine offers several technical benefits for UAV path planning:

• A unified standard data model within GanosBase for all input data, including rasters and surface grids.

• Complete data processing with internal functions of GanosBase, as well as a comprehensive set of path planning helper functions.

• Using degenerated grid technology to reduce storage overheads and enhance computation speed.

• Various parameter options for path planning algorithms, moving methods, and distance calculation methods to meet diverse needs.

Best practices

This following sections showcase the application of 3D path planning in real-world scenarios using oblique photography data from a specific park.

Recommended specifications

For optimal performance, the following PolarDB cluster specifications are recommended:

• Database engine: PolarDB for PostgreSQL (Compatible withOracle) 2.0

• Engine version: 2.0.14.23.1

• CPU: >= 4 cores

• Memory: >= 16 GB

• Disk capacity: >= 100 GB

• GanosBase version: >=6.7

Test data

Data import and processing

1. Install the required extensions for grid path planning.

   Note

   If exceptions occur when you execute the following statements to install the extensions, contact us for assistance.

   CREATE EXTENSION IF NOT EXISTS ganos_geomgrid CASCADE;
   CREATE EXTENSION IF NOT EXISTS ganos_utility CASCADE;

2. Import the test data stored in OSS using the ST_ImportOSGB function. For more information, see ST_ImportOSGB.

   SELECT 
     ST_ImportOSGB(
       'test_oblique',
       'OSS://<access_id>:<secrect_key>@<Endpoint>/<bucket>/path_to/file', 
       '{"parallel":16,"project":"building"}');

3. Convert a specific level of tiles into the GLB format and store them in the temporary table temp_glb, using the SfMesh type as the intermediate type.

   SELECT 
     ST_ImportGLB(
       'temp_glb', 
       ST_AsGLB(ST_Combine(tile)), 
       'temp_glb_1', 
       '{"ignore_texture":true,"ignore_normal":true}'
     ) 
   FROM test_oblique_tile WHERE lod = 19 AND project_name = 'building';

   Note

   • When calling the ST_ImportGLB function, ignore unnecessary textures (ignore_texture) and normals (ignore_normal).

   • Tiles at lod = 19 are sampled. You may select a tile level that suits your needs. Keep in mind that while a high tile level may result in long sampling times but high accuracy.

   • The common naming of skewed data is used in the test. For example, in Tile_+006_+004_L14_0.osgb, the tile level can be obtained from the file name.

   • When skewed data uses irregular naming conventions, the tile level may not be retrievable. In such cases, HERE lod = 19 can be replaced with WHERE children IS NULL to select the leaf node tiles with the highest precision as sample tiles.

4. Update the temporary data and project it onto the EPSG:4490 coordinate system:

   UPDATE temp_glb 
   SET 
     gltf_data = ST_Transform(
       ST_Flatten(
         ST_SetSrid(
           ST_Translate(
             ST_YupToZup(gltf_data), 
             x_off, y_off,z_off), 
           srid), 
         FALSE), 
       4490) 
   FROM 
     (SELECT 
         srid, 
         ST_X(anchor) x_off, 
         ST_Y(anchor) y_off, 
         ST_Z(anchor) z_off 
       FROM test_oblique WHERE project_name = 'building') metadata 
   WHERE gltf_id = 'temp_glb_1';

   The preceding statement performs the following operations:

   • When converting OSGB to GLB, the Y-axis serves as the vertical reference. To accurately transform the coordinates, the ST_YupToZup function must be invoked to reorient it to a Z-axis up configuration.

   • Skewed data typically uses relative coordinates, necessitating the use of the ST_Translate function to apply an offset to each point using an anchor point. This transforms each point's coordinate into an absolute coordinate. Subsequently, the correct SRID is established using the ST_SetSrid function.

     Note

     This operation requires the original skewed data to have a complete metadata description file (metadata.xml), otherwise the anchor point and coordinate system cannot be correctly obtained.

   • For SfMesh objects containing rotation matrices, pre-flattening (ST_Flatten) is required to apply the rotation matrix to the actual coordinates for coordinate projection.

   • Given that the grid's coordinate system is defined as CGC 2000, the function must be utilized to reproject each point to the EPSG:4490 coordinate system.

5. Convert intermediate data to geometric grid (GeomGrid).

   -- Create the grid table.
   CREATE TABLE IF NOT EXISTS building_grid
   (
      id   SERIAL,
      grid GEOMGRID,
      grid_type TEXT
   );
   -- Generate GeomGrid data and insert it into the grid table.
   INSERT INTO building_grid (grid, grid_type)
   SELECT grid, 'border'
   FROM
     (SELECT unnest(ST_As3DGrid(gltf_data, 24, TRUE)) grid
      FROM temp_glb WHERE gltf_id = 'temp_glb_1' ) tmp;
   -- Remove the temporary tables
   DROP TABLE temp_glb;

   The and ST_As3DGrid functions allow you to customize for precision level of the geographic grid based on specific requirements. A higher precision results in a more detailed grid, but also increases the sampling time significantly. The following table lists the approximate sizes of different grid levels.

   Level	Approximate size	Level	Approximate size	Level	Approximate size
   0	Global	11	29.6 km	22	15.5 m
   1	1/4 of the Earth	12	14.8 km	23	7.7 m
   2	-	13	7.4 km	24	3.9 m
   3	-	14	3.7 km	25	1.9 m
   4	-	15	1.8 km	26	1.0 m
   5	-	16	989.5 m	27	0.5 m
   6	890.5 km	17	494.7 m	28	24.2 cm
   7	445.3 km	18	247.4 m	29	12.0 cm
   8	222.6 km	19	123.7 m	30	6.0 cm
   9	111.3 km	20	61.8 m	31	3.0 cm
   10	59.2 km	21	30.9 m	32	1.5 cm

Grid display formats

• The generated grid can be exported in the GLB format for viewing the approximate shape.

  SELECT 
    ST_AsGLB(
      ST_ZupToYup(
        ST_3DRemoveDuplicateVertex(
          ST_MergeGeomByMaterial(
            ST_Triangulate(
              ST_Translate(
                ST_Transform(
                  ST_Flatten(
                    ST_Collect(
                      ST_AsMeshgeom(array (SELECT grid FROM building_grid WHERE grid_type = 'border')):: sfmesh[]),
                    TRUE
                  ), 
                  srid
                ), 
                - ST_X(anchor), - ST_Y(anchor), - ST_Z(anchor)
              )
            )
          ), 
          0.1
        )
      )
    ) 
  FROM test_oblique WHERE project_name = 'building';

  The preceding statement performs the following operations:

  • Convert the grid array to a MeshGeom array using the ST_AsMeshGeom function.

  • Convert the MeshGeom array type into an SFMesh array and combine them using or ST_Collect into a standalone SfMesh object.

  • Use ST_Flatten to simplify the aggregated object and use ST_Transform to project it to its original coordinate system.

  • Apply an offset to the entire aggregated object (ST_Translate) to reposition all coordinate points as relative to the origin.

  • Use the or ST_Triangulate function to triangulate the aggregated object, thereby streamlining subsequent processing steps.

  • Use the ST_MergeGeomByMaterial function in conjunction with the function ST_3DRemoveDuplicateVertex to effectively reduce data volume and alleviate rendering load.

  • Invoke the ST_YupToZup function to convert data from the left-handed to the right-handed coordinate system, as in GLTF. Then, use the ST_AsGLB function to export the data in GLB format.

  The following table compares the effects of different levels (using level 25 and level 24).

  Level	Result
  Raw data
  Level 25
  Level 24

• Use the following statement to generate data suitable for Cesium reading from grid objects:

  -- Create a function for easy calls.
  CREATE OR REPLACE FUNCTION GridToJson(geomgrid[])
  RETURNS json AS $$
  SELECT to_json(
          array_agg(
              json_build_object('center', array_to_json(array[ST_X(center), ST_Y(center), ST_Z(center)]), 
                             'size', array_to_json(array[ST_DistanceSpheroid(min_point, ST_Point(ST_X(max_point), ST_Y(min_point), 4490)), ST_DistanceSpheroid(min_point, ST_Point(ST_X(min_point), ST_Y(max_point), 4490)), z]))))
  FROM
    (SELECT ST_Transform(ST_PointZ(ST_X(st_centroid(geom)), ST_Y(st_centroid(geom)), (ST_ZMax(geom) + ST_ZMin(geom)) / 2, 4490), 4479) center,
            ST_SetSrid(BOX[0]::geometry, 4490) min_point,
            ST_SetSrid(BOX[1]::geometry, 4490) max_point,
            ST_ZMax(geom) - ST_ZMin(geom) z
     FROM
       (SELECT ST_ASBox(grid) BOX, ST_AsGeometry(grid) geom
        FROM (SELECT unnest($1) grid) a)b)c $$
  LANGUAGE 'sql';
  -- Call the GridToJson function to generate the result.
  SELECT GridToJson(array (SELECT grid
                       FROM building_grid WHERE grid_type = 'border')) ;

  Note

  The GridToJson function created by the above statement converts grid objects into a JSON array that includes the center position and size of each grid element. In this process, the ST_Transform function is called to convert the spatial reference system of the grid object from SRID 4490 to SRID 4479. As a result, the coordinate values of the center field in the JSON array is in SRID 4479. You can adjust this setting according to your needs.

  The returned result is a JSON array:

  [
    {
      "center": [-1583397.2647956165,5313841.088458569,3142388.7651142543],
      "size": [3.3600142470488144,3.848872238575258,3.3680849811062217]
    },
    ...
  ]

  • center: The center point of each grid projected to the EPSG:4479 coordinate system.

  • size: The approximate size of each grid in the latitude/longitude/height direction.

  In Cesium, the preceding data can be loaded in the following format:

  <!DOCTYPE html>
  <html lang="en">
  <head>
    <meta charset="utf-8">
    <script src="https://cesium.com/downloads/cesiumjs/releases/1.89/Build/Cesium/Cesium.js"></script>
    <link href="https://cesium.com/downloads/cesiumjs/releases/1.89/Build/Cesium/Widgets/widgets.css" rel="stylesheet">
    <style>
      html,
      body,
      #cesium_container {
        width: 100%;
        height: 100%;
        margin: 0;
        padding: 0;
        overflow: hidden;
        }
    </style>
  </head>
  <body>
    <div id="cesium_container"></div>
    <script>
      Cesium.Ion.defaultAccessToken = YOUR_CESIUM_TOKEN
      const viewer = new Cesium.Viewer('cesium_container', ['timeline', 'animation', 'infoBox', 'navigationHelpButton'].reduce((opts, opt) => (opts[opt] = false) || opts, {}))
      
      // Specify the grid to be displayed.
      const grids = [{ "center": [-1583315.44750805, 5313895.98214751, 3142303.525767127], "size":... 
      const add_grids = (grids, material) =>
        grids.forEach(({ center, size }) => viewer.entities.add({
            position: new Cesium.Cartesian3(...center),
            box: {dimensions: new Cesium.Cartesian3(...size),
              material, outline: true, outlineColor: Cesium.Color.BLACK}}))
        
      // Display the result in semi-transparent red.
  	add_grids(grids, Cesium.Color.RED.withAlpha(0.2))
        
      // Jump to the grid location
      viewer.zoomTo(viewer.entities)
    </script>
  </body>
  </html>

  Overlay the level 24 grid with skewed data. For the code to overlay skewed data, see Appendix. The following figure shows the result.

  

Grid path planning

After constructing the grid, a three-dimensional path based on the grid can be planned in the scenario using the ST_3DGridPath function with two points as the start and end points:

-- Define start point, end point, and searchable range.
WITH vals (start_p, end_p, box_range) AS (
  VALUES 
    (
      ST_PointZ(106.59182291666669, 29.70644097140958, 355.322855208642, 4490), 
      ST_PointZ(106.59244791666666, 29.707135415854022, 348.58669235736755, 4490), 
      'BOX3D(106.591788194444 29.7062326380763 341.85053662386713, 106.592899305556 29.7071701380762 362.0590251699541)' :: box3d
    )), 
border AS (
  SELECT DISTINCT grid, grid_type 
  FROM building_grid, vals 
  WHERE 
    -- Only calculate grids within the range.
    -- All geometric types involved in the calculation require a spatial reference of EPSG:4490.
    ST_3DIntersects(ST_SetSrid(box_range :: meshgeom, 4490), grid) 
    OR ST_3DContains(ST_SetSrid(box_range :: meshgeom, 4490), grid)
) 
SELECT ST_3DGridPath(start_p, end_p, box_range, array[ST_SetCost( array (SELECT grid FROM border WHERE grid_type = 'border' ), -1)], '{"algorithm":"astar","movement":"cross","distance":"euclidean"}') result 
FROM vals;

The ST_SetCost function sets the travel cost for the grid.

• The non-passable area is fixed at -1.

• If no other settings are required, the travel cost for any non-passable area is fixed at 1.

Use the GridToJson function to view the result in Cesium:

If the moving method is changed to strict_octothorpe, the result is shown in the following figure.

Multi-cost area grid path planning

After setting different travel costs for different areas in the passable area, the algorithm will choose the path with the lowest comprehensive cost. A high-cost travel area is added in the previous scenario to demonstrate the application of multi-cost grid path planning.

1. Insert the grid representing the high-cost travel area into the building_grid table:

   INSERT INTO building_grid (grid, grid_type)
   SELECT grid, 'risk_zone'
   FROM
     (SELECT unnest(ST_As3DGrid(ST_SetSrid('BOX3D(106.59192708333332 29.706614582520686 341.8505366235368, 106.59220486111111 29.706892360298472 365.4271128197744)' :: box3d :: meshgeom, 4490), 24)) grid) tmp;

   The area shape is as shown in the following figure (orange part).

   

   Note

   The high-cost travel area grid overlapping with the non-passable grid will also be regarded as a non-passable grid.

2. Execute path planning.

   WITH vals (start_p, end_p, box_range) AS (
     VALUES 
       (
         ST_PointZ(106.59182291666669, 29.70644097140958, 355.322855208642, 4490), 
         ST_PointZ(106.59244791666666, 29.707135415854022, 348.58669235736755, 4490), 
         'BOX3D(106.591788194444 29.7062326380763 341.85053662386713, 106.592899305556 29.7071701380762 362.0590251699541)' :: box3d
       )), 
   border AS (
     SELECT DISTINCT grid, grid_type 
     FROM building_grid, vals 
     WHERE 
       ST_3DIntersects(ST_SetSrid(box_range :: meshgeom, 4490), grid) 
       OR ST_3DContains(ST_SetSrid(box_range :: meshgeom, 4490), grid)
   ) 
   -- Set the travel cost of risk_zone to 2.
   SELECT ST_3DGridPath(start_p, end_p, box_range, array[ST_SetCost( array (SELECT grid FROM border WHERE grid_type = 'border' ), -1), ST_SetCost( array (SELECT grid FROM border WHERE grid_type = 'risk_zone' ), 2)], '{"algorithm":"astar","movement":"cross","distance":"euclidean"}') result 
   FROM vals;

   The following figure shows the resulting path.

   

   

   Compare this path with the one without a high-cost travel area (purple path).

   

Summary

Utilizing the GanosBase geographic grid engine, UAV path planning can be accomplished with minimal coding. As the world's first professional spatial database, GanosBase broadens the scope of spatial data to encompass air, ground, indoor and outdoor, above and under the ground, dynamic and static areas. It offers a spatio-temporal processing framework for the physical world's digitization from the underlying database system level. In the future, GanosBase will continue to provide more efficient in-database spatial analysis and visualization capabilities, and promote the application of spatial information across industries towards a seamless integration of visualization and computation.

Appendix

Create a simple backend service using Node.js to proxy 3DTiles requests and display the results with Cesium as the frontend framework.

1. In a custom directory, write the dependency file package.json:

   {
     "dependencies": {
       "koa": "^2.14.2",
       "koa-router": "^12.0.0",
       "koa-send": "^5.0.1",
       "pg": "^8.10.0"
     }
   }

2. Run npm install in the directory to install dependencies. Create a Node.js script file index.js in the same directory:

   const Koa = require('koa');
   const Send = require('koa-send');
   const Router = require('koa-router');
   const router = new Router()
   const { Pool } = require('pg');
   const pool = new Pool({ user: <YOUR_USER>, host: <YOUR_HOST>, database: <YOUR_DB_NAME>, port: <YOUR_PORT> });
   
   const TABLE_NAME = 'test_osgb'
   const PROJECT_NAME = 'prj1'
   
   router.get('/', (_) => Send(_, '/index.html'))
   
   /* get metadata of current project */
   router.get('/project', async (ctx) => {
     const sql = `SELECT (REGEXP_MATCHES(ST_ASTEXT(ST_TRANSFORM(ANCHOR,4326)), 'POINT Z \\((.*?)\\)'))[1] _ANCHOR, PROJECT_ID FROM ${TABLE_NAME} WHERE PROJECT_NAME='${PROJECT_NAME}';`
     const { rows: [{ _anchor, project_id }] } = await pool.query(sql)
     const anchor = _anchor.split(' ').map(x => parseFloat(x))
     const url = `/tileset/${project_id}/${project_id}`
     ctx.body = { url, anchor }
   })
   
   router.get('/tileset/:project_id/:uid', async (ctx) => {
     const { params: { project_id, uid } } = ctx
     const sql = `SELECT TILESET FROM ${TABLE_NAME}_TILESET WHERE PROJECT_ID=$1::UUID AND UID=$2::UUID;`
     const { rows: [{ tileset }] } = await pool.query(sql, [project_id, uid])
     ctx.body = tileset
   })
   
   router.get('/b3dm/:project_id/:uid', async (ctx) => {
     const { params: { project_id, uid } } = ctx
     const sql = `SELECT ST_ASB3DM(TILE) TILE FROM ${TABLE_NAME}_TILE WHERE PROJECT_ID=$1::UUID AND UID=$2::UUID;`
     const { rows: [{ tile }] } = await pool.query(sql, [project_id, uid])
     ctx.body = tile
   })
   
   new Koa().use(router.routes()).listen(5500, '0.0.0.0');

3. Create the HTML file index.html in the same directory.

   <!DOCTYPE html>
   <html lang="en">
   
   <head>
     <meta charset="utf-8">
     <script src="https://cesium.com/downloads/cesiumjs/releases/1.89/Build/Cesium/Cesium.js"></script>
     <link href="https://cesium.com/downloads/cesiumjs/releases/1.89/Build/Cesium/Widgets/widgets.css" rel="stylesheet">
     <style>
       html,
       body,
       #cesium_container {
         width: 100%;
         height: 100%;
         margin: 0;
         padding: 0;
         overflow: hidden;
       }
     </style>
   </head>
   
   <body>
     <div id="cesium_container"></div>
     <script>
       Cesium.Ion.defaultAccessToken = <SET_YOUR_OWN_TOKEN_HERE>
       const disable_opt = ['timeline', 'animation', 'infoBox', 'navigationHelpButton']
         .reduce((opts, opt) => (opts[opt] = false) || opts, {})
       const viewer = new Cesium.Viewer('cesium_container', disable_opt)
       fetch('/project')
         .then(res => res.json())
         .then(({ anchor, url }) => {
           const position = Cesium.Cartesian3.fromDegrees(...anchor)
           const modelMatrix = Cesium.Transforms.eastNorthUpToFixedFrame(position)
           const tileset = new Cesium.Cesium3DTileset({ url, modelMatrix })
           tileset.readyPromise.then(() => viewer.zoomTo(tileset))
           viewer.scene.primitives.add(tileset)
         })
     </script>
     </div>
   </body>
   
   </html>

4. Start the service by run the command below in the same directory, then enter localhost:5500 in the browser to view the data.

   node index.js