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

摘要

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