Edit on GitHub

[Improving Voronoi meshes for FV ]

It has been shown that finite volume methods for elliptic PDE should be more accurate if for each generator the distance to its vertices is approximately equal. This can be achieved as follows:

mynodes = VoronoiNodes(rand(2,200))
VG1 = VoronoiGeometry(copy(mynodes),cuboid(2,periodic=[]),integrator=VI_GEOMETRY)
draw2D(VG1)
VG2 = VoronoiGeometry(copy(mynodes),cuboid(2,periodic=[]),integrator=VI_GEOMETRY,improving=(max_iterations=5,))
draw2D(VG2)

The above example generates two Voronoi grids: One where mesh is generated from the given nodes and one using the improving keyword, where the nodes are modified so that the nodes will lie closer to the centers of mass of their respective Voronoi cell. This is an iterative process and takes the following parameters:

  • max_iterations::Int = 1: The process will stop after this amount of iterations even if the wanted accuracy is not achieved.
  • tolerance::Float64 = 1.0: if the distance between a node and the center of mass D and the minimal distance of the node to the boundary r satisfy D/r < tolerance the node will not be modified.

The following pictures illustrate the improvement of the mesh for standard setting and 200 Points in $\mathbb R^2$:

Original Mesh

original

Modified Mesh

nodes versus time in 5D

improving Syntax

Simple_LLoyd

When called as above, HighVoronoi will call the improving-mode called Simple_LLoyd. That is a method that calculates for each cell the average of all vertices and takes this as the new center of the cell if the shift is more than tolerance. The two equivalent calls are

mynodes = VoronoiNodes(rand(2,200))
VG1 = VoronoiGeometry(copy(mynodes), cuboid(2,periodic=[]), integrator=VI_GEOMETRY, improving=(max_iterations=5,tolerance=0.1))
draw2D(VG1)
VG2 = VoronoiGeometry(copy(mynodes), cuboid(2,periodic=[]), integrator=VI_GEOMETRY, improving=( method=Simple_LLoyd(5,0.1), silence=false))
draw2D(VG2)

Note that the second call introduces silence to optionally suppress output during improving.

LLoyd

This is the actual implementation of the classical LLoyd Algorithm. 

mynodes = VoronoiNodes(rand(2,200))
VG1 = VoronoiGeometry(copy(mynodes),cuboid(2,periodic=[]),integrator=VI_GEOMETRY,improving=(method=LLoyd(1,0.9;tolerance_function = (x,y,v)->v*norm(x-y)^2),silence=false))
draw2D(VG1)
VG2 = VoronoiGeometry(copy(mynodes),cuboid(2,periodic=[]),integrator=VI_GEOMETRY,improving=Simple_LLoyd(1,0.9))
draw2D(VG2)
HighVoronoi.LLoyd — Type
LLoyd(max_iterations::Int; tolerance::Float64=Inf,
      integrator=VI_POLYGON, tolerance_function=nothing,
      mc_accurate=(1000, 5, 20),
      global_tolerance::Bool=true,
      local_tolerance::Bool=false,
      use_voronoi_data::Bool=false,
      local_tol::Float64=Inf,
      global_tol::Float64=Inf)

Create (and trigger) a Lloyd’s algorithm solver to produce a centroidal Voronoi tessellation.

Parameters

  • max_iterations::Int Maximum number of iterations to perform.
  • tolerance::Float64=Inf Convergence threshold for centroid movement.
  • integrator Method used to compute centroids of each Voronoi cell.
  • tolerance_function A user-supplied function to measure the “distance” between an old and new centroid. By default, no custom function is used.
  • mc_accurate::Tuple{Int,Int,Int}=(1000, 5, 20) Parameters for Monte Carlo integration when integrator == VI_MONTECARLO:
  • global_tolerance::Bool=true If true, sum the values of tolerance_function over all cells and compare against min(tolerance, global_tol). If the total is below this threshold, the algorithm halts or skips updating all nodes at once.
  • local_tolerance::Bool=false If true and global_tolerance == false, apply tolerance_function cell-by-cell. Each cell’s displacement is compared against min(tolerance, local_tol), and only cells exceeding this limit are updated.
  • use_voronoi_data::Bool=false If true, tolerance_function is called with cell index i and a VoronoiData object instead of (old_centroid_center, new_centroid_center, cell_volume).
  • local_tol::Float64=Inf Override for per-cell tolerance when local_tolerance == true.
  • global_tol::Float64=Inf Override for the summed tolerance when global_tolerance == true.
source

improving! method

Missing docstring.

Missing docstring for improving!. Check Documenter's build log for details.