使用体素的Python高效3D Voronoi图

Question

我正在尝试使用代表体素的 3d 数组创建 Voronoi 图，其中坐标由数组的索引表示。例如：

points = np.random.random([10,3])
vox_len = 0.1
lx = ly = lz = 11
hull_space=np.zeros([lx,ly,lz],dtype=np.int16)
hull_space.fill(-1)
for i in range(lx):
    for j in range(ly):
        for k in range(lz):
            coord = np.array([i,j,k]).astype(float)*vox_len
            diff = points - coord
            dist = np.sqrt(diff[:,0]**2 + diff[:,1]**2 + diff[:,2]**2)
            closest = np.argmin(dist)
            hull_space[i][j][k]=closest

问题是对于较大的数组，代码非常慢。我也试过：

grid = np.indices((lx,ly,lz)).astype(float)*vox_len
hull_space = np.ones([lx,ly,lz],dtype=np.int16)
hull_space.fill(-1)
closest_dist = np.ones(hull_space.shape)
closest_dist.fill(999)
for index,point in enumerate(points):
    dist2 = (grid[0]-point[0])**2 + (grid[1]-point[1])**2 + (grid[2]-point[2])**2
    hull_space[dist2 < closest_dist]=index
    closest_dist[dist2 < closest_dist]=dist2[dist2 < closest_dist]

但结果更糟糕。我知道 scipy 的 voronoi 图方法，但我需要构建一个体素图像才能对 voronoi 区域的边缘进行距离变换。我的目标是创建纠缠纤维结构的图像，以用于孔隙网络模型，体素方法对于获取孔体积很有用。

任何帮助使算法运行得更快将不胜感激。对于 300x300x300 的 500 点图表，在我的机器上大约需要 50 分钟

Answer 1

您可以尝试对点进行排序。将坐标视为二进制并交错。然后以两种方式对其进行排序。事实上，Cgal使用相同的算法。