基于六边形的自适应层次网格及其应用于点在球面多边形内的判断

Adaptive Hexagonal Hierarchical Grid for Point-in-spherical-polygon Tests

点在球面多边形内的判定计算,在全球数据处理中有大量的需求.为此,提出一种基于六边形的自适应层次网格,克服了已有六边形层次网格难以自适应划分组织的不足,并应用于点在球面多边形内的判定.首先,基于正二十面体对球面进行均匀划分,形成初始网格.然后,根据球面多边形的边与六边形网格的相交情况,对六边形网格单元进行自适应的细分处理,形成层次化的网格,使得各个没有细分的单元不包含或仅包含少量的多边形的边,并预计算这样单元本身或其中心点位于多边形内/外的属性.在此,记录相邻层次的六边形网格之间关联的点边面的拓扑结构,由此可快速地从初始网格检索到没有细分的网格单元.对于一个测试点,检索到其所在的没有细分的六边形单元,再依据该单元关于多边形的局部情况即可判定该测试点是否位于多边形内.实验表明,所提方法较以往方法具有更稳定而高效的判定性能.

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, precomputing 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.