Any way of generating centroidal voronoi diagrams?

[iMplode-nZ]

See https://www.redblobgames.com/x/1842-delaunay-voronoi-sphere/. Using the centroids of the delaunay triangulation makes the diagram look more regular.

[andreesteve]

That sounds like the Lloyd relaxation iterations you can configure in the builder: https://docs.rs/voronoice/0.0.1/voronoice/struct.VoronoiBuilder.html#method.set_lloyd_relaxation_iterations

In it iteration it generates the voronoi partition and then use the centroid of each cell as site for the next iteration.

You can see it in action in the latter portion of the animation at https://github.com/andreesteve/voronoice-inspector

Is that what you are looking for?

[iMplode-nZ]

The centroidal voronoi diagrams are after performing lloyd relaxation, you generate the diagram by using the centroids of the delaunay triangles instead of the circumcenters.

[andreesteve]

Got it. Yes, that is possible. You can actually get that today without changing the library itself, if you are OK with disabling clipping. The Voronoi cell edges are indexed based on their relationship with the Delaney triangles. So instead of using the iterator that maps the cell edges to points, you can iterate based on the centroids.

You could do something like this:

 let v: Voronoi = VoronoiBuilder::default()
     .generate_square_sites(10)
     .set_clip_behavior(ClipBehavior::None)
     .build()
     .unwrap();

v.cell(0).iter_triangles().map(|t| get-centroid-of-triangle(t))

I likely have bunch of compiler violations on the code above as I didn't have the chance to try this out yet.

If you go back enough in the commit history, my original code used centroids instead of circumcenters; but that does not generate a Voronoi partition of the plan (things like distances and other properties of the partition would not be accurate). Frankly I do not recall it being too different from using circumcenters from a distribution perspective. The main factor for the initial partition looks like is what generator you use for the initial site positions.

If you are looking for a more regular distribution, then lloyd relaxations will probably yield better results; even 2 iterations makes a significant difference.

[iMplode-nZ]

I would also expect lloyd relaxations, but this is also necessary to make the thing look decently good. Eg: vs (the bottom one is the centroidal diagram)

It might make sense to just add a flag on the VoronoiBuilder for this.

[iMplode-nZ]

Turns out lloyd relaxation makes centroidal diagrams irrelevant.