This article presents an algorithm to compute digital images of Voronoi, Johnson-Mehl or Laguerre diagrams of a set of punctual sites, in a domain of a Euclidean space of any dimension. The principle of the algorithm is, in a first step, to investigate the voxels in balls centred around the sites, and, in a second step, to process the voxels remaining outside the balls. The optimal choice of ball radii can be determined analytically or numerically, which allows a performance of the algorithm in $O(N_v \ln N_s$), where $N_v$ is the total number of voxels of the domain and $N_s$ the number of sites of the tessellation. Periodic and non-periodic boundary conditions are considered. A major advantage of the algorithm is its simplicity which makes it very easy to implement. This makes the algorithm suitable for creating high resolution images of microstructures containing a large number of cells, in particular when calculations using FFT-based homogenisation methods are then to be applied to the simulated materials.
翻译:本篇文章提出了一个算法,用于计算Voronoi、Johnson-Mehl或Laguerre图中一组准时站点的数字图像,位于任何维度的欧几里德空间域内。算法的原则是,第一步调查圆球周围球体中的氧化物,第二步是处理球体外的氧化物。可以分析或用数字方式确定球射线的最佳选择,这样就可以用$O(N_v =lnN_s$)来进行算法,其中,$N_v$是域的氧化物总数,而$N_s$是星系的数。考虑的是周期和非周期边界条件。算法的主要优点是其简单性,因此很容易执行。这使算法适合于生成含有大量细胞的高分辨率的微结构图象,特别是在使用基于FFT的同源方法进行计算时,然后适用于模拟材料。