ISPRS, Vol.34, Part 2W2, "Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
octahedral decomposition at level 0. Since the earth is divided 
into 8 equilateral spherical triangular faces as shown in Figure 
4-a, an octal digit is assigned to a 0 for addressing each face as 
follows: 
a 0 = 0,1,2,3 
90° > <j> > 0°, for the Northern hemisphere 
a 0 = 4,5,6,7 
And 
0°> <t>>- 90°,for the Southern hemisphere 
a 0 = 0,4 
90°> A>0° 
a 0 = 1,5 
180°> X >90° 
a 0 = 2,6 
-90°> A >-180° 
3o~ 3,7 
0°> A >-90° 
In the next code aia 2 a 3 a k , the ID-code of center triangular is 
“0”, up or down triangular is ”1”,left is”2”,and right is “3”(shown in 
Figure 4-b). This code have changeless direction, and suitable to 
proximity query. 
4.3 Definition Neighboring triangular 
We give the definition of neighboring triangular in QTM and term 
neighbors with shared edges direct neighbors and only with 
common vertices indirect neighbors, showed as Figure 5-A. In 
the data structure of O-QTM, neighbors of a triangle, which are 
located in two adjacent octants, must also be especially 
considered because the finding methods in different locations of 
border triangles are different. From Figure 5-B, we can see that if 
a triangle has edge(s) at the border of an octant, the triangle will 
have direct neighbors and indirect neighbors in its neighboring 
octant(s); if a triangle has vertices(s) at the border of an octant, 
the triangle will only have indirect neighbors) in its neighboring 
octant(s). They can be classified into 4 categories of border 
triangles: edge, sub-edge, corner and sub-comer triangles and 
can be defined as follows [Goodchild et.al 1992], as shown in 
Figure 5-B 
Fig.5 Definitions of neighbor triangles and border triangles: A) 
Direct neighbors and indirect neighbors, B) classification of 
border triangle 
• edge triangle if it has exactly one direct neighbors in the 
adjacent octant. 
• sub-edge triangle if it has exactly three indirect 
neighbors in the adjacent octant. 
• corner triangle if it has exactly two direct neighbors in 
the adjacent octant. 
• sub-comer triangle if it has exactly six indirect 
neighbors in the adjacent octant. 
4.4 Finding algorithm of direct neighbor triangles 
All triangles have three direct neighbors on sphere. We use the 
codes t, I, r to represent the three direct neighbor triangles with 
common top, left and right edges for a given triangle U inside an 
octant, the code T, L, R to represent the direct neighbor triangle 
of a top, left and right edge triangle lying in the adjacent octant. 
The different finding methods will be used if the triangles at the 
different location in one octant. They can be classified into 7 
categories of triangles and can be defined as follows: 
• inside triangles(A)—-The addresses code of a given 
triangle U include digital ‘0’ or include digital '1' AND ‘2’ AND 
‘3’. Its edge-neighbor-triangles are (t, I, r). 
• top corner triangles(B) The addresses code of a given 
triangle U include digital‘T only. Its edge-neighbor-triangles 
are (t, L, R). 
• Left corner triangles(C) The addresses code of a given 
triangle U include digital '2' only. Its edge-neighbor-triangles 
are (T, L, r). 
• Right comer triangles(D) The addresses code of a given 
triangle U include digital ‘3’ only. Its edge-neighbor-triangles 
are (T, I, R). 
• Left edge triangles(E) The addresses code of a given 
triangle U include digital ‘1’ AND '2' only. Its 
edge-neighbor-triangles are (t, L, r). 
• Right edge triangles(F) The addresses code of a given 
triangle U include digital ‘1’ AND '3’ only. Its 
edge-neighbor-triangles are (t, I, R). 
• Top edge triangles(G) The addresses code of a given 
triangle U include digital ‘2’ AND '3' only. Its 
edge-neighbor-triangles are ( T, I, r). 
Let the triangular addresses of direct neighbors of a given 
triangle U be represented by: 
t=ti. t 2 . t 3 -,tk 
l~ll- 12- 13• ,lk 
r=r h r 2 . r 3 . -,r k 
T=7V T 2 . T 3 . •, T k 
E=E 1 .E 2 .E 3 . ,E k 
W=W,. W 2 . W 3 . ,W k 
The data strings t, I, r, T, E and M can be gotten by the 
triangular address U. The details can be seen in [Goodchild 
et.al, 1991]: 
4.5 Finding algorithm of indirect neighbor triangles 
(a) (b) (c) 
Fig.6 indirect neighbor triangles: a)top corner triangle ; 
b)no-top corner triangle ; c) Finding types 
As the triangles location in an octant, corner triangle has 7 
indirect neighbor triangles, and the other has 9 indirect neighbor 
triangles (Figure 6-a-b). There are some methods to find indirect 
neighbor triangles. In this paper, they have been found by direct 
triangles. 
The left neighbor triangle of triangle U is expressed as : L (U) = 
Left (U) ; The right neighbor triangle is as: R (U) - Right (U) ; 
The up or down neighbor triangle is as: T (U) = Top (U) . 
Finding algorithm of indirect neighbor triangles are different 
according to the different location of U in the octant, and 
classified as 9 as follows: (Figure 6-c): inside, edge, sub-edge, 
comer and sub-corner triangles 
A) inside triangles ( 9 ) : 
L(T(U)),R(T(U)), T(L(U)),L(L(U)), T(R(U)),R(R(U)),L(L(T(U))) 
,R(R(T(U))),R(T(L(U))) 
B) corner triangles ( 7 ) 
L(T(U)),R(T(U)), T(L(U)),L(L(U)), T(R(U)),L(L(T(U))),R(R(T( 
U))) 
C) left-corner triangles ( 7 ) •• 
L(T(U)),R(T(U)),L(L(U)), T(R(U)),R(R(U)), R(R(T(U))), 
L(T(R(U))) 
D) right-corner triangles ( 7 ) : 
L(T(U)),R(T(U)), T(L(U)),L(L(U)),R(R(U)),L(L(T(U))), T(R(R( 
m 
E) left-edge triangles ( 9 ) 
L(T(U)),R(T(U)), T(L(U)),L(L(U)), T(R(U)),R(R(U)), T(L(T(U))) 
,R(R(T(U))),T(L(L(U))) 
Mm'-va'm mm<-7/. 
, T(R(T(U))),R(T(L(U))) o 
393