International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004
3.5 Movement of Points
When a point is continually moving over time, it makes no
sense to continually insert, delete and re-insert it again
somewhere else, because it is a costly operation. Instead, it can
simply be moved and the topological relationships locally
updated when it is needed. Roos (1991) and Gold (1991) detail
a method that uses flipping to update the adjacency
relationships of a 2D Delaunay triangulation as one vertex is
moving over time. The movement of only one vertex to another
location involves updating, by flips, all the topological
relationships that will be modified from the starting point to the
end point. If the location of the point is just slightly changed,
the topological relationships will probably not need to be
updated, but as soon as the moving point enters or leaves the
circumcircle of a neighbouring triangle, a flip must be
performed.
These ideas generalize to three dimensions, although, to our
knowledge, no implementation is known. We are also currently
working on implementing the method by using flip23 and flip32
to update the DT as one vertex is moving.
3.6 Possible Data Structures
When choosing a data structure to store a Delaunay
tetrahedralization (or a Voronoi diagram), there is a trade-off
between the size of the data structure and the topological
relationships stored. For example, a very simple data structure
means that when some operations are performed more work will
have to be made (e.g. to retrieve the boundaries of Voronoi
cells), while a data structure where the DT and its dual are both
stored will speed up the use of these operations.
The simplest data structure to store the DT is the tetrahedron-
based data structure where each record represents a tetrahedron
with four pointers to its vertices and four pointers to its
neighbouring tetrahedra. Many implementations of the DT (e. g.
CGAL) use this data structure because it is simple and yields a
fast construction. However, in our case, the VD will be needed
for many spatial analysis functions and storing both might be
advantageous. One solution is using the /acer-edge structure
(Dobkin and Laszlo, 1989), which stores symmetrically both the
primal and dual of a threc-dimensional subdivisions. As it name
implies, the 'atom' of the structure is a pair of an edge and a face
and operators to navigate from edges to edges on a same face or
to visit all the faces incident to a given edge are available.
Construction operators are also available. Although this
solution seems attractive, it has been found difficult to
implement in practice and, to our knowledge, has not been used
for 'real projects'.
We are currently working on a simpler data structure, the
augmented qguad-edge', that also stores symmetrically the
primal and dual 3D subdivisions. It uses the popular quad-edge
structure (Guibas and Stolfi, 1985) originally developed for 2D
subdivisions to store individually each cell (tetrahedron or
Voronoi cell). The cells are linked together by the dual edge to
the face shared by the two cells. The data structure is very
simple to implement as only the quad-edge operators with
minor modifications are needed to construct and modily the DT
and the VD at the same time. The major limitation of this data
structure is its high storage requirements.
4. VORONOI DIAGRAM AS A SPATIAL MODEL
Two-dimensional GIS's vector-based representations describe
individually each object with geometric primitives, usually
706
points, lines and polygons. The structure of these systems is
based on the 'overlays', i.e. that the topology between objects is
based on the intersection of lines, and, moreover, the building
of this topology is a global process that needs to be done each
time there is a modification on the map. The vectorial
representation has also been extended to 3D, tor example by
Molenaar (1992), but the same ‘problems’ are present.
Modelling three-dimensional oceanographic data with such a
spatial model is obviously impossible because, firstly, the
definition of topology is not appropriate, and secondly, the
movement of objects is almost impossible.
The other spatial model used in the GIS and 3D modelling
systems is the raster representation. Such a spatial model
divides the space into regular cells that are usually squares in
2D and cubes in 3D (this is also called a voxel representation).
The raster representation is particularly useful to represent
fields or continuous phenomena because cells cover the whole
space. Although being a popular representation in geosciences
because the model gives a simple definition of spatial
relationships, it cannot represent each object individually (the
original data are "lost when converting them to raster) and the
volume of data can become enormous if one wants to have a
fine resolution, especially in 3D. To overcome the latter
problem, the octree (Samet, 1990), where voxels are indexed
and merged together to save space, can be used.
A spatial model for oceanographic data should ideally be able to
represent both discrete objects and continuous phenomena. The
Voronoi diagram has properties from both the vector and the
raster spatial models: each individual object can be represented,
and the ‘tiling’ properties give a definition of adjacency even
for unconnected objects (each point generates one cell and this
cell has some neighbours). Field-type data can be represented
by assigning an attribute value to each Voronoi cell. There are
several reasons for using a spatial model based on the Voronoi
diagram over other models:
I. This is an adaptive method, i.e. the size of the cells depends
on the distribution of the data points.
2. This is an automatic method that does not need user-defined
parameters to be constructed.
3. Original data are kept and not ‘lost’, as is the case with
raster representation.
4. By using the dual of the VD, the Delaunay
tetrahedralization, the rendering is optimised since
triangular elements are the primitives of choice for most
graphics packages and video cards.
5. Local updates to the model are possible.
S. 3DSPATIAL ANALYSIS FUNCTIONS AND
APPLICATIONS
Once the VD/DT is built, many spatial analysis operations are
possible and even simplified. This section gives some examples
of these.
5.1 Spatial Interpolation with the VD
Interpolation methods are used to estimate the value of an
attribute at unsampled locations. They are required to model,
visualise and better understand a dataset, and also to convert a
dataset to another format (c.g. from scattered data to voxels).
Traditional GIS interpolation methods (e.g. distance-based and
triangle-based methods) can be generalized to 3D but they have
many flaws when dealing with datasets having a highly irregular
distribution. These flaws are caused by the fact that these
methods do not consider the configuration of the data. It has
Intern
been s
avoids
well f
1992).
for bot
of thei
locatio
ND. T
the ne
volum
of the |
Althou
2D ap
becaus
require
one w
algorit
algorit
been d
2004).
same a
believe
known
flips, x
52 f
It is n
visuali
rotatio
unders
surfac«
implic
an iso
where
comm
cubes
voxel
rewritt
cubes:
betwec
are co
cases 1
and th
or fou
created
adjace
is idea
With t
graphi
all by
colour
inside
plays
becom
(1997)
better
S3 T
The V
with lc
As shc
operat
a map,
