Istanbul 2004
tation and
urface either in
rdinate system,
ies.
n Mesh (QTM)
ed to set up the
ew hierarchical
' nodes, one is
organizing of
ode' for index
iewing window
am based on
level will be
y relationships,
updates in local
PHERICAL
M
' surface and its
n 1999]. In this
QTM codes and
nd to facilitate
re is simple: it
e. QTM address
t the initial one,
2 digits are used
»-millimeter and
d. In conceptual
ised to provide a
al data, but also
ic problem (by
ititude/longitude
)utton 1999b]).
al property and
n address codes.
| the coordinates
ordered list of
rtices in a point
‘the application
Iti-scale display
A address codes.
yy an ordered list
1 a global spatial
. For example,
gion boundaries
c-line data, only
ponding triangle
ry. In most cases,
| interpolation (10
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
large scales) and generalization (to small scales). A line can be
interpolated to achieve higher levels of detail or filtered to
achieve lower levels for display or other manipulations. If two
consecutive triangles are not neighbours, interpolate their
longitude/latitudes and transfer them to triangular address until
consecutive pairs of triangles are neighbours or have the same
triangular address. If adjacent triangles have the same triangular
address, remove the duplicated ones.
3.3 Area (Curve surface) Objects
Two-dimensional object (curve surface) on the sphere is
represented by a directional and closed boundary arc-line and
encoded triangular cells, which are completely within the region
[shown as Figure 5 and Table 2]. When compared to simple
boundary arc circular vertex list, this structure makes the
evaluation of spatial relationships significantly more efficient.
The solution will often be obtained by simple manipulation of
QTM address code, instead of the evaluation of boundary
geometry. The time consumption of calculation is inversely
proportional to the triangle size.
Az: ID P; nou Alm
Arc-Le Pa 02102202317 7 ES
P K QUO tt "3 t.
Nj babzzbıattt Din
Encoded AG bajbzgbza ba,
triemgles-Mj | e | onm
N bjbjglys ttt bs
Tab.2 Area (Curve surface) is represented by a directed
circular boundary arc-line and an encoded aggregate list of
triangle cells.
This representation of a two-dimensional object is a
combination of the traditional vector representation and those
schemes based on regular planar tessellations. It is of high
resolution and precision as vector representation and is efficient
in relational evaluation as raster. In addition, it does not violate
the true spherical nature of the data domain. For instance, if /A/
is a region, then NOT[A] is an infinite, numerically ill-defined
region in a planar. By contract, on any spherical surface, NOT/[A4]
is the simple finite complement.
4. VARIBLE-TREE DATA STRUCTURE
4.1 The concept of variable tree structure
The dynamic manipulation (or updating) of spatial data is based
on objects, and multi-resolution management of the global
Spatial data is based on fields instead of objects. To
accommodate these two requirements, a mixed global data
Structure -- Variable Tree Data Structure -- is designed by
connecting the dynamic stability of Voronoi data structure with
the hierarchy of QTM. In this data structure, the spherical
surface is tessellated with QTM and spatial objects are
represented by triangular codes, which have both hierarchical
and positional properties.
To operate data dynamically and efficiently, VTDS is
reconstructed with two types of new nodes which are different
with the traditional quadtree data structure:
* One is ‘O-Node’ (i.e. object-node) for a standard QTM
hierarchical organizing of multi-resolutions data. The
sub-node of this type consists of “/eaf-node’ and
‘branch-node’ which is as the same as the traditional
quadtree.
* Another is ‘/ Node'(i.e. index-node) which expresses an
793
index mechanism for retrieving the required data level and
local objects in a limited viewing window efficiently. The
sub-node of this type consists of *O-Node' and *I-Node' in
next level.
Meanwhile, the Voronoi diagram between objects at a given
level will be dynamically generated to preserve adjacency
relationships which are fundamental to perform queries and
updates in local addition or deletion of individual objects. The
basic principle of VTDS is illustrated in Figure 1. The
representation of O Nodes is almost same as that by the
traditional quadtree, so in this section, only the different types of
I Nodes and their representations in VTDS will be discussed in
details.
ROOT
0
FE reste
a ' Q. ac oum CP Index
: is structure
Level-0 T, E, 5 Aim
Lernen ie remet cR T
: ; i Os 9. Od \ |
; Lever à AN Wr Branch
nodes :
; H e---- j - a un A T M y Cont" X
: : otn. O13 zs Ponta sets Curve face
: Level-2 ! i t E
Dynamic rane í Address
aintain spatial ( uan MN code E
MANN SON | \ diagram / -
> relationships ee
Multi-resolution
manipulation
Fig.1 Basic principle of VaribleTree Data Structure
(VTDS)
4.2 Initial Nodes
From the tree root, the VTDS starts with as a forest of initial
three types of / Nodes and one type of O Node according to
their different locations. They are defined as follows (shown as
Figure 2):
* [n-triangle (T): The object is completely within an octant
triangle (including initial triangles T,-T,, totally 8
[ Nodes);
Edge-neighbour (E): The object only covers two
edge-neighbour octant triangles (including Eo;, E,?, E53, E39;
Eds, Ese, E67 Eva; Eos, Eis, Ege, E, totally 12);
Angle-neighbours (A): The object covers two or more
angle-neighbour octant triangles which have one common
vertex (including: Ao123, A4567, A0374 Aroası Az267; A2156
totally 6);
NO-neighbour (Objects): An object covers two or more
no-neighbour octant triangles, these are O Nodes and the
pointers, which point to these objects, are stored in the
nodes (including: Oo6s O17, O24, O35).
fi
/ 4| | JA,
x s woo. Lid
Og Or... " iT, Ti. Ta! En En
Fig.2 Categories and representations of initial Nodes
