-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