×

You are using an outdated browser that does not fully support the intranda viewer.
As a result, some pages may not be displayed correctly.

We recommend you use one of the following browsers:

Full text

Title
The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics
Author
Chen, Jun

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° > > 0°, for the Northern hemisphere
a 0 = 4,5,6,7
And
0°> >- 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
• sub-edge triangle if it has exactly three indirect
• corner triangle if it has exactly two direct neighbors in
• sub-comer triangle if it has exactly six indirect
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