python - 编辑 voronoi 类以返回 python 中的多边形点

Question

有 Python 经验的人能帮我看看这个吗？

我正在使用这段代码:

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

对一组点执行 voronoi 镶嵌。

它有效，但问题是代码只提供了用于创建多边形的所有顶点的列表，以及哪些对必须连接在一起。它没有提供关于使用哪些点来构成我需要的每个多边形的任何信息。

谢谢。

Answer 1

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

要找到给定点 p 的 Voronoi 单元，需要找到使用输入点的所有顶点(三角形)。然后找到这些顶点如何通过 edges 数组连接的顺序。

这是一个简单的(未经充分测试的)代码:

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)