Python – Calculating Voronoi Diagrams for Polygons

delaunayvoronoi-thiessen

There are a variety of good algorithms for generating the Voronoi polygons or their complement, the Delaunay Triangulation for a set of points.

My question is simply, is there an algorithm for generating the Voronoi diagram for a set of input polygons, rather than points?

One technique I've explored is breaking my polygons into sets of vertices, and creating the Voronoi diagrams for those, then combining the resulting shapes for each set of vertices belonging to a particular input polygon. The results are not totally accurate, however. Does anyone have an alternate technique?

EDIT:

Here is a super rough hand-drawn example of what I'm after. I have a set of polygons with gaps. I'm trying to create output polygons with no gaps between them. Ultimately I want to use this to say whether any two nearby polygons can be considered "adjacent" to one another, even if they are not touching.

Best Answer

I posted a mini python package to make it - voronoi-diagram-for-polygons. It should be pointed out in advance that this package depends on v1.8.dev0 of shapely which is still in development. In other words, it cannot be installed by pip automatically. You have to install it by the following:

pip install git+https://github.com/Toblerity/Shapely.