面向Hilbert八叉树的邻近格元计算算法
作者:吴宇豪; 曹雪峰
更新时间:
为了提高格元的计算效率,利用Hilbert码标记格元提出了一种相邻格元Hilbert码的快速计算方法。在Hilbert基元曲线的基础上,引入状态向量的概念,记录Hilbert曲线对同一父格元的所有子格元的填充顺序,从而建立状态向量的递阶演化和退化函数,得到状态向量在m阶和m+1阶曲线中的递阶映射关系,最后,利用状态向量及其递阶演化和退化函数实现了相邻节点的计算。结果表明,该算法的计算结果是正确的。状态向量的计算速度随着电平的增加而降低。4201个单元可以在ms的20级上计算,这对后续相邻单元的计算几乎没有影响。在计算指定级别上相同数量的相邻单元时,该算法的速度明显优于现有算法。在计算15层上百万个相邻单元时,该算法的速度约为现有算法的2.1~2.4倍。在数百万个不同级别的相邻小区的计算中,与现有Morton码转换算法算法相比,该算法的计算速度随着级别的增加而提高,在第20个级别上,该算法的效率提高了2.6倍。