[SciPy-user] voronoi diagrams and the delaunay module

[Robert Kern]

Eric Bruning wrote:
> I'd like to retrieve the Voronoi diagram for a set of points. 
> Internally, the delaunay module (in the sandbox) appears calculate the 
> voronoi diagram, but I don't think it's exposed in python.
> 
> What would need to be done do to enable voronoi output?
> 
> Eventually, I'm hoping to pass the polygons of the voronoi diagram to a 
> polycollection in matplotlib...

All of the information that you need and that the algorithm can provide is
already given. Just connect the circumcenter of each triangle to the
circumcenters of the triangle's neighbors. I left out doing much more because I
have no idea what concrete formats consumers might need. Voronoi diagrams are
somewhat abstract beasts; the circumcenters and the connections between them
(and a point at infinity) are all that is really defined for them. Doing
something concrete with them requires more information than a general tool
really has available. For example, if you are going to draw the lines out to
infinity, how should I represent them?

Forming them into polygons is a bit tricky, but not too bad. For each point in
the interior of the triangulation (i.e., points not on the convex hull), walk
around the triangles that impinge on it counterclockwise and connect their
circumcenters. To handle the edges of the Voronoi diagram that go out to
infinity, you need to know the bounding box of your display. Walk around the
edges of the convex hull, find the circumcenter of the triangle with the edge
and connect it to a point outside the display bounding box along the line from
the circumcenter perpendicular to the convex hull edge. Now walk around the
points of the convex hull, and make a Voronoi polygon for each of them using the
appropriate "points at infinity" that you made.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
 that is made terrible by our own mad attempt to interpret it as though it had
 an underlying truth."
  -- Umberto Eco