Implementation of Additively Weighted Voronoi Diagram

[Alejo Hausner]

On Wed, 13 Mar 2002, Yaron Berman wrote:

> Do you know of an existing implementation to the Additively Weighted
> Voronoi Diagram?
> If so, is it possible to obtain it for research purposes?
> If not, can you think of some implementation of Voronoi diagrams that may
> be altered so to take into account additive weights?

If you can tolerate a pixelized approximation to
your problem, it's fairly easy to do this using graphics
hardware.  Since each Voronoi diagram is defined by
the distance function attached to each site, it's
just a matter of drawing a uniquely-coloured cone at
each site, and looking down on it from above.

To understand why this works, consider two generators,
and their associated cones.  The cones will intersect
at a hyperbola which, seen from above, is a line.
That line is the perpendicular bisector of the line
through the two points.  In other words, it's a voronoi
edge.

Of course, this only gives you a discretized approximation.
You can refine it by identifying adjacent distinctly-coloured
pixels.  If two neighbouring pixels differ, then there
is an edge between the two sites, in the Delaunay triangulation.
You can then re-draw the voronoi edge exactly.

If a colour is missing, its region was too small for the
pixel spacing, and you'll need to "zoom in" on that site
to see it.  In this way, you can reconstruct the exact
voronoi diagram, eventually.

(by the way, Fortune's sweepline alg for voronoi diagrams
 corresponds to this approach, looking down at the cones
 from a 45-degree direction)

Using different cones, you can draw different kinds of
voronoi diagrams.  I used something like this arrange
decorative mosaic tiles, and have some code for that
purpose.

Alejo Hausner (ah at dgp.utoronto.ca)


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.