Generating a Voronoi Diagram around 2D Polygons
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 and vpair >= 0: # vertices v0 = self.vor.vertices[vpair] v1 = self.vor.vertices[vpair] # edge endpoints start_point = (v0, v0) # start point end_point = (v1, v1)
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.
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.