CGAL users discussion list

[Michael Balzer <>]

Yes, CGAL has definitely one of the fastest implementations for that 
purpose. But in general, the computation of a CVT is quite expensive, 
especially for large points sets.

Michael



Peter Schröder schrieb:
> Michael Balzer wrote:
> > The question that is left is how to generate such a distribution, and 
> > there are many different ways to do that, e.g. dart throwing, 
> > inserting points at the center of the largest empty circle, etc. 
> > Another very excellent (but slow) method, that generates high quality 
> > uniform distributions of points, are so-called centroidal Voronoi 
> > tessellations (CVT). These CVTs can be computerd iteratively by first 
> > computing a Voronoi tessellation of a random point set (using CGAL, 
> > for example), then moving each generator point in the center of the 
> > according Voronoi region, and repeat this procedure until the distance 
> > between generator and centroid is below a chosen threshold.
> Thanks to the speed of CGAL this can actually be done rather rapidly 
> (and makes for a cool interactive application). Pierre Alliez once built 
> such a little sample program. Fun and very impressive.
>
> peter