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:

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.

Answers


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.


Need Your Help

get top most result of one of the table in join

sql oracle oracle11g

I need to 3 join three tables TM, TA, MS - TA has multiple records for each row in TM I need to get the last row from TA for ever row in TM based a field called status which is highest for the new...