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

空间填充曲线的空间排列码可实现多维空间到一维空间的线性映射,广泛应用于空间查询、空间索引、空间划分及影像编码等领域。Hilbert是一种优秀的空间填充曲线,具有非常好的空间聚集性。传统的Hilbert排列二进制循环位操作算法的算法复杂度为O(n²)。本文首先分析了Hilbert的分形自相似特性,推导并归纳出Hilbert状态转移矩阵,按位编码顺序定义了空间划分中的象限顺序,将Hilbert状态转移矩阵转换为C++中的数组运算,减少了Hilbert码计算过程中的嵌套循环及迭代处理,将算法复杂度降为O(n)。其次,采用位域共用体以数值计算替代了传统计算过程中的数值与字符串间类型转换,提高了Hilbert码生成算法的性能。最后,在C++环境下实现了Hilbert码快速生成算法的相关代码,并完成算法的正确性验证实验和性能对比实验。实验结果表明,本文提出的算法计算结果与二进制循环位算法的结果一致,在性能上本文算法与二进制循环位算法及空间层次分解算法相比有明显的优势。

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

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 partition, 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(n²). 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 binary 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.