Comment 2 for bug 171901

Bill Baxter wrote:
Doing Voronoi diagrams (and delaunay triangulations) robustly is
tricky. Simpler algorithms tend to barf on input that has too many
collinear points, or has points placed exactly on a grid. And the
textbook implementations usually avoid constraints altogether.
But the Triangle lib by Jonathan Shewchuk handles all that and more
quite beautifully and can create both Voronoi diagrams and Delaunay
triangulations of the interiors of arbitrary polygons. (Arbitrary in
the sense of being concave and having holes. Probably not
self-intersecting ones, though I haven't tried that).

http://www.cs.cmu.edu/~quake/triangle.html

The license is a bit odd though. Has some odd advertising
requirements and commercial product restrictions:
------------------------------------------------------------------------------

These programs may be freely redistributed under the condition that the
copyright notices (including the copy of this notice in the code comments
and the copyright notice printed when the `-h' switch is selected) are
not removed, and no compensation is received. Private, research, and
institutional use is free. You may distribute modified versions of this
code UNDER THE CONDITION THAT THIS CODE AND ANY MODIF

---
Aaron Spike wrote:

Livarot used to do Voronoi diagrams.

http://livarot.sourceforge.net/

:-)