An Algorithm for Hilbert Ordering Code Based on Spatial Hierarchical Decomposition
一种基于空间层交分解的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.