地球信息科学学报

地球信息科学学报 ›› 2014, Vol. 16 ›› Issue (6): 846-851.doi: 10.3724/SP.J.1047.2014.00846

• • 上一篇    下一篇

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

李绍俊1,2,3(), 钟耳顺1,3, 王少华1,3,*(), 张珣1,2   

  1. 1. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室,北京 100101
    2. 中国科学院大学,北京 100049
    3. 北京超图软件股份有限公司,北京 100015
  • 收稿日期:2014-03-14 修回日期:2014-05-05 出版日期:2014-11-10 发布日期:2014-11-01
  • 通讯作者: 王少华 E-mail:lishaojun@supermap.com;wangshaohua@supermap.com
  • 作者简介:

    作者简介：李绍俊(1978-),男,博士生,研究方向为GIS软件技术。E-mail:lishaojun@supermap.com

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

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

LI Shaojun1,2,3(), ZHONG Ershun1,3, WANG Shaohua1,3,*(), ZHANG Xun1,2   

  1. 1. State Key Laboratory of Resources and Environment Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China
    2. University of Chinese Academy of Sciences, Beijing 100039, China
    3. SuperMap Software Co., Ltd., Beijing 100015, China
  • Received:2014-03-14 Revised:2014-05-05 Online:2014-11-10 Published:2014-11-01
  • Contact: WANG Shaohua E-mail:lishaojun@supermap.com;wangshaohua@supermap.com
  • About author:

    *The author: WANG Jiacheng, E-mail：shanqiangw@fync.edu.cn

RichHTML

PDF (PC)

赞

被引次数

8

摘要：

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

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

Abstract:

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(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 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.

Key words: linear mapping, space- filling curves, Hilbert ordering code, state- transition matrix, Quick Hilbert Code (QHC)