在2D多边形周围生成Voronoi图 [英] Generating a Voronoi Diagram around 2D Polygons

问题描述

我正在尝试围绕2D孔(最好是在PyGame或scipy中，但不是必需的)创建一个Voronoi图并保存边缘.它看起来应该像这样:

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:

我已经能够使用 scipy的Voronoi 来生成围绕点的图，但是我不确定如何处理2D障碍.

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.

我处理点的代码是:

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障碍物(也可以是相邻的或接触的，以形成更大的障碍物)，并生成与这些障碍物等距的一组线.

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.

推荐答案

您需要的构造是中间轴.构造近似中间轴的一种方法是生成孔之间空间的约束Delaunay三角剖分.然后，通过连接相邻三角形的外接点来形成中间轴的边缘. 此处 .例8是相关位.

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.

不幸的是，scipy没有约束Delaunay三角剖分的实现.它只是具有不受约束的Delaunay三角剖分和Vornoi图，它们互为对偶.您还需要其他东西.经常使用三角形，并且似乎具有python绑定.

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.

这篇关于在2D多边形周围生成Voronoi图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！