-neighbour 
ified into 2 
(shown as 
or more 
non vertex 
-neighbour 
ler pointing 
Yeighbour 
, SPATIAL 
struction of 
1992]. This 
| spatial data 
e utilize the 
ure to update 
fluences the 
ture of other 
e two main 
this section, 
le location in 
les in VIDS. 
resented by 
, is the total 
k (<=8x4"). 
d ‘3’ and U' 
se code f, €, 
is completely 
triangles, and 
s which have 
ts Nodes in 
ir triangles in 
xdes in level i 
bour triangles 
mon vertex. 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
ds ane ose inno ; . 
1). To search u, m level 0 (type 1): 
* If (0,6) OR.{1,7} OR.{2,4},OR. {3,5} € tu, | no=0,1,..,7} 
*, 
Object[u]—/eve/ 0, then stop recursive search. 
* [f n5*1 I Node T,, is added if it is not existed and process 
i, according to type 2. 
« If ny=2.AND.(u, , uy) € {(2,6),(3,7) (0,4). (1,5)}, 1_Node 
Ey? is added if it doesn't exist, process u, according to 
type 3 
«If n=24AND.( u; . uy )e{(0.1).(1,2).(2,3).(3.0).(4,5. 
(5.6).(6,7),(7,4)}, I Node A,» 1s added if it is not existed 
and process u, according to type 6. 
* Otherwise, / Node Auj;,»usu4 is added if it doesn't exist, 
a | s 1: AR 
process u, according to type 5. 
2). To search / Node t; in which object is within one triangle 
level i (i<k) (type 2). 
* If n= 4, the search finishes, and object [U] level i. 
* 1fn, =. AND.{u{} €(0,1,2,3}, I Node t,, is added if it 
doesn't exist, process ee according to type 2. 
i-l 
* Ifn=2.AND.(u' uy) =(0.1), I_Node eu12 is added if it 
1 
doesn’t exist, process wl! according to type 3. 
"df n-2.AND (s : ; uy) €((0,2),(0,3)?, I Node e,» is 
added if it doesn't exist, process utt according to 
type 4. 
* Otherwise, / Node a,;,5,* 1s added if it doesn't exist, 
i+1 
process 7, according to type 5 
i*l 
3). To search / Node e,;,5» (or E,,,5) in which object traverses 
two edge-neighbour triangles which neighbour orientation is 
‘Top and Down’ in level i (i<k) (type 3): 
* Ifdigital ‘7’e{u, | n=0.1,....}, the search finishes, and 
object[U] level i. 
* df (uiu) c (22), 3.3), 1. Node ej) is added if it 
doesn't exist, process u i according to type 3 
i+l 
* Otherwise, / Node A,1u2u3utu5uo 1S added if it doesn’t exist, 
] 
process 4 * according to type 5. 
i+ 
4). To search I Node e,;, in which object traverses two 
edge-neighbour triangles in one octant which neighbour 
orientation is ‘Lefi-Right’ in level i (i<k) (type 4): 
* 15. ui 72.08. ul —3, the search finishes, and object [U] 
— level 7. 
> 1 n=2.AND.(u ; Jul) (1.2), (3,1)), I Node e,j,51s added 
if it doesn't exist, process ut according to type 4.. 
41 
* Otherwise, / Node a,;,/2u3u4usu5 18 added if it doesn't exist, 
À o 7 ; & 
process # ^ according to type 5. 
ist 
5). To scarch I Node Aylu2u3udu5u6 (or Antuzu3u4) in which object 
traverses two more than two angle-neighbour triangles that have 
one common vertex in Jevel i (i<k) (type 5). 
* I0 c (uh | n;70,1,....j]. 1 Node a' is added if it doesn’t 
exist, process 7 P according type 5. 
ist 
* Otherwise, the search finishes, and object [U] level i. 
6). To search I Node E,;,; in which object traverses two 
edge-neighbour triangles in two different octant and its 
orientation is *Lefi-Right in level i (i«K) (type 6): 
Hu OR. u, =3, the search finishes, and object [U] 
—level i 
* If 5j72.AND.(u | uS) CL D), (3.2)), 1. Node E,,, is added 
if it doesn’t exist, process 2"! 
according to type 6. 
* Otherwise, I Node A, uu3uansus 18 added if it doesn't exist, 
1 
process y!"' according to type 5. 
i+ 
The deletion operation is almost as same as insertion. The only 
difference is that the searching orientation is reversed. 
5.2 Adjacency Relationship Maintenance in 
Manipulation 
Dynamic 
In local updating, deletion and insertion of objects results in 
a change in spatial relationship with only adjacent objects and 
indeed the topological relationships of other objects remain 
unchanged (shown as Figure 6). This is one of the excellent 
properties of Voronoi diagram [Gold 1992]. In VTDS, 
QTM-based method for the computation of a spherical Voronoi 
diagram can be seen in our former work [Zhao et al. 2002]. The 
whole data of one object is in one node and it is very easy to 
calculate the adjacency relationships of the changing objects 
and their neighbours. 
v v 
* MuR ur . à - : 
rd " d 5 ^ 
t « X 3 
& f p: . ; 4 if 
x = - ir a ; = * wi " 
UR. CA os an = 
“ n * ë . Uu : = 
PE——— PEE 
A S y EE 
F3 L TE RID pee P2 — Pl 
EN ASIN 
Pg x e. 
po^ NI PM me | » ^ 
C eR ET TN 
S. for Pie os : y eT b. gis 
| RS | |ocppeee- p^ | 
a ps f SN + AES 
Ps |. P^. E 
Je — * d E ; 
> pps —— PM 
Fig.6 Deletion and insertion of objects and their adjacent 
relationships changes.. 
6  DISSCUSION AND CONCLUSIONS 
In this GHDDM, the conceptual data model of spherical objects 
and their representation based on QTM address codes are 
presented at first. It offers several advantages, such as being 
unique and domain independent, appropriately indexed or 
linearized grids express spherical surface location in a single 
string, preserving geometrical integrity both locally and 
globally, and making resolution explicit in the length of the 
string. 
One important contribution in our approach is that integrate the 
advantages of field-based and object-based data models to 
construet thé VaribleTree Data Structure (VTDS) by two types 
of new nodes, one is O Node for a powerful hierarchical 
organizing of multi-resolutions data and another is /_Node for 
index mechanism to retrieve local data in a limited viewing