Voronoi入门1

Voronoi入门1

建议先看一下voronoi的基本概念：

【数学之美】泰森多边形的构造和应用_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Ea4y1H7LT

Voronoi详细代码以及请参考：

Spatial data structures and algorithms (scipy.spatial) — SciPy v1.7.1 Manualhttps://docs.scipy.org/doc/scipy/reference/tutorial/spatial.html本文适用于刚学习voronoi小白，并对上面链接中解释不详细的地方进行一定的解释

上源码，可直接使用Python编译器编译：（如果编译不了，显示numpy等用不了请百度自行解决）

from scipy.spatial import *
import numpy as np
import random
import matplotlib.pyplot as plt

points = np.array([[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2],
                   [2, 0], [2, 1], [2, 2]])
vor = Voronoi(points)

vor.vertices
vor.regions
vor.ridge_vertices 
vor.ridge_points

print(vor.vertices,vor.regions,vor.ridge_vertices,vor.ridge_points)

plt.plot(points[:, 0], points[:, 1], 'o')
plt.plot(vor.vertices[:, 0], vor.vertices[:, 1], '*')
plt.xlim(-1, 3); plt.ylim(-1, 3)
# plt.show()

for simplex in vor.ridge_vertices:
    simplex = np.asarray(simplex)
    if np.all(simplex >= 0):
        plt.plot(vor.vertices[simplex, 0], vor.vertices[simplex, 1], 'k-')
# plt.show()  #画出四个质心点的框

center = points.mean(axis=0)
for pointidx, simplex in zip(vor.ridge_points, vor.ridge_vertices):
    simplex = np.asarray(simplex)
    if np.any(simplex < 0):
                i = simplex[simplex >= 0][0]  # finite end Voronoi vertex
                t = points[pointidx[1]] - points[pointidx[0]]  # tangent
                t = t / np.linalg.norm(t)
                n = np.array([-t[1], t[0]])  # normal
                midpoint = points[pointidx].mean(axis=0)
                far_point = vor.vertices[i] + np.sign(np.dot(midpoint - center, n)) * n * 100
                plt.plot([vor.vertices[i, 0], far_point[0]],
                         [vor.vertices[i, 1], far_point[1]], 'k--')
plt.show()

可得到结果：

为了便于理解，将上述结果图做一定的标记，如下:

（此图转载自于如下连接，如有侵权，联系删除）python 泰森多边形法函数属性理解（python Voronoi function properties explained in detial) - ttweixiao9999 - 博客园 (cnblogs.com)https://www.cnblogs.com/ttweixiao-IT-program/p/14374270.html

 图1 

points = np.array([[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2],[2, 0], [2, 1], [2, 2]])

 points对应图1中的point0,point1,……,point8

>>vor.vertices
#输出结果为：
[[0.5 0.5]
 [0.5 1.5]
 [1.5 0.5]
 [1.5 1.5]]

vor.vertices对应的是图橙色的四个点，即voronoi的四个顶点vertice0,vertice1,vertice2,vertice3,这四个顶点的顺序以及数值很重要，后面要考。

>>vor.regions
[[], [-1, 0], [-1, 1], [1, -1, 0], [3, -1, 2], [-1, 3], [-1, 2], [0, 1, 3, 2], [2, -1, 0], [3, -1, 1]]

vor.regions里面存储的索引要结合上面vor.vertices的值来看（注意：-1表示voronoi 的顶点在无穷远处）。结合图1，vor.regions [-1, 0] 表示该区域中一个voronoi的顶点是vertice 0,另一个顶点在无穷远处，由此可以确定voronoi region1（对应图1中蓝色字体）。

再看，vor.regions [1, -1, 0]，表示该区域的两个voronoi的顶点是 vertice 0和vertice 1，还有一个顶点在无穷远处，由此课确定voronoi region3(对应图1中蓝色的字体)。

再看一个比较特殊的，vor.regions [0, 1, 3, 2]，表示该区的四个顶点是分别vertice 0, vertice 1, vertice 3, vertice2.由此可确定voronoi region7(对应图1中蓝色的字体)

由上可以推出其他的voronoi region区域

注意vor.regions里面存储的索引[-1, 0], [-1. 1], [1, -1, 0]……[3, -1,1 ]分别对应voronoi region1, voronoi region2, voronoi region3, …… , voronoi region9， 是有顺序的

>>vor.ridge_vertices 
[[-1, 0], [-1, 0], [-1, 1], [-1, 1], [0, 1], [-1, 3], [-1, 2], [2, 3], [-1, 3], [-1, 2], [1, 3], [0, 2]]

vor.ridege_vertices里面存储的索引对应图1中的ridge line0, ridege line1, …… ,ridge line 11, 同上文-1表示顶点在无穷远处

vor.ridege_vertices表示构成每个 Voronoi 脊线（ridge line）的 Voronoi 顶点（vertices）索引，要结合vertice顶点来区分，[-1, 0]表示脊线的一个顶点在vertice0，另一个在无穷远处，[-1, 3]表示其中一个顶点在vertice3另一个在无穷远处，由此规律可以找出ridge line0, ridege line1, …… ,ridge line 11所在的位置。

>>vor.ridge_points
[[0 3]
 [0 1]
 [2 5]
 [2 1]
 [1 4]
 [7 8]
 [7 6]
 [7 4]
 [8 5]
 [6 3]
 [4 5]
 [4 3]]

vor.ridge_points表示每条 Voronoi 脊线（ridge line）附近的点（points）的索引，即每条脊线的控制点。

结合图1，可以看到ridge line1的控制点为point0，point3，即对应输出结果的[0, 3]，ridege line2对应的控制点为point0和point1，即对应输出结果的[0, 1]

注意：vor.ridge_points里面存储的索引也存在一一对应的关系

for simplex in vor.ridge_vertices:
    simplex = np.asarray(simplex)
    if np.all(simplex >= 0):
        plt.plot(vor.vertices[simplex, 0], vor.vertices[simplex, 1], 'k-')

经过上面对每个参数的详细解释，此段代码使用了for循环连接图1中4个Vertices0,1,2,3顶点。ridge_vertices里面存储的索引是4个顶点之间的连接线，且只有大于0的时候才说明这条连接线是4个顶点之间的连接线。

center = points.mean(axis=0)
for pointidx, simplex in zip(vor.ridge_points, vor.ridge_vertices):
    simplex = np.asarray(simplex)
    if np.any(simplex < 0):
                i = simplex[simplex >= 0][0]  # finite end Voronoi vertex
                t = points[pointidx[1]] - points[pointidx[0]]  # tangent
                t = t / np.linalg.norm(t)
                n = np.array([-t[1], t[0]])  # normal
                midpoint = points[pointidx].mean(axis=0)
                far_point = vor.vertices[i] + np.sign(np.dot(midpoint - center, n)) * n * 100
                plt.plot([vor.vertices[i, 0], far_point[0]],
                         [vor.vertices[i, 1], far_point[1]], 'k--')
plt.show()

此段代码为画出图1中的虚线，不做详解。

此文主要为了解释vor.vertices，vor.regions，vor.ridge_vertices，vor.ridge_points四个参数里面存储的是什么索引，当弄清楚这4个参数的存储值，即可明白后面两个循环的意义。

如果有任何疑问或者解释不清楚的地方请在下方留言，本人也是刚开始接触Voronoi图，如果解释不太清楚的地方，敬请留情。