A simple and fast algorithm for computing discrete Voronoi, Johnson-Mehl or Laguerre diagrams of points - Ecole Centrale de Marseille Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2022

A simple and fast algorithm for computing discrete Voronoi, Johnson-Mehl or Laguerre diagrams of points

Résumé

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.
Fichier principal
Vignette du fichier
Moulinec_MTC_2021.pdf (774.6 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03522759 , version 1 (13-01-2022)
hal-03522759 , version 2 (31-05-2022)

Identifiants

  • HAL Id : hal-03522759 , version 1

Citer

Hervé Moulinec. A simple and fast algorithm for computing discrete Voronoi, Johnson-Mehl or Laguerre diagrams of points. 2022. ⟨hal-03522759v1⟩
201 Consultations
222 Téléchargements

Partager

Gmail Facebook X LinkedIn More