Skip to content

Geodesic Centroidal Voronoi Tessellations

A Voronoi tessellation partitions a domain M based on a set of sites s_i \in M. To each site s_i, we associate a region (or “Voronoi cell”) consisting of the points closer to s_i than to any other site. Such a tessellation is called centroidal if each site is at the center of its corresponding cell. This routine computes centroidal Voronoi tessellations on surface meshes.

Output is not unique!

By default, this procedure picks some random points and optimizes them to compute a centroidal Voronoi tessellation. Since the initialization is random, the results will generally be different each time the procedure is run.

#include "geometrycentral/surface/geodesic_centroidal_voronoi_tessellation.h"

karcher means

VoronoiResult computeGeodesicCentroidalVoronoiTessellation(ManifoldSurfaceMesh& mesh, IntrinsicGeometryInterface& geom, VoronoiOptions options = defaultVoronoiOptions)

Compute a geodesic centroidal Voronoi tessellation on the input mesh. Options are passed as a VoronoiOptions object, and the output is returned as a VoronoiResult object.

Helper Types

Options

Options are passed in to computeGeodesicCentroidalVoronoiTessellation via a VoronoiOptions object.

Field Default value Meaning
size_t nSites; 10 the number of sites to place
std::vector<SurfacePoint> initialSites; {} desired locations for sites. If blank, initial locations are chosen randomly
size_t iterations; 50 number of iterations to run for
bool useDelaunay; true solve on an intrinsic Delaunay triangulation of the input
double tCoef; 1 diffusion time for the vector heat method
size_t nSubIterations; 1 number of iterations to use when computing surface centers during optimization

Result

The result is returned as a VoronoiResult, which has 3 fields:

Field Meaning
std::vector<SurfacePoint> siteLocations; the sites at the centers of the Voronoi cells
std::vector<VertexData<double>> siteDistributions; indicator functions which each Voronoi cell
bool hasDistributions; is siteDistributions populated?

Citation

This algorithms is described in The Vector Heat Method, the appropriate citation is:

@article{sharp2019vector,
  title={The Vector Heat Method},
  author={Sharp, Nicholas and Soliman, Yousuf and Crane, Keenan},
  journal={ACM Transactions on Graphics (TOG)},
  volume={38},
  number={3},
  pages={24},
  year={2019},
  publisher={ACM}
}