'anbul 2004
Quantifying
esettlement
n Zambia.
15-3456.
ipping and
n the Jbaria
sing, 19(3),
- dynamics
te Sensing,
sitivity of
l extent
7(9), 1027-
ques using
te Sensing,
nal boreal
Journal of
sitivity of
of Remote
of satellite
zes in the
Journal of
02, Urban
id. spectral
M data,
7--3078.
»-temporal
China, In
e 1152.
Asse: 189-
rch Grant
1cil, Hong
stitute of
larly Mr
MODELLING OCEANOGRAPHIC DATA WITH THE THREE-DIMENSIONAL
VORONOI DIAGRAM
Hugo Ledoux and Christopher Gold
Dept. Land Surveying & Geo-Informatics, Hong Kong Polytechnic University
Hung Hom, Kowloon, Hong Kong
hugo.ledoux@polyu.edu.hk, christophergold@voronoi.com
KEY WORDS: GIS, Three-dimensional, Modeling, Oceanography, Triangulation, Algorithms, Data Structures, Dynamic
ABSTRACT:
Managing oceanographic data with traditional geographical information systems (GIS) is a difficult task because these systems have
been primarily designed for land-based applications. The main problem is that the nature of objects at sea is completely different
from the nature of objects found on the land: at sea most objects are represented by unconnected points that can have three-
dimensional coordinates, the datasets have 'abnormal' distribution and the objects tend to change position over time. We propose in
this paper using a spatial model based on the three-dimensional Voronoi diagram (VD) to handle topological relationships between
objects. We present the main properties of the 3D VD, algorithms to construct and modify it, and show how some 3D GIS operations
are greatly simplified when a spatial model is built upon it
1. INTRODUCTION
Data collected for marine applications have particular properties
that are usually not present in data collected on the land. First.
because almost no man-made objects are found at sea, the
objects (samples) are mostly represented by unconnected points,
to which some attributes are attached. Second, the samples are
usually collected from a boat, which results in datasets having
highly irregular distribution (samples are distributed according
to each ships track). Two-dimensional datasets (e.g.
bathymetric samples having x-y coordinates and depth of water)
are very difficult to manage with traditional geographical
information systems (GIS) because their spatial model is built
for two-dimensional land applications and their data structure is
based on the ‘overlays’ as a definition of adjacencies between
objects (Gold and Condal, 1995). Three-dimensional
oceanographic datasets are usually composed of CTD data:
attributes (Conductivity-Temperature-Depth) of the water are
measured with a sensor that is moved through the water column.
A three-dimensional (volumetric) representation of the water is
built with many water columns collected along different ship
tracks. Samplings obtained in such a way are sparse in the
horizontal direction but abundant in the vertical direction. The
integration of such datasets into traditional GIS is problematic
because these systems usually deal only with surfaces and two-
dimensional objects, and, as a result, datasets must often be
‘reduced’ by one dimension (for example by 'slicing' it) to be
integrated and analysed. Some solutions exist — using 3D raster
data structures as in the work of Jones (1989), Raper (1989) and
O'Conaill et al. (1992) — but, as shown in Section 4 , they have
shortcomings for oceanographic data. A further important
consideration is that the marine environment is dynamic, which
means that objects are likely to move over time.
The many problems arising when using a traditional GIS for
handling marine data have been described by many researchers
(Davis, 1988; Li, 1993; Lockwood, 1995). Using a spatial
model based on the two-dimensional Voronoi diagram (VD), as
Gold and Condal (1995) propose, solves most of the problems
mentioned earlier. As explained in Section 2, the VD will adapt
naturally to the distribution of the data and its 'tiling' properties
can be used to manage the topological relationships between
unconnected objects. Moreover, unlike the structure of
traditional GIS, the topology can be updated locally. Wright and
Goodchild (1997), in a review, atfirmed that this method was
the only published attempt at that time to solve many important
problems related to the nature of marine data. The only problem
not tackled by Gold and Condal is 3D volume-based
representations.
In this paper, we extend the work of Gold and Condal (1995)
and propose using the Voronoi diagram in three dimensions to
handle the topological relationships in oceanographic datasets.
As shown in Section 2, the concepts and properties of the VD
can all be generalized to three dimensions, and, as a result, we
have a spatial model capable of solving most of the problems
we have when dealing with oceanographic data. Although the
concepts easily generalize, their implementations are not
straightforward. For this reason, we discuss in Section 3 the
main construction and modification algorithms, and also
different data structures for storing the VD and its geometric
dual, the Delaunay tetrahedralization (DT). As described in
Section 4, such a spatial model has numerous advantages over
other knows methods. One of them is that many three-
dimensional spatial analysis operations are greatly simplified
and optimised, and we show in Section 5 how some of these
operations, when applied to an oceanographic dataset, can help
us to have a better understanding of it.
2. PROPERTIES OF THE 3D VORONOI DIAGRAM
The Voronoi diagram for a set of points in a given space Riis
the partitioning of that space into regions such that all locations
within any one region are closer to the generating point than to
any other. In two dimensions, each cell around a data point is a
convex polygon, having a defined number of neighbours; for
example in Figure 1 the point p has 7 neighbouring Voronoi
cells. In three dimensions, a Voronoi cell generalizes to a
convex polyhedron formed by convex faces, as shown in Figure
2. In any dimensions, the VD has a geometric dual structure
called the Delaunay triangulation. In 2D. this structure is
defined by the partitioning of the plane into triangles — where
the vertices of the triangles are the points generating each
Voronoi cell — that satisfy the empry circumcircle test (a circle
is empty when no points is in its interior, but more than three
703
