Calculating Voronoi Diagrams for polygons

Question

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.

EDIT 2 The accepted solution is still a good answer, but I was so consumed by the adjacency question that I created a Python package to do this job, using Voronoi diagrams. It doesn't create a perfect diagram for polygons, but it does "densify" then with additional vertices as necessary: https://pypi.org/project/geo-adjacency/ https://medium.com/@penguinboy561/finding-adjacent-geometries-with-python-a68bb766fff1

Could you give an application example or how you intend to use them? Maybe this could clarify your needs. — Nikos, May 02 '17 at 21:43
I think you mean "complement" where you have "corollary", but I agree a diagram would be helpful. Do you have polygons and then some blank areas (which are also technically polygons) and you want to Voronoize the blank areas? — , May 03 '17 at 00:17

score 8 · Accepted Answer · answered Jul 29 '20 at 15:04

8

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.

answered Jul 29 '20 at 15:04

Bruce Xiaolong Liu

136
1
2

Thank you I am also trying to do this (to include some points which contain addresses around existing land parcels). I went to OSGeo4W Shell and typed python -m pip install git+https://github.com/Toblerity/Shapely then Enter but it doesn't work. Do you know how I could download your plugin? Thank you very much again, that would help me a lotl! 謝謝你！ – Philippe Morgan Sep 06 '20 at 21:09
1

How about python -m pip install git+https://github.com/Toblerity/Shapely? – Bruce Xiaolong Liu Sep 18 '20 at 05:27

score 3 · Answer 2 · answered Apr 16 '18 at 07:25

The easiest way I found is using PostGIS to create buffers and then use use ST_ApproximateMedialAxis. It is (slightly) approximate but it does work really well in the vast majority of cases. It allows much better results than using buffer and then use the centroid of the polygons to generate a Voronoi Diagram to clip it with.

In practice, the buffer size needs to be large enough so the generated buffers overlap each other. Then ST_Union will dissolve the buffers, you then cut the resulting dissolved buffer layer by clipping it with the original one. The result is a large dissolved buffer with holes. It's this buffer that needs to be processed by ST_ApproximateMedialAxis.

Finally, the polygons that do not touch the original ones need to be deleted with ST_Touches, which is also very good to grab attributes of the original set of polygons:

ST_VoronoiPolygons doesn't produce the expected result in my situation:

score 2 · Answer 3 · answered May 03 '17 at 07:38

2

You may search publications about "Segment Voronoi Diagram" or perhaps also "Medial Axis". CGAL offers Segment Voronoi Diagrams.

answered May 03 '17 at 07:38

Geom

121
2

It seems like this could be workable if I can create the Voronoi diagram for each segment in a given polygon, and then join together. – AJSmyth May 03 '17 at 22:08

score 2 · Answer 4 · answered Jul 25 '17 at 22:12

I like the answer which mentioned "Segment Voronoi diagrams," but I ultimately found it difficult to implement in my particular workflow. I found that because my geometries were fairly detailed (i.e., they had a large number of vertices compared to their area) I was able to calculate the voronoi diagram for the vertices of all input polygons using ST_VoronoiPolygons in PostGIS. Then I intersected those voronoi polygons with the input geometries and unioned them accordingly. The resulting polygons were good enough to tell me which polygons were adjacent (that is, it was possible to cast a ray from at least some point on Polygon A to Polygon B without hitting any Polygon C) without the polygons actually touching. This method obviously has some limitations; if your geometries are not detailed enough, the results will be less accurate. In my case, it was good enough.

score 0 · Answer 5 · answered May 04 '17 at 00:11

0

Do you have to use Voronoi tesselation, or are you simply looking for a means to fill the gaps between polygons? Are you working with a particular GIS suite? I ask because you might use something like Euclidean Allocation in ArcGIS to get at a suitable result. The tool outputs a raster, but that could be converted back to polygons if required.

answered May 04 '17 at 00:11

Jae

1,302
8
10

The ultimate goal is to determine which polygons are adjacent to which. This method might be a decent approximation, though I worry about performance; I would need to run this function 100s of thousands of times using rather large rasters at times. – AJSmyth May 04 '17 at 23:57

Calculating Voronoi Diagrams for polygons

5 Answers5

Linked