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

作者简介:

李静(1972-), 女, 博士, 工程师, CCF高级会员, 主要研究领域为计算机图形学, 计算几何;王文成(1967-), 男, 博士, 研究员, 博士生导师, CCF高级会员, 主要研究领域为计算机图形学, 虚拟现实, 图像编辑

通讯作者:

李静, E-mail: jingli2018@ioz.ac.cn

中图分类号:

TP391

基金项目:

国家自然科学基金(61872348, 62072446, 31961143002)


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-09-02
  • 最后修改日期:2020-11-10
  • 录用日期:
  • 在线发布日期: 2022-07-15
  • 出版日期: 2022-09-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号