Adaptive Hexagonal Hierarchical Grid for Point-in-spherical-polygon Tests
Author:
Affiliation:

Clc Number:

TP391

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Point-in-spherical-polygon tests are highly required in global data processing. For this reason, this study proposes an adaptive hexagonal hierarchical grid, which overcomes the difficulty of existing hexagonal hierarchical grids in adaptively subdividing grid cells, and applies it to point-in-spherical-polygon tests. First, the initial spherical hexagonal grid is built by uniformly partitioning a sphere using a regular icosahedron. Then, hierarchical grids are constructed by adaptively subdividing hexagonal cells according to whether a grid contains many polygon edges. As a result, the cells not subdivided contain no or only a few edges, called leaf cells. Finally, pre-computing is performed to determine the location attributes (inside/outside the polygon) of such cells or their center points. In the hierarchical structures, the topologies of related points, edges and faces between adjacent hexagonal grid levels are recorded, by which the leaf cells can be quickly located. For a test point, the leaf cell containing it is found quickly, and then whether it is located in the polygon is determined according to the local situation of the cell. Experimental results show that the proposed method has more stable and efficient performance than the existing methods.

    Reference
    Related
    Cited by
Get Citation

李静,王文成.基于六边形的自适应层次网格及其应用于点在球面多边形内的判断.软件学报,2022,33(9):3485-3497

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 02,2020
  • Revised:November 10,2020
  • Adopted:
  • Online: July 15,2022
  • Published: September 06,2022
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063