I have written many Delaunay Triangulation/Voronoi Diagram programs, in many programming languages.

In my opinion, OpenSCAD is probably NOT the appropriate language for this.

Theoretically, of course, it is possible. But, beware of numerical instability.

The best place to start is probably the O(N^4) algorithm given by O'Rourke. It gives the

wrong answer in pathological cases - but this can be fixed.

I recommend *against* the "edge-flipping" method mentioned by the OP. I spent months ferreting out

the numerical issues - but that was in the early '80s BEFORE the theoretical result relating the Delaunay Triangulation in 3D with

the Convex Hull in 3D. That's the method I use routinely, now.

But...that code is fairly large, and it's not written in OpenSCAD. The current version is written in Java. If this

is of interest to you, contact me off-list. Trust me - it will *not* help you implement this in OpenSCAD!

My recommendation is to work out a workflow where you can generate the points you want (somehow) - compute the Voronoi Diagram (using something *other than* OpenSCAD) - and then importing something suitable for further OpenSCAD processing.

That's if you want to do it on the 2D plane. If you want to try to produce a similar result on a curved 2D surface embedded in 3D, then all bets are off. I'm not particularly up on this, but I would not be surprised if there were significant dificulties in even DEFINING the Voronoi Diagram on an arbitrary curved surface. And, lifting to 3D (to take advantage of the duality with the convex hull) becomes problematic. This would require more than simple coding - I suspect there is serious theoretical work

to do first.

When GRUs first appeared, there was a rash of "geometric" algorithms (including DT/VD) introduced to take advantage of them.

The primary difficulty with these is they don't *really* compute the Voronoi Diagram - but rather a close approximation. In

some applications, that may be adequate - but be careful about definitions when reading papers.

Finally - back to my suggestion to start with the O(N^4) algorithm. Consider *how many* points you need to process. If it's

small enough, the theoretically slow algorithm may be adequate. The advantage is that the algorithm is simple to implement, numerically stable, and easy to understand. I haven't tried it, but it *might* be suitable for OpenSCAD implementation.

No matter what language you are using, I strongly recommend that you start with simple, but perhaps slow, algorithms, first.

If nothing else, they provide a check on the answers you get from more complex algorithms (on small examples, of course).

If you can get O'Rourke's O(N^4) method working in OpenSCAD, you may well decide that you have better things to do than to try

to implement edge-flipping, or even the 3D Convex Hull methods.

--

Kenneth Sloan

[hidden email]Vision is the art of seeing what is invisible to others.

For this type of model generation you may want to use Solidpython which will give you access to normal variables, data structures etc. and generate a model that can be interpreted and viewed by OpenSCAD without creating the exponentially higher computation costs of an OpenSCAD-only implementation.

New here but not new to programming. Been enjoy openscad for a while now and

made a few things But I'm stumped so far trying to make a voronoi pattern.

Been looking into it for a few weeks and I think i have found a the

algorithms but they are fairly complex. Would it be possible to write this

in openscad script or would it need to be a new feature/primitive in

Openscad?

What i was thinking was the function or primitive would be for 2d at least

to start applying it to

an arbitrary surface... well I'm not that advanced yet.

voronoi( B= bounding polygon, P = set of points, r = Rounding, t =

thickness)

First step is to convert the set of points to a set of non overlapping

triangles via

https://en.wikipedia.org/wiki/Delaunay_triangulation

Now the math there is pretty daunting but fortunately someone wrote a paper

on someone simple implementation. the following link has about 20 lines of

pseudo code.

https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm

For Each Point in P find all the triangles from step one that have this

point as one of the vertices.

Then you find the circumcenter of each triangle. (This is fairly easy and I

have openscad script for this) for this point and the poloygon of these

points is the voronoi area.

from there is easy, you can just offset (-r) and minoski with the rounding

parameter.

The way variable are handle I'm not sure if I can do all the math (I have a

ton of C experience), I don't think I've fully adjusted to how openscad

doesn't have true variables yet.

--

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

_______________________________________________

OpenSCAD mailing list

[hidden email]

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

_______________________________________________

OpenSCAD mailing list

[hidden email]http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

_______________________________________________

OpenSCAD mailing list

[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org