R PRÉ
propriate
overhaul
| diagram
work on
roduce a
cimity of
lot Book
v the sea
(d by its
was used
'ere used
nent and
ariety of
uired an
iired for
t for the
look at
epresent
ensional
salinity
ideas of
pre two-
ted the
for the
Voronoi
etection
but felt
to take
'aphical
al. data
le data
he map
ve that
de the
le. We
_ (Woo
use of
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004
transparency), Delphi for the programming language (because
of its excellent development environment, and object-oriented
programming facilities), and the Quad-Edge data structure
(Guibas and Stolfi, 1985) for the representation of spatial
relationships (because of its simultaneous preservation of both
primal and dual relations).
2. RELATED WORK
In recent years, many papers have discussed the problems of
using a land-based GIS for marine applications. Probably one of
the first articles about Marine GIS is the one by Davis and
Davis (1988) in which they state that variables in three
dimensions, plus time and attributes are needed to correctly
represent the marine phenomena. Li and Saxena (1993),
Lockwood and Li (1995) and Wright and Goodchild (1997)
give a complete review of what sets apart a Marine GIS from a
land-based GIS; they state that objects at sea are different from
objects on the ground because they are likely to change position
over time, they can have three-dimensional coordinates, they
are mostly represented by points (lines and polygons are scarce
at sea) and the distribution of samples is usually *abnormal
(data are sparse in one or two dimensions but abundant in the
others). If the nature of the data is completely different, why
should a land-based GIS be used for marine applications? The
major problems of traditional GIS are that their spatial model is
built for static two-dimensional land applications and their data
structure is based on the ‘overlays’ as a definition of
adjacencies between objects. The only thing that has been done,
by commercial companies, to solve these problems is trying to
extend — by adding new kinds of analysis and by modifying the
database model — the spatial data model of current GIS; but the
real problems are the spatial model used and the building of the
topology process, not the database aspect (Gold, 1991). A
Marine GIS needs a dynamic data structure to handle time and
objects moving over time — local updates of the topology when
an object is added, deleted or moved must be possible because
now with traditional data structures it is a global operation — not
just an extension of the current polygon-arc-node on the plane.
Most GIS research on time tries to extend the current
architecture of GIS by adding temporal information in the
database, but GIS are usually closed systems and the extensions
cannot handle every spatio-temporal problem. To overcome
these problems, van Oosterom (1997) proposed a spatial model
that can manage changes both over time and topology in the
same database by a data structure usually used in CAD systems;
and Gold (1996) managed the topology of a map and the spatio-
temporal operations made on it — objects can be added, removed
or freely moved — with a spatial model based on the Voronoi
diagram. This same spatial model was also used by Gold and
Condal (1995) and Gold (1999) to build a prototype of a Marine
GIS where objects (mostly unconnected points) are handled by
the ‘tiling’ properties of the Voronoi diagram. This prototype,
entirely based on the Voronoi diagram to handle topology and
perform analysis and operations, has many advantages over the
traditional GIS for many applications at sea. Wright and
Goodchild (1997), affirmed that this method was the only
published attempt that could solve important problems related
to the nature of marine data (abnormal distribution of samples,
dynamism of the sea, etc.).
689
3. THE VORONOI DIAGRAM AS A SPATIAL DATA
MODEL
The static Voronoi diagram (VD) for à set of points in the
Euclidian plane is 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. The VD has a geometric
dual structure called the Delaunay triangulation (DT) that is
defined by the partitioning of the space into triangles — where
the vertices of the triangles are the points generating each
Voronoi cell — that satisfy the empty circumcircle test (a circle
is empty when no points is in its interior, but more than 3 points
can be directly on the circle). The DT for a set of non-cocircular
points is unique; and so is the VD. In the case of 4 or more
cocircular points, an arbitrary choice must be done to form 2
triangles. The static VD for points on the plane has been used in
many fields (see Aurenhammer (1991) for a summary). Its
properties are well known and many algorithms have been
developed to create it. The incremental algorithm is the most
interesting in the GIS field because it permits the addition,
deletion or movement of points in the VD without rebuilding
the whole diagram.
The VD, which can be constructed from the DT and vice versa,
also provides the adjacency relationships between points: each
cell, which is convex, has a finite number of neighbours. It also
has the advantages of both the field-type (raster) and vector
representation. Each object (points, lines or polygons) can be
represented individually (each one has its own cell) and the
space-covering ‘tiling’ of the plane gives a definition of spatial
adjacency between objects (even if they are unconnected). The
same spatial model can therefore be used to manage both vector
data and images.
The spatial model of commercial land-based GIS is usually
based on a vector-based representation (the ‘polygon-arc-node’
structure being the most popular) and the topological
relationships between objects are defined by the ‘overlays’. In
other words, polygons are formed firstly by identifying the
intersections between the lines, and secondly by finding a
‘closed loop’ among these lines using ‘graph-searching’
algorithms. This global operation must be done not only to
build the initial topology, but also each time there is a
modification in the map (insertion, deletion or movement of an
object), and for the whole map. An operation is local when,
after a modification, only the immediate neighbours of an
object must be updated. A GIS based on a static vector-based
data model can obviously not manage a moving object or
temporal data, two important factors in a Marine GIS
4. GRAPHIC SYSTEM DESIGN
One concept in the development of computer graphics (e.g.
Foley et al, 1990) is the ability to concatenate simple
transformations (rotations, translation (movement) and scaling)
by the use of homogeneous coordinates and individual
transformations expressed as 4x4 matrices for 3D worlds.
(Blinn, 1977) showed that these techniques allowed the
concatenation of transformation matrices to give a single matrix
expressing the current affine transformation of any geometric
object. More recent graphics hardware and software (e.g.
OpenGL: Woo et al., 1999, Hill, 2001) adds the ability to stack
previous active transformation matrices, allowing onc to revert
to a previous coordinate system during model building.
