CODEWITHSUNDEEP
pythongraphgraphicsscipypygame
Teknophilia
Teknophilia

Reputation: 778

Generating a Voronoi Diagram around 2D Polygons

I'm trying to create a Voronoi diagram around 2D holes (preferably in PyGame or scipy, but not necessary) and save the edges. It should look something like this: enter image description here

I have been able to use scipy's Voronoi to generate a diagram around points, but I'm not sure how to proceed with 2D obstacles.

My code for working with points is:

self.vor = Voronoi(POINTS)

# iterate over voronoi graph and save edges
for vpair in self.vor.ridge_vertices:
    if vpair[0] >= 0 and vpair[1] >= 0:
        # vertices
        v0 = self.vor.vertices[vpair[0]]
        v1 = self.vor.vertices[vpair[1]]

        # edge endpoints
        start_point = (v0[0], v0[1])  # start point
        end_point = (v1[0], v1[1])

Basically, I want to input 2D obstacles (which could also be adjacent/touching so as to form a larger obstacle) and generate a set of lines which are equidistant from those obstacles.

Upvotes: 0

Views: 2638

Answers (2)

Bruce Xiaolong Liu
Bruce Xiaolong Liu

Reputation: 1

I posted a mini python package to make it - voronoi-diagram-for-polygons. You can find an example output from here. 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.

Upvotes: 0

Bill
Bill

Reputation: 488

The construction you need is a medial axis. One way of constructing an approximate medial axis is to generate a constrained Delaunay triangulation of the space between the holes. Edges of the medial axis are then formed by connecting the circumcentres of adjacent triangles. There's quite a good matlab tutorial here. Example 8 is the relevant bit.

Unfortunately, scipy doesn't have an implementation of constrained Delaunay triangulation. It just has unconstrained Delaunay triangulations and Vornoi diagrams, which are dual to each other. You will need something else. Triangle is commonly used, and appears to have python bindings.

Upvotes: 1

Related Questions