268 
ISPRS Workshop on Service and Application of Spatial Data Infrastructure, XXXVI(4/W6), Oct. 14-16, Hangzhou, China 
3. GLOBAL GRIDS BASED ON THE QUATERNARY 
TRIANGULAR AND DIAMOND SUBDIVISIONS 
Similar to White [8], we conceive of the surfaces of the 
octahedron and icosahedron as composed of pairs of the 
adjacent (south and north) triangles, or diamonds, that tessellate, 
or cover the surface, so the octahedron has four base diamonds 
(we also refer to it as quadrant). The octahedron that made up 
by four diamonds is a coarsest approximation to the surface of 
the earth. 
Each triangle in the octahedron can be divided into four smaller 
equilateral triangles by breaking each edge into 2 pieces and 
connecting the break points with lines, which is referred to as 
QTM(quatemary triangular mesh)subdivision. Recursively 
subdividing the triangles thus obtained in the same manner 
yields QTM (figure 2); like the quadtree subdivision of the 
square, each quadrant (base diamond) in the octahedron can be 
divided into four smaller diamonds (figure 2). These two kinds 
of subdivision are essentially the same, so the QTM can be 
regarded as diamond meshes. The surface of the earth can be 
represented as a quadtree that the root (corresponding to the 
surface of the earth) has four children node (four base 
diamonds), and the internal node has four children node. 
It must be illustrated that the diamonds on the polyhedron are 
bent, and the four points that form the diamond are not in one 
plane, but for data structure they can be considered entire. 
Similar to the square meshes, the geometric structure of 
diamonds meshes is much more simpler than that of triangular 
mesh. Unlike the triangular mesh (has up and down triangle), it 
has uniform orientation, thus make the spatial operation 
especially neighbor finding easier. 
Figure 2. QTM and the diamond tessellation at the third level 
4. INDEXING AND CODING OF DIAMOND BASED ON 
LINEAR QUADTREE 
The surface of the earth can be represented as a linear quadtree 
that there need only the location of leaves to be registered in the 
storage process. The leaves can be labeled according to the Z 
spacefilling curve (figure 4). Each diamond is assigned a 
quadcode D and Morton codes M. The code of a diamond L can 
be represented as DM, where D is the quadcode of the quadrant, 
and M is the Morton codes of the diamond in the same quadrant. 
The quadrant is assigned a numerical label 0,1,2 or 3 (The 
quadcode D) according its location on the surface of the earth. It 
is illustrated as follows: 
D=0> 90°> A >0° 
D= 1, 180°> A >90° 
D= 2 , 270°> X >180° 
D= 3, 360°> 2 >270° 
Latitude. 
Longitude 
+ 180° 
Figure 3. The coding of four base diamonds 
Morton codes are used to label the different diamond produced 
by the subdivision within the same quadrant. It has two kinds of 
form: quaternary Morton code and decimal Morton code. 
Each diamond will be substituted by four smaller diamonds 
when performs subdivision. These four newly produced 
diamonds can be labeled respectively through adding a 
additional digit 0, 1, 2 and 3 according to their location (left, 
down, up and right) in the parent diamond (figure 4). Thus, the 
Morton code of a diamond consists of a sequence of numbers 
(0,l,2or3), where the length of the sequence represents the 
partition level of the base diamonds (quadrant). Each digital of 
the Morton code is the Arabic digital no larger than 3. 
Figure 4. The Morton code and Z space filling curve of 
diamonds 
5. NEIGHBOR FINDING OF DIAMOND 
It is easy to determining the Morton codes of either the sons or 
the parent of a diamonds according to the properties of the 
Morton codes. The sons of a diamond are determined by 
appending the digits 0,1,2 and 3 at the end of the Morton codes, 
and the address of the parent of a diamond is obtained by 
simply discarding the trailing quaternary digit. 
In order to determine adjacent neighbors of the diamond, firstly 
we must take the conversions between the Morton codes and 
row/column number of the diamond. The conversion algorithm 
between the Morton codes and row/column number of the 
diamond are introduced in detail in paper [11]. Figure 5 show 
the correlation between them.