From: Jeff Erickson
Newsgroups: comp.graphics.algorithms,sci.math.num-analysis
Subject: Re: Voronoi diagrams of convex sites
Date: Thu, 17 Dec 1998 11:46:06 -0600
ACARY wrote:
> I'm searching for algorithms which compute Voroinoi diagrams for a set
> of line segments and convex polygons.
> Where Can I find informations about such algorithm ( Stability,
> robustness, implementation ).
Probably the most robust and stable implementation in existence is by
Martin Held, described in his paper ``Voronoi Diagrams and Offset Curves
of Curvilinear Polygons'', Comput. Aided Design 30(4):287-300, 1998.
Once nice feature of this algorithm is that it also handles polygons
with circular-arc edges almost for free.
You can see some examples of his algorithm's output at
http://www.cosy.sbg.ac.at/~held/projects/voronoi_2d/voronoi.html
You can't download his Voronoi diagram code off the web, but you can get
it by sending him email.
--
Jeff Erickson jeffe@cs.uiuc.edu
Computer Science Department http://www.uiuc.edu/ph/www/jeffe
University of Illinois, Urbana-Champaign