摘要
基于 Hilbert空间填充曲线的 Hilbert空间排列码是一种优秀的线性映射方法 ,故在空间查询与索引中得到广泛应用 .传统的 Hilbert排列码算法是基于 Morton码上的二进制位操作 ,复杂度为 O(n2 ) ,在 Hilbert空间填充曲线的空间层次分解特征的基础上 ,提出了一种新的 Hilbert排列码生成算法 ,即通过栅格空间层次分解与构造区域状态转移向量 ,以递归的方式来生成 Hilbert码 ,其复杂度为 O(n) ,较之传统算法显著地提高了效率 .在此基础上 ,结合点特征空间区域查询方法 ,又进一步阐述了以 Hilbert空间排列码作为地址码的二叉平衡排序树空间索引方法的应用特点 。
Hilbert spatial ordering based on Hilbert Peano curves is an excellent linear mapping method, and gets wide applications in spatial querying and spatial indexing. The traditional algorithm for Hilbert ordering code is based on binary bit manipulation on Morton code. It has a complexity of O(n 2 ). In this paper, the author set forward a new generating algorithm for Hilbert ordering code, which is implemented by raster space recursive decomposition and regional phase shifting vector, and has a complexity as O(n) .Experiments have valideted the efficiency of the new algorithm. The algorithm has been applied in a feature based non planar data model for urban traffic networks to generate the address code so as to facilitate the point feature dynamic indexing based on balanced binary ordering tree and the linear feature indexing based on vertex retrospection. The address codes for querying area boundary cells can be used to separate the area into several sub areas to decrease excessive searching. Spatial ordering based on Hilbert code facilitates spatial clustering of the spatial objects and speeds up data extraction. Spatial indexing with Hilbert code is more efficient than sequential indexing when a great number of spatial objects are procesed. It is distinct for spatial extent and proximity querying.
出处
《中国图象图形学报（A辑）》
CSCD
北大核心
2001年第5期465-469,共5页
Journal of Image and Graphics
基金
国家"九五"科技攻关项目! (96 -B0 2 -0 3-0 5 )
