面向Hilbert八叉树的邻近格元计算算法

摘要：

为提高线性八叉树邻近格元计算效率,利用Hilbert码标记格元,提出一种邻近格元Hilbert码快速计算方法.以Hilbert基元曲线为基础,引入状态向量的概念以记录Hilbert曲线对同属于一个父格元的所有子格元的填充顺序,从而建立状态向量的层级演进与退化函数,得到状态向量在m阶与m+1阶曲线中的层级映射关系,最终利用状态向量及其层级演进与退化函数实现邻近格元Hilbert码的计算.结果表明,所提算法计算结果正确;状态向量计算速度随层级提高而降低,在第20层级上1ms内可完成4 201个格元的计算,对后续邻近格元计算影响较小;在指定层级上同等数量的邻近格元计算中,该算法的速度明显优于现有Morton码转换算法,在第15层级上百万级规模的邻近格元计算中,该算法的速度约为现有Morton码转换算法的2.1～2.4倍;在不同层级的百万级规模邻近格元计算中,该算法计算速度相比现有Morton码转换算法的提升倍数随层级提高而增大,在第20层级上该算法的效率提升达到2.6倍.

关键词：Hilbert码、线性八叉树、邻近格元、状态向量

所属期刊栏目：47

分类号：P208(一般性问题)

资助基金：国家自然科学基金;国家自然科学基金

在线出版日期：2022-06-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：613-622