International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
cosines for an object are computed, there is no need of using
transcendental functions in subsequent spatial manipulations.
Instead, calculations are carried out using a vector algebra
requiring only floating addition, subtraction, multiplication,
division, and an occasional square root. Such calculations are
not only very fast but also very stable everywhere on the Earth’s
surface. On this basis, Gold and Mostafavi [2000] consider to
take advantage of the dynamic Voronoi data structure for the
addition and deletion of points and line segments using a small
set of purely local operations, and for the preservation of the
adjacency relationships between objects which are fundamental
to perform queries and updates.
But in all object-based GDMs, the hierarchy of space is created
by grouping and organizing spatial objects according to some
pre-defined relations. In this case, changes are referred to spatial
objects themselves and hierarchy of spatial object is maintained
using explicitly defined relations among spatial objects instead
of recursive decomposition of space. When a spatial process
results in changes to spatial objects at one particular level, these
changes cannot be propagated to its adjacent levels [Pang and
Shi 1998]. Hence, these object-based GDMs are difficult to
manage large volume of global data and to manipulate
multi-resolution data efficiently.
In a field-based data model, object representations are in cells
(i.e. grids or raster) and spherical surface are tessellated as a
series of packets or cells. The familiar latitude/longitude
graticule (or cell) is the most common basis for GDMs in use
today. In the case of GDMs for storing field data, lines spaced at
regular latitude and longitude increment form the boundaries of
area cells. GDMs based on the latitude/longitude graticule have
numerous practical advantages and have been used to develop
sound survey sampling designs on the Earth's surface, such as in
environment monitoring [Olsen ef al. 1998] and climate
modelling [Thuburn 1997]. These GDMs based on spherical
grids would not only allow the same structure to be used over a
wide range of spatial resolutions and efficiently load only
needed segments [Faust ef al, 2000], but also allow the
presentation of data at multiple levels and any arbitrary
resolution and offer several major 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
[Goodchild and Yang, 1992]. GDMs with hierarchical grids
properties have been adopted in many contexts, including the
quadtree indexes used in spatial database [Samet, 1989], global
environment monitoring [White er a/, 1992], map generalization
[Dutton 19992, 1999b], and dynamic navigation [Lee and Samet
2000]. But their major disadvantages are that (1) they are
familiar to a large community, and (b) lack of an intuitive
relationship between pairs of codes and proximity [Goodchild
2000]. These properties may be not very important for
virtualisation purposes, but would be problematic in
maintenance an object in this hierarchical data structure may
exist in the nodes of different branches in the tree structure. If an
object is removed a little bit (or deletion or insertion), the whole
data structure may be changed completely. Therefore, these
field-based GDMs are not good for frequent local updating and
the consistent topological structure maintenance dynamically
[Pang and Shi 1998].
In order to efficiently store, retrieve and analyse spatial data on
a global scale, alternatives to current GIS data models are
urgently needed [Goodchild and Yang 1992]. The new data
model must be
e seamless on a global scale
e efficient for dynamical updating
792
e capable of facilitating hierarchical representation and
e able to retain the topology of the earth's surface either in
the data model itself, or in the internal coordinate system,
which allows local modifications and queries.
Our approach starts with a Quandary Tessellation Mesh (QTM)
based on the inscribed octahedron, which is used to set up the
concept data model of spatial objects. Then, a new hierarchical
data structure is constructed by two types of nodes, one is
‘O Node’ for a powerful hierarchical organizing of
multi-resolutions data and the other is ‘/_Node’ for index
mechanism to retrieve local data in a limited viewing window
efficiently. Meanwhile, the Voronoi diagram based on
triangular-grids between objects at a given level will be
dynamically generalized to preserve adjacency relationships,
which are fundamental to perform queries and updates in local
addition or deletion of individual objects.
3. CONCEPTUAL DATA MODEL OF SPHERICAL
OBJECTS BASED ON QTM
The details of the tessellation method on sphere surface and its
labelling scheme of QTM can be seen in [Dutton 1999]. In this
paper, spherical objects will be represented by QTM codes and
their identifiers to save computer storage and to facilitate
multi-resolution manipulations.
3.1 Point Objects
Digital representation of a point on the sphere is simple: it
consists of an identifier and a QTM address code. QTM address
codes consist of digits ‘0°, ‘1°, ‘2’, or ‘3° except the initial one,
and each digital can be expressed by 2-bit. If 32 digits arc used
in a QTM code, locational accuracy reaches sub-millimeter and
such a code can be expressed as one 64-bit word. In conceptual
data model, address code of a point is not only used to provide a
multi-resolution operation of large-volume global data, but also
used to provide a numerical solution of metric problem (by
transformation between address code and latitude/longitude
coordinates [Goodchild and Yang 1992, Dutton 1999b]).
Address codes of points have both hierarchical property and
location property. Location of point is implicit in address codes,
not as explicit as in the other systems in which the coordinates
are records explicitly.
3.2 Arc-line Objects
Arc-lines on sphere are represented by an ordered list of
triangles traversed by the arc and a list of vertices in a point
format described above, shown as table 1. If the application
requires frequent manipulations of spatial multi-scale display
and overlay, it may be efficient to only use QTM address codes.
r
Lj ID+ P; dia OI.
P; 0210222237 "7^ Can
P k Guadgduatt "Os
Tab.1 Arc-lines on sphere are represented by an ordered list
of triangles.
Arc-line is one of the most important objects in a global spatial
database (like line in the planar database). For example,
hydrology, transportation, terrain relief and region boundaries
are commonly represented by arc-lines. For arc-line data, only
the vertex points are transferred to corresponding triangle
address codes in order to saving storage memory. In most cases
these triangles are discontinuous and may need interpolation (to
[nte
larg
inte
ach
con
long
con
trial
add
Twi
rept
enc
[she
bou
eva
The
QTI
geo
pro]
Az:
Thi:
com
sche
resc
inr
the |
is a
regi
is th
4.1
The
on :
spat
accc
Stru«
conr
the
surf:
repr
and
To
reco
with
