ShaPo

ShaPo: a framework for generating 2D voronoi meshes. Voronoi meshes are involved in numerous applications from astrophysics to biology or computer graphics. Their properties are especially widely used in geophysical flows and computational fluid dynamics. Our main interest in Voronoi meshes related to Reconnection-Based ALE family of methods introduced in [1]. In this talk we present ShaPo, a cross platform C++ software library accessible from different programming languages (C, Fortran and Python) that integrates algorithms to generate, in serial or in parallel, 2D Voronoi meshes from a set of generators into a domain defined by non-convex multi-connected boundary polygons. ShaPo allows to generate either Constrained Voronoi or Clipped Voronoi tessellations respectively inspired from [2, 3] and [4], and provides the full cells, points and edges connectivity. We describe the two different robust Voronoi construction algorithms implemented in ShaPo both based on the dual Delaunay triangulation computation. Proposed optimizations in regard to the original algorithms are also described. As ShaPo can also be used in a data-parallelism context where generators and boundaries are distributed across processors, a quick overview of the parallel algorithm based on an MPI communication layer is presented. Finally we describe the remeshing functionality of ShaPo which enables the generation of a Voronoi mesh in the sub-domain of an existing unstructured mesh.