围绕2D多边形生成Voronoi图

Question

我试图围绕2D空洞创建Voronoi图（最好在PyGame或scipy中，但不是必需的）并保存边缘。它应该看起来像这样：

我已经能够使用scipy's Voronoi围绕点生成一个图，但我不知道如何处理2D障碍。

我的用于与点工作的代码是：

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]) 

基本上，我想输入的2D障碍物（其也可以是相邻的/接触，以便形成一个更大的障碍）并生成一组线，其与这些障碍等距。

Answer 1

你需要的结构是一个中轴。构建近似中轴的一种方法是生成孔之间空间的约束德劳内三角剖分。然后通过连接相邻三角形的外围中心形成中轴的边缘。有相当不错的matlab教程here。例8是相关位。

不幸的是，scipy没有约束Delaunay三角剖分的实现。它只是具有无约束的Delaunay三角剖分和Vornoi图，它们彼此是双重的。你需要别的东西。通常使用Triangle，似乎有python绑定。