Newsgroups: comp.infosystems.gis
Date:         Mon, 14 Dec 1992 16:02:03 HNE
From:         Chris Gold <CGOLD@VM1.ULAVAL.CA>
Subject:      Re: Voronoi Tessalation GIS
              11 Dec 1992 11:17:00 GMT from <STGG8004@IRUCCVAX.UCC.IE>

Recently Darius Bartlett asked me on GIS-L about the Voronoi work
that I have been doing (thanks for the plug, Darius). I will attempt to
give a brief summary (well, try, anyway).

Traditional Voronoi/Thiessen/Dirichlet tesselations, and the dual-graph
equivalent, the Delaunay triangulation, have been around for perhaps 15
years, in the form of functional algorithms. Most of these methods find
the proximal regions around each of a set of data points using either
incremental or divide-and-conquer methods. This means that they are
static ("batch") or at most incrementally updateable.

My early work was concerned with interpolation - firstly triangulation,
then what I call the "area-stealing" method, based on inserting a
sampling point into the Voronoi diagram of the data points, and seeing
how much of the neighbouring Voronoi polygons' areas had been stolen.
Thsi turned to be (in my opinion) an ideal way of combining the old
interpolation problems of selecting a set of neighbours, and then
selecting appropriate weights for each of them. The result is a
surface that always honours the data points, whatever their distribution.
A couple of minor modifications take care of slope continuity at data
points, and honouring data point slope values, if available. This stuff
is best described in Ch. 3 of "#-D applications in GIS", 1989, Jonathan
Raper, ed.

(Correction: "3-D applications)

This idea of a sampling point led to the idea of a point moving within
the Voronoi tesselation, its own "bubble" touching (and stealing area
from) different neighbours as it moved. It was clearly possible to
maintain a type of topology (the Delaunay triangulation) that kept
track of the neighbours of this point as its set of neighbours changed.

Once this was achieved it became easy (well, relatively) to have a
fully dynamic system where points could be created or deleted by
splitting them off from existing points, and then moving them to their
desired destination (and reversing the process for deletion). This
produces a "dynamic" data structure in the true sense, as used in
data base index trees, etc, where objects may be added, subtracted or
modified without having to rebuild the whole thing. (GISs, in general
are not dynamic in their spatial data structure - although there are
some exceptions).

The next bright idea was to allow the moving point to become a "pen"
and leave a line behind it as it moved. This gave a Voronoi diagram
consisting of a contiguous set of tiles (the Voronoi polygons), each
one having a "generator" in its interior - either a point, as in the
usual Voronoi diagram, or, now, the interiors of line segments. This
then became a fully dynamic spatial data structure permitting the
construction of complex objects out of points and line-segments.

One may ask why to bother (working out the rules took several years).
One answer is that the resulting structure is the same, whether the
problem is interpolation (see above), a vector polygon topology
(albeit with many more links than the usual polygon-arc-node stuff),
or a field representation methodology for arbitrarily-distributed
data (a raster can be thought of as a regularly-spaced Voronoi).

The second answer is that, at least potentially, many more operations
may be done with a dynamic system than with a static one. Imagine
being able to edit a polygon map and have the topology be verified
immediately (yes I know that it is coming with commercial systems,
but you must admit that it took a long time). Imagine being able to
run a robot about in your map, finding the best path and bumping
into things. Imagine being able to simulate moving cells, e.g. for
atmospheric simulation with the Free-Lagrange method. Imagine being
able to run a "movie" of the sequence of digitizing commands used to
construct your map in the first place (or undraw the map, by running
it backwards). Yes Virginia (sorry  - Darius) there IS a possible
strategy for working with time-varying GIS.

Well, I have talked long enough on this - some of it is in the
Charleston Spatial Data Handling Proceedings. It is NOT yet a
commercial product, and may never be, but it exists at the demonstration
level - not yet fully bug-free, but clearly proving that it is doable.

Cheers,   Chris Gold
          Chaire industrielle en geomatique
          Centre de recherche en geomatique, Universite Laval
          Pavillin Casault, Local 1349
          Quebec, Qc, Canada G1K 7P4.