Yes, Fortune's algorithm is also a good candidate, maybe better. I would
have to review its details to see how to deal with the data structures.

That said, I've been thinking about the computational complexity thing, and

I am not sure I understand your point but I think the current
implementation of concat for successive additions to a list is O(k) for k
new elements provided no access is done to the list in between. The first
access would require another O(k) operation.

We have Oskar Linde's 3d convex hull implementation already written.  So it
sounds like you're saying it's just a trivial step then to produce the VD?

Kenneth Sloan wrote

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

This does seem to be pretty darn simple.  Is this right?

include<BOSL2/std.scad>
include<BOSL2/hull.scad>

module vornoi(pts)
{
pt3d = [for(pt=pts) [pt.x,pt.y,sqr(pt.x)+sqr(pt.y)]];
faces = hull(pt3d);  // Faces of 3d convex hull
// keep ones whose normal points down
keep = [for(face=faces)
let( n = polygon_normal(select(pt3d,face)))
if (n.z<0) face];
vnf_wireframe([path3d(pts), keep],d=.1);
}

N = 10;
test = array_group(rands(0,10,2*N),2);
vornoi(test);
color("red")move_copies(test) circle(r=.15,$fn=8);

http://forum.openscad.org/file/t2477/vd.png

adrianv wrote

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

Yes.

A) given a set of (x,y) points in the plane, lift them to (x,y,x^2+y^2)
B) find the 3D convex hull
C) remove all triangles that face UP
D) project back to (x,y)

You now have the Delaunay triangulation in 2D.

E) compute the dual graph: triangles map to points (the triangle’s
circumcenter), edges shared by triangles map to edges connecting the
circumcenters.

On Mon, Apr 12, 2021 at 17:54 adrianv avm4@cornell.edu wrote:

--
-Kenneth Sloan

Hardest step by far is E.  I'll let someone else do that.... :)  I'm not sure
how you handle points at infinity.  Maybe you supply a bounding box for the
diagram?  Is there a convention?

Kenneth Sloan wrote

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

Depends on context.  For the purist...they are "points at infinity".  When I draw diagrams, I usually pick a sufficiently large distance and construct a line from the triangle  circumcenter through the middle of the edge which is on the convex hull of the DT, terminating at the "sufficiently large distance".  Eventually, these lines are clipped against the viewing window.

As  long as you are already using 3D at some point, you might consider keeping the points in 3D and projecting the "real" points to z=1 and the points at infinity to z=0.  That gives you a clean data structure - but pushes off the decision about what to do with the points at infinity to whatever turns the data structure into a concrete realization. (for the uninitiated, see "Homogeneous Coordinates".)

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

Fascinating, but I can't get close enough to see what's happening with
it. How do I make it bigger?
On Mon, 2021-04-12 at 16:11 -0700, adrianv wrote:

adrianv wrote

A lazy way would be to restrict the tessellation to cells centered on points
that are on the interior of the Delaunay triangulation.

Delaunay triangulations can be degenerate if there are more than three
points on  a circle, so that may need special handling when generating the
Voronoi tessellation.

It's reasonably straightforward to generate the Voronoi cells from the
triangulation by walking the mesh around each point.  The dumb_voronoi.scad
script above does something like that.  If you care about asymptotic
performance, that kind of cell generation is doable in O(n log n) time and
O(n) space where n is the number of triangles.

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

This is not correct for a “real” VD, but is a useful idea in many practical
applications.  Often, the “sites” (the vertices of the DT) are samples
taken from a finite window.  In these cases, the VD cells at the edges are
“wrong”, because the sites which should have defined them are outside the
sample window.

I usually try to determine a boundary enclosing the “good” region.  My
usual guideline is to exclude a ring around the boundary thick enough to
contain at least 1 (preferably 2) sites all the way around.  I then exclude
VD cells with any vertex outside this boundary.

The precise details on how to do this depend on the application, snd the
distribution of the sites.

Often, you are only concerned with the behavior of the VD in a central
region, far from any “edge effects”

But - there are other applications where the boundaries are important.  For
them, it is essential to have some way of representing “points at infinity”.

I can think of two ways to do that/

A) use homogeneous coordinates, representing 2D points in 3D, with finite
points at z=1 and points at infinity at z=0.

B) treating edges on the convex Hull as a special case and generating fake
Voronoi vertices at a distance “sufficiently large”

In either case, the graph of the VD will have dangling edges which must be
handled carefully.

If your final clipping window is small enough, you can simply ignore edges
on the convex Hull when mapping from the DT to the VD.  These can be
identified as edges which participate in only one finite triangle.

On balance, I prefer to generate VD vertices which are “at a great
distance” to stand in for the ones “at infinity”.  This requires special
case handling of convex  hull edges.  You have a good set of Voronoi edges,
but still need to be aware that some Voronoi cells will not be closed
polygons.  If you just draw diagrams, the diagrams will be correct as long
as none of the points “at a great distance” appear in your clipping window.

If you actually want to analyze the VD (say, by measuring areas or aspect
ratios or number of neighbors), and your sampling area was limited, you
must be aggressive about excluding all Voronoi cells which are near enough
to the boundary to be warped because a defining site fir that cell was
outside your sampling window.  This is always application dependent!

Note that even closed Voronoi cells mat be “wrong”. Simply excluding points
at infinity is not good enough!

On Tue, Apr 13, 2021 at 08:09 NateTG nate-openscadforum@pedantic.org
wrote:

--
-Kenneth Sloan