一种基于空间层次分解的Hilbert码生成算法

摘要

基于Hilbert空间填充曲线的Hilbert空间排列码是一种优秀的线性映射方法,故在空间查询与索引中得到广泛应用.传统的Hilbert排列码算法是基于Morton码上的二进制位操作,复杂度为O(n2),在Hilbert空间填充曲线的空间层次分解特征的基础上,提出了一种新的Hilbert排列码生成算法,即通过栅格空间层次分解与构造区域状态转移向量,以递归的方式来生成Hilbert码,其复杂度为O(n),较之传统算法显著地提高了效率.在此基础上,结合点特征空间区域查询方法,又进一步阐述了以Hilbert空间排列码作为地址码的二叉平衡排序树空间索引方法的应用特点,并结合实例进行了讨论.