基于状态转移矩阵的Hilbert码快速生成算法  

An Algorithm for Hilbert Ordering Code Based on State-Transition Matrix

作　　者：李绍俊[1,2,3] 钟耳顺[1,3] 王少华[1,3] 张珣[1,2] 

机构地区：[1]中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101 [2]中国科学院大学,北京100049 [3]北京超图软件股份有限公司,北京100015

出　　处：《地球信息科学学报》2014年第6期846-851,共6页Journal of Geo-information Science

基　　金：国家科技支撑计划项目(2009AA12Z331;2011BAH06B03);交通运输部科技项目(2012-364-X04-102)

摘　　要：空间填充曲线的空间排列码可实现多维空间到一维空间的线性映射,广泛应用于空间查询、空间索引、空间划分及影像编码等领域。Hilbert是一种优秀的空间填充曲线,具有非常好的空间聚集性。传统的Hilbert排列二进制循环位操作算法的算法复杂度为O(n2)。本文首先分析了Hilbert的分形自相似特性,推导并归纳出Hilbert状态转移矩阵,按位编码顺序定义了空间划分中的象限顺序,将Hilbert状态转移矩阵转换为C++中的数组运算,减少了Hilbert码计算过程中的嵌套循环及迭代处理,将算法复杂度降为O(n)。其次,采用位域共用体以数值计算替代了传统计算过程中的数值与字符串间类型转换,提高了Hilbert码生成算法的性能。最后,在C++环境下实现了Hilbert码快速生成算法的相关代码,并完成算法的正确性验证实验和性能对比实验。实验结果表明,本文提出的算法计算结果与二进制循环位算法的结果一致,在性能上本文算法与二进制循环位算法及空间层次分解算法相比有明显的优势。Spatial ordering based on space-filling curves is a linear mapping method from multi-dimensional space to one-dimensional space, which has been widely used in spatial querying, spatial indexing, space parti-tion, image coding, and other related fields. The Hilbert curve is an excellent space-filling curve with remarkable spatial clustering properties. The traditional algorithm for Hilbert ordering code is based on binary circular bit manipulation, which has a complexity of O（n2） . In this article, the Hilbert state-transition matrix is generated based on the fractal self-similarity, the spatial quadrants are redefined by the sequence of spatial partition, and the Hilbert state-transition matrix is translated into arrays in C＋＋, all of which effectively reduce the nested loops and the iterations in the process of computing Hilbert code, thus decrease the complexity of algorithm to O（n） . Also, the bit field union type is used to avoid the type conversion from number to string in the process of Hilbert code computation, which brings numerical calculation into full play and improves the performance of the Hilbert coding algorithm. Finally, the C＋＋code for Hilbert code generating algorithm is given, and various tests have been conducted to verify the correctness of the algorithm and to compare the performance with regard to the bi-nary circular bit algorithm as well as the hierarchical space decomposition algorithm. Test results show that the algorithm demonstrates notable merits compared with the other two algorithms.

关 键 词：线性映射 空间填充曲线 状态转移矩阵 Hilbert排列码 QuickHilbertCode(QHC) Quick HILBERT CODE (QHC) 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] P208[自动化与计算机技术—计算机科学与技术]