A Global Discrete Grid Modeling Method Based on the Spherical Degenerate Quadtree

In this paper, a new modeling method of global discrete grid based on the spherical degenerate quadtree is described. Our approach starts with a new partition method, called degenerate quadtree grid (DQG), and an encoding scheme of the corresponding grids is presented. Next, the adjacent characteristics of DQGs in different positions are analyzed. Then, an adjacent searching algorithm of DQGs is given in details. The experiment and analysis are carried out with the global terrain data, GTOPO30. The results illustrate that: (1) the global discrete grid based on the spherical degenerate quadtree is seamless, hierarchical, and regular over the whole Earth, and it has the same simple geometrical structure as longitude-latitude grid; (2) the geometrical distortion of DQG cells is stable and astringency with the partition level increasing; and (3) the efficiency of adjacent searching in this model has been improved 100 times and 30 times respectively relative to the traditional Bartholdi algorithm and decomposing algorithm. The results are good and receivable.