编辑voronoi类以在python中返回多边形点 [英] Editing voronoi class to return polygon points in python

问题描述

我会使用这段代码：

https://bitbucket.org/mozman/geoalg /src/5bbd46fa2270/geoalg/voronoi.py

在一组点上执行voronoi tesselation。
$ b $它可以工作，但问题是代码只提供了用于创建多边形的所有顶点的列表，以及哪些对必须连接在一起。它没有提供任何信息，用于构成每个多边形，我需要哪些点。

谢谢。

解决方案

context.triangles 表示Delaunay三角形输入点参与其中。每个三角形都与Voronoi顶点相关。三角形和顶点并行存储在三角形和顶点数组中。

要找到给定点 p 的Voronoi单元格，需要找到所有使用输入点的顶点（三角形）。而不是找到这些顶点如何通过边数组连接。

这是一个简单的（未经过测试的）代码如下：

  from voronoi import voronoi 
从集合中导入随机
 import defaultdict 
 
 num_points = 50 
 points = [（random.uniform（0,10），random.uniform（0,10））for xrange（num_points）] 
c = voronoi（points ）
 
＃对于每个点查找单元格的三角形（顶点）
 point_in_triangles = defaultdict（set）
 for t_ind，ps in enumerate（c.triangles）：
对于p in ps：
 point_in_triangles [p] .add（t_ind）
 
＃顶点连接图
 vertex_graph = defaultdict（set）
 for e_ind，（_ （c.edges）：
 vertex_graph [r] .add（l）
 vertex_graph [l] .add（r）
 
 def cell（点）：
如果点不在point_in_triangles中：
 return None 
 vertices = set（point_in_triangles [point]）＃copy 
 v_cell = [vertic es.pop（）] 
 vertices.add（-1）＃模拟无限:-) 
顶点：$ b​​ $ b neighbors = vertex_graph [v_cell [-1]]&顶点
如果不是邻居：
 break 
 v_cell.append（neighbours.pop（））
 vertices.discard（v_cell [-1]）$ ​​b $ b返回v_cell 
 
 for xrange（num_points）：
 print p，cell（p）
  

Would anyone with Python experience be able to take a look at this for me?

I'm using this code:

https://bitbucket.org/mozman/geoalg/src/5bbd46fa2270/geoalg/voronoi.py

to perform voronoi tesselation on a group of points.

It works, but the problem is that the code only provides a list of all the vertices used to create the polygons, and which pairs must be joined together. It doesn't provide any information as to what points are used to make up each polygon, which I need.

Thanks.

解决方案

context.triangles says in which Delaunay triangles input point participate. Each triangle is related to a Voronoi vertex. Triangles and vertices are stored parallel in triangles and vertices arrays.

To find Voronoi cell for a given point p, it is needed to find all vertices (triangles) in which input point is used. And than find order how these vertices are connected by edges array.

Here is a simple (not quite tested) code to do that:

from voronoi import voronoi
import random
from collections import defaultdict

num_points = 50
points = [(random.uniform(0,10), random.uniform(0,10)) for i in xrange(num_points)]
c = voronoi(points)

# For each point find triangles (vertices) of a cell
point_in_triangles = defaultdict(set)
for t_ind, ps in enumerate(c.triangles):
    for p in ps:
        point_in_triangles[p].add(t_ind)

# Vertex connectivity graph
vertex_graph = defaultdict(set)
for e_ind, (_, r, l) in enumerate(c.edges):
    vertex_graph[r].add(l)
    vertex_graph[l].add(r)

def cell(point):
    if point not in point_in_triangles:
        return None
    vertices = set(point_in_triangles[point]) # copy
    v_cell = [vertices.pop()]
    vertices.add(-1)  # Simulate infinity :-)
    while vertices:
        neighbours = vertex_graph[v_cell[-1]] & vertices
        if not neighbours:
            break
        v_cell.append(neighbours.pop())
        vertices.discard(v_cell[-1])
    return v_cell

for p in xrange(num_points):
    print p, cell(p)

这篇关于编辑voronoi类以在python中返回多边形点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！