Lifting the 2D points to a 3D paraboloid and computing the 3D Convex Hull has been the method of choice since the 1980's.  I have implemented this several times.

Computing the dual is not difficult in an imperative language.  I have no idea what the best method would be in OpenSCAD.

Briefly, every Delaunay Triangle is mapped to a point - that point is the triangle's circumcenter.  Edges of the Delaunay Triangles are mapped to edge in the Voronoi Diagram - a DT edge which is shared by two DTs is mapped to a VD edge connecting the DT circumcenters.

This is easiest if you use data structures capable of representing Edges, Triangles, and Points, with information on which edges belong to which triangles (each edge is shared by 1 or 2 triangles).

If all you have is a collection of triangles, computing the Voronoi Point corresponding to each triangle is easy - but finding the connections between the points (that is, the triangles which share edges with each other) can involve considerable search overhead.

In my opinion, intersecting cones is a very "OpenSCAD-like" method - but, as noted, it's unlikely to be fast.

--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.

Troberg wrote

A big issue with using the geometry engine is that you don't get access to
the result of the computation in a way that lets you do more with it.spe

I did try to make simple stupid Voronoi and  Delaunay using the n^4 approach
of checking every possible circumcircle but even that is much longer than
your example, and involves subtle stuff like dealing with floating point
math and more than 3 points on a circle.

dumb_voronoi2d.scad
http://forum.openscad.org/file/t2140/dumb_voronoi2d.scad

dumb_delaunay2d.scad
http://forum.openscad.org/file/t2140/dumb_delaunay2d.scad

--
Sent from: http://forum.openscad.org/

Note that the N^4 method also has a potential bug - 4 co-circular points will generate 4 triangles which overlap.  Perhaps that's what  NateTG is referring to.

Floating point math is always an issue with these  computations.  Use standard precautions.

I  have not-so-fond memories of debugging the "flip-triangles" method, about a year before the "lift to a paraboloid" method was published.  The "sweep-line" method used to be popular, but (in my opinion) was poorly described when first published.  In my opinion, it is valuable for the ability to modify it for variants of the Voronoi Diagram - but is not the method of choice for classic Delaunay Triangulation.

My choice (for the last several decades) has been the "lift to a paraboloid" method.  Once implemented (not trivial, but not difficult) I can't recall any serious issues with precision.  I do  take some care with conditioning input data (mostly merging points that are "too close").

And again - I have no clue what  difficulties might be involved in implementing this in OpenSCAD.
My inclination would be to use "intersecting cones", if forced to implement it in OpenSCAD.
At least, I'd implement that first and wait to see what the performance penalty was.

--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.

There is a vornoi calculator in the dotSCAD library:

https://github.com/JustinSDK/dotSCAD

I have no idea what algorithm it uses, or its performance, but might be
worth a look.

Kenneth Sloan wrote

--
Sent from: http://forum.openscad.org/

NateTG wrote

Yep, but I made it just to generate a cool shape for a lamp shade for laser
cutting, so I just wanted a quick and dirty solution for that.

--
Sent from: http://forum.openscad.org/

I sort of lost track as to what the original requirement was in this
thread, but since it has been generating so many responses - I had a need
for a Voronoi pattern in a design last week, and I ended up cheating and
using https://voronoi-editor.web.app/ , tweaking it to my liking, exporting
the svg and then import()/linear_extrude()'ing that svg. Was much easier to
use than the various native solutions I found online. The main disadvantage
was that the regular preview was completely screwed up so I had to F6 every
time I wanted a proper idea of what the result would look like. Just
mentioning that maybe an external solution is the more pragmatic approach.

cheers

On Mon, Apr 12, 2021 at 9:21 AM Troberg troberg.anders@gmail.com wrote:

adrianv wrote

// Half-plane Intersection: it's slow but simple.
voronoi/vrn2_cells_from(points)
voronoi/vrn2_from(points, spacing = 1, ...)

// Half-plane Intersection && Nearest Neighbor (idea from
https://thebookofshaders.com/12/)
voronoi/vrn2_cells_space(size, grid_w, seed = undef)
voronoi/vrn2_space(size, grid_w, seed = undef, spacing = 1, ...)

https://openhome.cc

Sent from: http://forum.openscad.org/

I may be wrong but I guess the best candidate for an implementation of
Delaunay in OpenSCAD would be the divide and conquer: divide the pointset
in two halves, recursively build the Delaunay triangulation of the right
and left sets and merge them. It is a O(n.log n) method whose hardest (and
runtime expensive) part is to devise and build an appropriate data
structure that keeps the local tasks constant time. In an implementation of
the Catmull-Clark and similar subdivision methods we did, a suitable data
structure played the most demanding effort. With the appropriate data
structure, to find the dual to get the Voronoi is easy.

Ronaldo wrote

Fortune's algorithm (https://en.wikipedia.org/wiki/Fortune%27s_algorithm)
looks pretty doable.  To make that work in n log n time requires data
structures for the event queue and beach line that have log n insertion
time.

That said, I've been thinking about the computational complexity thing, and
there's a tendency to end up with a recursion pattern like:

concat( partial_list, function(index+1) )

If concatenation takes order n time for a length n list, then anything that
uses a pattern like that will have time complexity n^2 in the size of the
output anyway,  so the value of getting from n^2 to n log n for Delaunay
triangulation may be marginal unless that's also changed.

--
Sent from: http://forum.openscad.org/

On 4/12/2021 1:07 AM, Roel Vanhout wrote:

Sounds like you need to set convexity on your linear_extrude.  Set it to
10 or so.  People have done performance experiments, and there's almost
no downside to setting a larger convexity.