2004 
  
58. 
S for 
SPRS 
affine 
rrain, 
). 
Joint 
-86. 
high- 
tions, 
ey "of 
tions. 
omial 
tional 
"&RS, 
uality 
;&RS, 
ns for 
URL: 
stract 
URL: 
stract 
nation 
È 
tional 
+ &RS, 
lel for 
ith the 
" Cross 
9 p. 
itation 
Earth 
tion in 
|] p. 
GLOBAL INDEXING OF 3D VECTOR GEOGRAPHIC FEATURES 
J. Kolar 
Centre for 3DGI, Aalborg University, Jernes Niels Vej 14, 9220, Denmark, kolda«&3dgi.dk 
KEY WORDS: Spatial Information Sciences, Global, Multiresolution, Three-dimensional, Databases, Geography, Geometry. 
ABSTRACT: 
Geographic data management is essential for development of geo-related applications and systems. Fast access to a subset of data 
related to an area of interest with a sufficient precision is a common need for geographic applications. The mechanism for 
organizing data in the database determines how geographic features can be represented, whether or not the underlying database can 
be distributed or how the database can be updated. This article introduces a uniform global indexing method for 3D vector 
geographic data. The index facilitates several properties important for geographic systems, such as fast access to features with a 
similar geographic location, a multi-resolution representation, a global uniform coordinate system and the avoidance of using 
cartographic projections. In order to avoid truly 3 dimensional spatial indexing the solution is based on a tessellation of the space 
using two spherical coordinates. This decreases the computational complexity and increases performance. The article presents 
description of main concepts of the indexing method. Introduced method has been implemented and used with real terrain data. Also 
example applications are considered and practical connection with an RDBMS is proposed. 
1. INTRODUCTION 
1.1 Global Grids 
Indexing spatial data globally provides a unique approach for 
organizing geographic or any geo-related data. Various works 
on global grids has been elaborated in order to facilitate 
management of vector data, raster data, data quality and 
resolution of data. The main motivation for the presented 
indexing technique is development of referential model of Earth 
suitable for visual navigation. Taking this effort from the 
scratch an application of global grids as an indexing approach is 
a very essential issue of such development. However, not all 
spatial data management aspects of global geographic 
applications have been considered and even more left to be 
solved. Global grids, as division schemes, are naturally suitable 
for indexing spatial data. 
The major indexing property of global grids is division of the 
space into smaller areas. The task of an indexing application 
then is to access data from these areas fast, even though there 
are possibly huge amounts of data for the rest of the spatial 
domain covered by the grid. 
Another important issue is ability to edit data from these 
smaller areas independently from the rest of data in the covered 
domain; at least to certain extent. This means for example to 
have possibility to edit parts of the model representing Northern 
Jutland in Denmark independently from the part of the same 
model covering Sao Paolo in Brazil. Assuming that it is 
possible to do this using the same technology would have 
advantageous implications for distributed development and 
maintenance of global geographic model. 
The possibility of the maintenance “in pieces” would also 
facilitate constructing the model gradually, which is an 
Important requirement for practice. Global grids also influence 
669 
how the resulting geographic model can be exploited and shared 
by other geographic applications. 
A support for multiple level of detail of the model at various 
scales can be one such influence global grids can be behind. 
And it is particularly significant for visual applications. 
Proposed indexing technique is focused on visualization of 
global vector data, while most of the works were oriented 
towards raster data and data projected on a map plane. 
1.2 Related Work 
Several works elaborating different types of global grids have 
been published. 
In (Dutton, 1989) is introduced an irregular grid that divides 
sphere using recursive division of faces of octahedral into 
triangles. The quaternary triangulated mesh (QTM) method 
divides each face of octahedral into four same triangles whose 
vertices are projected on sphere afterwards. The process of 
division can be performed recursively. QTM has been used for 
various applications such as location code that allows locating 
any position around the globe together with its precision using 
only one number (the code). Also applications for map 
generalization, indexing and terrain representation have been 
elaborated. 
The global grid presented in (Lukatela. 1987) is based on 
Voronoi diagrams on the sphere. The shape of the division 
scheme is given by centroids distributed around the origin. The 
tessellation is based on radial proximity to the centroids. The 
scheme has been devised as one level global indexing technique 
for spatial data. The division scheme has been used for terrain 
representation too. 
In (Aasgard, 2002) is elaborated a solution for projecting 2D 
regular grid on sphere and thus take advantage of quad division 
in global 3D models. This approach is advantageous mainly for