用于建立三维GIS的八叉树编码压缩算法

复杂的空间数据结构在三维GIS领域中占有突出的地位,它直接关系到GIS的功能和效率,为了有效地进行三维GIS大量数据的存储和管理,重点讨论了三维GIS栅格数据结构中的八叉树编码压缩技术,由于Morton码值的排序是实现八叉树编码压缩的基础,为此,根据Morton码排序的特殊性,提出了采用时间复杂度为O（n）的计数排序算法,使排序速度大为撇提高,在此基础上进行压缩处理,并对算法的时间及空间复杂度进行了分析,在PC机上进行的模拟实验结果表明,在目标复杂度一定的前提下,八叉树存储数据占用空间小（当分割阶次为9阶时,八叉树存储量只占栅格存储量的4.32%）,是一种较为理想的描述复杂海量地理空间数据的压缩结构。

Quick Encoding Compression Algorithm of Octree for Modeling Three Dimensional GIS

To meet the requirements of the three dimensional(3D) GIS community, it is necessary to study sophisticated 3D data structures, which exerts very important influence on GIS function and efficiency. An efficient and compact raster data structure in 3D GIS called octree is presented. Arbitrary 3D objects can be represented to any specified resolution in a hierarchical 8 ary tree structure or octree. To save memory, E octants are not registered. A linear octree data structure that lists only octree codes of F Octree is used. This paper focuses on discussing the compression technique of linear octree. According to the peculiarity of morton code, Counting sort algorithm occupying linear time is applied to sort code. Sorting time is faster 21 times than quick sort with n =7. An effective way of compacting sorted octants having the same attribute is given, and temporal and spatial analysis is described. Experiments on PC demonstrates that the memory storage for octree code using proposed algorithm is considerably low in comparison to others(octree/raster=4 32% with n =9). The study also indicates that octree is an ideal data structure for representing the sophisticated geographic spatial information. Program "3D Octree" has been written to develop, verify and demonstrate the octree encoding algorithms.