Hi!
Does anyone know the Basis behind the Voronoi 2D module in Grasshopper i.e. the Algorithm it uses? (Lloyd’s, Fortune’s, Boyer-Watson,…)
Cheers,
Balaji
It builds the delaunay triangulation, then creates the dual.
Oh that’s 2D voronoi, 3D voronoi is brute force, slicing convex volumes with mid-planes. If I ever write a 3D delaunay volumetric mesher this can be sped up using a dual approach as well.
Thanks for the answer David!
Do you know the algorithm involved behind the computation of delaunay triangles.
I could see that there are quite a bunch for them too 
I implemented an algorithm described by Paul Bourke, with the added optimization that the vertices are sorted left to right first, so I can move triangles from the algorithm front into a ‘fixed’ list, reducing the number of circumcircle/vertex tests.
I think there was also some extra stuff added to deal with the case of more than three vertices being coincident with a single circle, but I can’t remember now.
1 Like