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

Question

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

我正在使用这段代码：

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

在一组点上执行 voronoi 细分。

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

谢谢。

Answer 1

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

要找到给定点的 Voronoi 单元，p需要找到使用输入点的所有顶点（三角形）。而不是找到这些顶点如何通过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)