圍繞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綁定。