CAJ | 학술논문

空间填充曲线的空间排列码可实现多维空间到一维空间的线性映射，广泛应用于空间查询、空间索引、空间划分及影像编码等领域。Hilbert是一种优秀的空间填充曲线，具有非常好的空间聚集性。传统的Hilbert排列二进制循环位操作算法的算法复杂度为O(n2)。本文首先分析了Hilbert的分形自相似特性，推导并归纳出Hilbert状态转移矩阵，按位编码顺序定义了空间划分中的象限顺序，将Hilbert状态转移矩阵转换为C++中的数组运算，减少了Hilbert码计算过程中的嵌套循环及迭代处理，将算法复杂度降为O(n)。其次，采用位域共用体以数值计算替代了传统计算过程中的数值与字符串间类型转换，提高了Hilbert码生成算法的性能。最后，在C++环境下实现了Hil-bert码快速生成算法的相关代码，并完成算法的正确性验证实验和性能对比实验。实验结果表明，本文提出的算法计算结果与二进制循环位算法的结果一致，在性能上本文算法与二进制循环位算法及空间层次分解算法相比有明显的优势。
공간전충곡선적공간배렬마가실현다유공간도일유공간적선성영사，엄범응용우공간사순、공간색인、공간화분급영상편마등영역。Hilbert시일충우수적공간전충곡선，구유비상호적공간취집성。전통적Hilbert배렬이진제순배위조작산법적산법복잡도위O(n2)。본문수선분석료Hilbert적분형자상사특성，추도병귀납출Hilbert상태전이구진，안위편마순서정의료공간화분중적상한순서，장Hilbert상태전이구진전환위C++중적수조운산，감소료Hilbert마계산과정중적감투순배급질대처리，장산법복잡도강위O(n)。기차，채용위역공용체이수치계산체대료전통계산과정중적수치여자부천간류형전환，제고료Hilbert마생성산법적성능。최후，재C++배경하실현료Hil-bert마쾌속생성산법적상관대마，병완성산법적정학성험증실험화성능대비실험。실험결과표명，본문제출적산법계산결과여이진제순배위산법적결과일치，재성능상본문산법여이진제순배위산법급공간층차분해산법상비유명현적우세。
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.