ISPRS Workshop on Service and Application of Spatial Data Infrastructure, XXXVI(4/W6), Oct. 14-16, Hangzhou, China 
INDEXING OF THE DISCRETE GLOBAL GRID USING LINEAR QUADTREE 
Jianjun Bai a , Xuesheng Zhao a,b , Jun Chen b 
a .China University of Mining and Technology (Beijing), Beijing 100083,China; 
b National Geomatics Center of China, Beijing 100044, China 
KEY WORDS: Indexing, The discrete global grid, Linear quadtree, Neighbour- finding, Recursive subdivision, Diamond 
ABSTRACT: 
In recent years a method of recursive subdivisions of the triangular faces of the octahedron or icosahedron has been developed for 
approximating to the surface of the earth. But the triangle-based discrete grids produced by this method are complicated in geometry 
structure, and is difficult to make such geographical operations as neighbor-finding, spatial searches and so on. In this paper we 
conceives of the surface of the octahedron as composed of pairs of adjacent triangles, or diamond, that tessellate the surface, and thus 
creates nested diamond subdivision of the ellipsoidal surface by quadtree recursive partition. The quadtree Morton coding system is 
used as the index for addressing the diamonds and for linearizing storage that preserve a high degree of spatial locality. And a 
method of finding neighbor, ancestors and descendants also is developed. Based on this we further develop an index for addressing 
the triangle and a neighbor-finding method. The addressing system exhibits a high degree of regularity that makes it possible to 
develop very efficient algorithms for common spatial database and geometric operations 
1. INTRODUCTION 
In order to meet the needs of applications in dynamic modeling, 
data organizing, information storage and display, global grid 
model that uses the subdivided surface of Platonic solids, or 
regular polyhedron, as the approximations to the surface of the 
earth has been studied extensively. Among them quaternary 
triangular meshes (QTM) developed by the partition of either 
the octahedron or icosahedron is one of the representative 
methods. Because it uses triangle as the basic cell to organize 
spherical data that fall into this area, many spatial analysis 
methods must be completed based on the triangle. However the 
geometric structure of the triangle meshes is very complex, it 
has asymmetry and uncertainty orientation that make it difficult 
to implement such spatial operation as adjacent analysis, spatial 
query, data update and so on. 
In this paper we conceive of the surfaces of the octahedron and 
icosahedron as composed of pairs of adjacent triangles, or 
diamonds, that tessellate, or cover the surface of the earth. The 
surface of the earth can be approximated through the diamond 
subdivision. The spherical data is organized as diamond cell, 
thus the linear quadtree Morton addressing system can be used 
to label and index the cell. Based on this we further develop an 
index for addressing the triangle and a neighbor-finding method 
of the triangle. The addressing system exhibits a high degree of 
regularity that makes it possible to develop very efficient 
algorithms for common spatial database and geometric 
operations. 
2. PREVIOUS WORK 
Dutton[1990] and Fekete[1990] introduce a “floating” labeling 
scheme in which the labeling of the child triangle at each level 
varies based on the orientation of the parent triangle. Indexing 
and neighbor-finding of the triangle also be introduced based on 
this labeling technique. The advantage of this labeling 
technique is that the path components of all location codes that 
correspond to the neighbors of a particular triangle differ by one 
directional code, at the expense of added complexity for the 
neighbor-finding process. Moreover, this technique has the 
further disadvantage that finding neighbors that lie on different 
faces of the polyhedron is much harder. 
Goodchild and Yang[1992, Lee and Samet[2000] and ZHAO 
Xuesheng [2002] adopt a similar labeling scheme in which the 
labeling of the child triangle fixes according to the location of it 
in the parent triangle (left, right, middle and top). The 
neighbor-finding methods used in Goodchild and Yang[1992] 
and ZHAO Xuesheng [2002] have a worst-case execution time 
proportional to the maximum level of decomposition. Although 
based on the same principle as this methods, the algorithms of 
the Lee and Samet[2000] use binary arithmetic, and have a 
worse-case constant time complexity. 
Otoo and Zhu [1993] use a SQC (Semi-Quadcodes) labeling 
scheme in which two triangles that make up each square can be 
distinguishes through add an additional bit at the end of the 
Quadcodes. This makes it possible to use algorithms and 
techniques developed for Quadtree Square meshes, including a 
variant of the worst-case constant time neighbor-finding 
algorithms, but his algorithms can not deal with the case when 
the neighbor triangle across the different face of the polyhedron.