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

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