Thanks Kenneth,

What algorithm did you use to do the triangulation?  I haven't looked at
O'Rourke why do you suggest it? the Bowyer-Watson doesn't look too bad and
its O(N Log N).

I agree its quite daunting given the limitations of openscad. That is why I
think it would be better
as a built in function.  What would be the process to do that.  I assume
some forum (this one?) or is there a developers forum. I posted to where I
thought it should go and was directed here.  If you have the code in C/Java
i would think it shouldn't be that difficult to implement inside Openscad.
More likely the time consuming part would be debating what are the right
parameters interface.

For instance I think it would be best if the function returned an array of
polygons but I don't think there is any openscad function like that. So if
its drawing the polygons then you need to build in some of the things that
will make it useful visually such as offset(-1) all the polygons to get
edges, and they do you want to do some rounding etc.

Someone asked about a division of work,  if it was C then it would be easy
to divide the work. The other way is to just have the code on GitHub and two
or more people can modify it as long as they talk frequently.
I have functions for point in circumcircle.
I need one to find a triangle that bounds a given set of point.
function to divide a triangle into three triangles given a point in the
triangle (ok this is pretty trival)

I'm having trouble with the overall structure and recursion.  so One person
to write a skeleton of the code and others to fill in specific functions.

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

Implementing incrementally updating data structures in OpenSCAD is a chore.
Try implementing a 2-3 tree if you want to see what it's like.

You could just do the 'dumb' O(N^5) Delaunay algorithm.... something like:

function triangulatepoints (points) =
[
for (i=[0:len(points)-4]) for(j=[i:len(points)-3])
for(k=[j:len(points)-2]) for(l=[l:len(points)-1])
if(circlecheck([i,j,k,l],points)) [i,j,k,l]
]
;

Circlecheck returns false if any of there are any points inside the
'circumsphere' of points i,j,k,l, and true otherwise.

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

Here's the start of a Delaunay triangulator that operates in userland.

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

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

I'm not sure these are particularly legible, but that's what you get for
using OpenSCAD.

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

This needs some work to dedup and deal with degeneracies.
delaunay3d.scad http://forum.openscad.org/file/t2140/delaunay3d.scad

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

I haven't digested it yet, but I just came across this:
https://doc.cgal.org/4.8/Manual/packages.html#PartVoronoiDiagrams

Admin - email* me if you need anything, or if I've done something stupid...

• click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

The TPP is no simple “trade agreement.”  Fight it! http://www.ourfairdeal.org/  time is running out!

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

delaunay2d.scad works well in many cases but produces an obviously wrong
result (one missing edge and one missing face) e.g. for theses points:

points = [[7.38276, -12.8839], [2.89678, -16.8555], [12.3433, -13.6067],
[7.62988, -18.7426], [0.799678, -21.9285], [13.0129, -18.8988], [6.12022,
-23.6863], [12.0965, -23.8574]];

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

I made another algorithm for a voronoi generator. It works, but don't be in a
hurry, because it's slow, very slow (tips for speeding it up appreciated).

module voronoi($maxx=1000,$my=1000,$numpoints=10,fn,gaps=1,$quick=true){
$pointsx=rands(0,$maxx,$numpoints);
$pointsy=rands(0,$maxy,$numpoints);

module cone(ix,fn){
	projection()
	difference(){
		translate([$pointsx[ix],$pointsy[ix],0])
		cylinder(d1=$maxx*2,d2=0.01,h=1000,$fn=fn);
	
		union(){
			for(n=[0:$numpoints-1]){
				if(n!=ix){
					if((abs($pointsx[ix]-$pointsx[n])<$maxx/($numpoints/40))||!$quick){
						if((abs($pointsy[ix]-$pointsy[n])<$maxy/($numpoints/40))||!$quick){
							translate([$pointsx[n],$pointsy[n],0])
							cylinder(d1=$maxx*2,d2=0.01,h=1000,$fn=fn);
						}
					}
				}
			}
		}
	}
}

intersection(){
	square($maxx,$maxy);
	
	for(n=[0:$numpoints-1]){
		offset(-gaps/2)
		cone(n,fn);
	}
}

}

//Try it with a low numpoints and fn (it'll be a little odd with low fn, but
close enough for testing) first.
//quick=true means that it won't look for intersections with far-away
points. Usually, it works, but occasionally, it might cause errors.
//Gaps are the width of the gaps between the polygons.
//maxx & maxy are the dimensions of the generated area.

//Commented out so that it won't render on load, it's slow...
//voronoi($maxx=2000,$maxy=2000,$numpoints=100,fn=5,gaps=10,$quick=false);

It is slow, though, even with fairly modest settings, we are talking
minutes.

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