Istanbul 2004
A MIX GLOBAL DATA STRUCTURE BASED ON QTM AND VORONOI
Xuesheng Zhao *
Jun Chen ^ Zhilin Li ^
* China University of Mining and Technology (Beijing),D11 Xueyuan Road, Beijing, China, 100083,E-mail: zxs(ücumtb.edu.cn
' National Geometrics Center of China,No.1 Baishengcun, Zizhuyuan, Beijing, China, 10004, E-mail: chenjun(insdi.gov.cn
* Department of Land Surveying and Geo-Informatics The Hong Kong Polytechnic University, Kowloon, Hong Kong
Tel: (+852) 2766 5960, Fax: (+852) 2330 2994; E-mail: Isllz@polyu.cdu.hk
Commission IV
KEY WORDS GIS, Updating, Modeling, | Dynammic,
ABSTRACT:
WG IV/8
Triangulation
To efficiently store, retrieve and update the global spatial data, a hierarchical and dynamic data model on a global scale is urgently
needed. The QTM (Quaternary Triangular Mesh) as a hierarchical quadtree data structure on sphere is one of the most efficient
methods for managing the global spatial data in many applications. But QTM structure is based on fields instead of objects. So it is
efficient in multi-resolution manipulation, but difficult in local data update frequency. To efficiently manipulate multi-resolution and to
update data dynamically, a mix global data structure----- Variable Tree Data Structure (VTDS) is designed. There are two different
types of ‘node’s in VTDS, one is *O Node' (i.e. object-node), the other is '1 Node" (i.e. index-node). At every level (except the root
one), all *O Node's only consist of spatial objects represented by QTM address codes which is efficient in multi-resolutions
manipulation. However, ‘I Node's may consist of child *O Node's and ‘I_Nnode’s which include indexing information by which the
interested objects within a location scope can be retrieved easily. Meanwhile, the Voronoi diagram based on QTM of related 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. Multi-resolutions manipulation and dynamic update of spherical objects in VTDS are
given in details in this paper.
1. INTRODUCTION
In recent years, the QTM (Quaternary Triangular Mesh), which
is a efficient spherical hierarchical quadtree data structure for
managing the global spatial data, has attracted much attention
from the GIS community and has been applied to some areas,
such as rendering and managing spherical data [Fekete 1990],
spatial data hierarchical index [Goodchild et al. 1991],
environment monitoring [White et al. 1992], positional
uncertainty in spatial databases [Dutton 1999b], digital map
generalization [Dutton 1999a], global navigation [Lee and
Samet 2000], and Continuous indexing of hierarchical
subdivisions of the globe [Bartholdi and Goldsman 2001]. QTM
partition is a tessellation of the Earth's surface with
non-overlapping triangles. It is a field-based data model (or
space-primary by Lee et al., 2000) instead of object-based (or
feature-primary by Lee et al, 2000). It has the property of
obvious hierarchical structure, which is efficient in
multi-resolution manipulation. However, such a data model
describes hierarchical space using a collection of basic units (e.g.
triangle) instead of spatial objects themselves. In this way, if a
single spatial object is changed, the entire hierarchical structure
may have to be re-organized [Pang and Shi 1998]. The process
of re-organization obstructs the maintenance of spatial relations
among the changed spatial objects in the hierarchy. Therefore,
QTM is not suitable for spatial processes of frequent data
updating locally. As a result, a data model with the good
properties of both field-based and object-based is very desirable
for global data sets, if feasible.
Indeed, in this paper, a Global Hierarchical and Dynamic Data
Model (GHDDM) based both on fields and objects will be
presented. In this model, spherical surface is partitioned with
Quaternary Triangular Meshes and spatial objects are
represented by triangular codes, which have both hierarchical
and positional properties.
791
Following this introduction is section for a critical examination
of existing global data models (GDMs). In section 3, partition
method of QTM on spherical surface and its code labeling will
be introduced. Section 4 will present the concept of data model
and the representation of spherical objects (points, arcs, and
curve surfaces). In section 5, the VaribleTree Data Structure
(VTDS) based on QTM and Voronoi is described in details.
Multi-scale manipulation is discussed in Section 6 and dynamic
manipulation of for local updating is discussed in section 7. At
last, the conclusions are made in Section 8.
2. GLOBAL DATA MODELS: A CRITICAL
EXAMINATION AND A NEW STRATEGY
In the recent years, Global Data Models (GDMs) have been has
been a hot topic due to the development of Digital Earth (DE).
These models could be either field-based or object-based [Pang
& Shi 1998]. The field-based is also called space-primary and
the object-based is also called feature-primary (Lee et al., 2000).
In an object-based data model, spatial object representations are
in vector mode. The basis for calculating the geographical
relationships ^ between surface ^ objects is usually
longitude/latitude coordinates, which bring about several
problems to be resolved [Lukatela 1987, Gold 1997], such as
e causing coordinates discontinuities of 180 longitude,
e being forced to use conventional ellipsoidal trigonometry
involving the transcendental functions which can affect
performance greatly, and
e (the most important) formulae being unstable at high
latitude
The inadequacies of GDMs based on the latitude/longitude have
led a number of researchers to explore alternative approaches.
Lukatela [1987] sets up a digital geo-positioning model, in
which direction cosines was used instead of latitude/longitude
in order to have a seamless data structure. Once the direction
