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 区域的边缘进行距离变换。我的目标是创建缠结纤维结构的图像以用于孔隙网络模型，体素方法对于获取孔隙体积很有用。

如果能帮助算法运行更快，我们将不胜感激。对于包含 500 个点的 300x300x300 图表，在我的机器上大约需要 50 分钟

Answer 1

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

python 使用体素的高效 3d voronoi 图

python efficient 3d voronoi diagram using voxels

python

voronoi

voxel