Quick Encoding Compression Algorithm of Octree for Modeling Three Dimensional GIS
Tong Cao · 2002
To meet the requirements of the three dimensional(3D) GIS community, it is necessary to study sophisticated data structures, which exerts very important influence on GIS function and efficiency. An efficient and compact raster data structure in GIS called octree is presented. Arbitrary 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 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.