如何为具有物理限制的随机点创建修改的 voronoi 算法

Question

毫无疑问，Voronoi 算法提供了一种可行的方法，可以根据到平面特定子集中的点的距离将平面划分为多个区域。这样一组点的 Voronoi 图是其 Delaunay 三角剖分的对偶。 现在可以通过使用模块 scipy 作为直接实现这个目标

import scipy.spatial

point_coordinate_array = np.array(point_coordinates)
delaunay_mesh = scipy.spatial.Delaunay(point_coordinate_array)
voronoi_diagram = scipy.spatial.Voronoi(point_coordinate_array)

# plot(delaunay_mesh and voronoi_diagram using matplotlib)

当预先给定点数时。结果如图1所示，

其中绿色虚线包围的区域是所有点的德劳内三角形，蓝色实线的封闭区域当然是中心点的voronoi单元（为了更好的可视化，这里只显示封闭区域）

直到现在，一切都被认为是完美的。但在实际应用中，所有的点都可能有自己的物理意义。（例如，当这些点代表自然粒子时，它们可能具有“半径”变量）。而上面常见的voronoi算法，对于这种可能需要考虑复杂物理限制的情况，或多或少是不合适的。如图 2 所示，voronoi 单元的脊可能与粒子边界相交。已经不能满足生理要求了。

我现在的问题是如何创建一个修改过的 voronoi 算法（也许它不能再被称为 voronoi）来处理这个物理限制。这个目的大致如图3所示，蓝色虚线封闭的区域正是我想要的。

所有的点数要求是：

1.numpy-1.13.3+mkl-cp36-cp36m-win_amd64.whl

2.scipy-0.19.1-cp36-cp36m-win_amd64.whl

3.matplotlib-2.1.0-cp36-cp36m-win_amd64.whl

并且都可以直接在http://www.lfd.uci.edu/~gohlke/pythonlibs/下载

我的代码已更新以进行更好的修改，它们是

import numpy as np
import scipy.spatial
import matplotlib as mpl
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
from matplotlib.collections import PatchCollection

# give the point-coordinate array for contribute the tri-network.
point_coordinate_array = np.array([[0,0.5],[8**0.5,8**0.5+0.5],[0,-3.5],[-np.sqrt(15),1.5]])

# give the physical restriction (radius array) here.
point_radius_array = np.array([2.5,1.0,1.0,1.0])

# create the delaunay tri-mesh and voronoi diagram for the given points here.
point_trimesh = scipy.spatial.Delaunay(point_coordinate_array)
point_voronoi = scipy.spatial.Voronoi(point_coordinate_array)

# show the results using matplotlib.
# do the matplotlib setting here.
fig_width = 8.0; fig_length = 8.0
mpl.rc('figure', figsize=((fig_width * 0.3937), (fig_length * 0.3937)), dpi=300)
mpl.rc('axes', linewidth=0.0, edgecolor='red', labelsize=7.5, labelcolor='black', grid=0)
mpl.rc('xtick.major', size=0.0, width=0.0, pad=0)
mpl.rc('xtick.minor', size=0.0, width=0.0, pad=0)
mpl.rc('ytick.major', size=0.0, width=0.0, pad=0)
mpl.rc('ytick.minor', size=0.0, width=0.0, pad=0)
mpl.rc('figure.subplot', left=0.0, right=1.0, bottom=0.065, top=0.995)
mpl.rc('savefig', dpi=300)
ax_1 = plt.figure().add_subplot(1, 1, 1)
plt.gca().set_aspect('equal')
ax_1.set_xlim(-5.5, 8.5)
ax_1.set_ylim(-4.5, 7.5)
ax_1.set_xticklabels([])
ax_1.set_yticklabels([])

# plot all the given points and vertices here.
ax_1.scatter(point_coordinate_array[:,0],point_coordinate_array[:,1],
             s=7.0,c='black')
ax_1.scatter(point_voronoi.vertices[:,0],point_voronoi.vertices[:,1],
             s=7.0,c='blue')

# plot the delaunay tri-mesh here.
ax_1.triplot(point_trimesh.points[:,0],point_trimesh.points[:,1],
             point_trimesh.vertices,
             linestyle='--',dashes=[2.0]*4,color='green',lw=0.5)

# plot the voronoi cell here.(only the closed one)
ax_1.plot(point_voronoi.vertices[:,0],point_voronoi.vertices[:,1],
          lw=1.0,color='blue')
ax_1.plot([point_voronoi.vertices[-1][0],point_voronoi.vertices[0][0]],
          [point_voronoi.vertices[-1][1],point_voronoi.vertices[0][1]],
          lw=1.0,color='blue')

# plot all the particles here.(point+radius)
patches1 = [Circle(point_coordinate_array[i], point_radius_array[i]) 
            for i in range(len(point_radius_array))]
ax_1.add_collection(PatchCollection(patches1, linewidths=1.0, 
                    edgecolor='black', facecolors='none', alpha=1.0))
# save the .png file.
plt.savefig('Fig_a.png',dpi=300)
plt.close()

Answer 1

它应该通过功率图方法来解决。您可以找到 2D Power 图的算法：

• 在之前的一个问题中
• 在GitHub中

功率图是由空间中一组有限的圆构成的。给定圆的像元由到该圆的幂距离小于到其他圆的幂距离的所有点组成。点的幂距定义为该点到圆心的距离的平方减去圆半径的平方。

电源图具有直的单元边缘。这似乎与问题相对应。加权 Voronoi 图也存在，但可以具有圆弧边。