论文标题
用于计算离散Voronoi，Johnson-Mehl或Laguerre点的简单快速算法
A simple and fast algorithm for computing discrete Voronoi, Johnson-Mehl or Laguerre diagrams of points
论文作者
论文摘要
本文提出了一种算法，以计算一组守时站点的Voronoi，Johnson-Mehl或Laguerre图的数字图像，该图像在任何维度的欧几里得空间的域中。算法的原理是第一步，研究以围绕地点为中心的球中的体素，并在第二步中处理保留在球外部的体素。可以通过分析或数字确定球半径的最佳选择，这允许在$ O（N_V \ ln N_S $）中执行该算法的性能，其中$ n_v $是该域的素数和$ n_s $ $ n_s $ tessellation的数量。考虑了周期性和非周期性边界条件。该算法的主要优势在于它的简单性使其非常容易实施。这使得该算法适用于创建包含大量单元的微结构的高分辨率图像，特别是当使用基于FFT的均质化方法的计算时，将其应用于模拟材料。
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.
