Kenneth Sloan wrote

It seems like this is creeping a little from generating Delaunay
triangulations and Voronoi tilings to dealing with applications.  If I
understand the description correctly, it seems like eliminating Delaunay
triangles which aren't contained by the sample window first and then only
using closed Voronoi cells should work most of the time.

This part of an earlier comment makes me think I'm missing something:

Kenneth Sloan wrote

It's not free, but if there's a list of N triangles with consistent winding
order, then we can make a sorted list of the 3N half-edges as a lookup table
in O(N log N) time.  Walking the perimeters of the Voronoi cells hits each
triangle 3 times, and each of the table look ups takes O(log N) time, so the
walking is O(N log N) too.

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

By definition, all DT are contained in the "sampling window" (by which, I mean the window used to limit the original sites).

Given just the DT, it might be safe to:

a) find (and remove) all triangles which involve a site on the convex hull
b) eliminate all sites involved in those triangles
c) remove all triangles involving those sites
d) (perhaps) repeat b) and c) as needed for extra safety
e) generate Voronoi cells for the remaining  sites

I would still be on the lookout for "long, skinny" Voronoi cells.

For your proposed search - how would you sort the half edges?  It's a whole lot easier if your DT  code generates a data structure where:

a) points are linked (both ways) to edges
b) edges are linked (both ways) to triangles

In that case, every Voronoi cell corresponds to a point (site).  The point links directly to all of its incident edges.  Each edge links to its (1 or 2) triangles.

If you augment the data structure to include the coordinates of the circumcenter of the triangle, then you are home free.

So:

Triangle = 3 edges + 1 (circumcenter)
Edge = 2 points +  1 or 2 triangles  [if you prefer, a half-edge = 1 point + 0 or 1 triangle(s)]
Point = coordinates + list of edges

Now, to generate a Voronoi cell associated with a point:

for each Edge in the list of Edges associated with this Point
add a line segment from Triangle 1's circumcenter to Triangle 2's circumcenter
# special case when only 1 Triangle

and, to generate a full Voronoi Diagram (just the edges)

for each Edge in a master list of all Edges
add a line segment from Triangle 1's circumcenter to Triangle 2's circumcenter
# special case when only 1 Triangle

No search at all (you did all the work when creating the data structure above).

Of course, if you want to ANALYZE the Voronoi Cells, you might want:

Cell = site + list of Voronoi edges
Voronoi Edge = 2 Voronoi vertices
Voronoi Vertex = coordinates (optionally + list of all Voronoi Edges sharing this Voronoi Vertex).

If you want full generality, you can do all of this with one data structure that represents both the DT and the VD and simply requires different interpretation.

For example:

HalfEdge = 1 site + 1 DT + link to next HalfEdge surrounding this point + link to matching HalfEdge
DT = 3 HalfEdges + circumcenter

Generalizing to non-triangular "Delaunay Triangles" is left as an exerise (but not really recommended).

Note that you can also bundle HalfEdges into lists (instead of pairs) if you want to support non-manifold surfaces.

All of the above is from ancient memory - I apologize for any errors.  It's been more than a decade since I last actually wrote code for this (and the code has been working since then with no issues).
Alas, the last collection of code was in Java, which  may not help anyone writing in OpenSCAD.

Here's a recent example:

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

I have a data structure built from a vertices-and-faces description (VNF)
that ensures that all local adjacencies can be found in constant time.
It is constructed in O(n log n) (involves sorting and local searches) and
the adjacency access functions are inspired by the quad-edge structure
without the dual access functions. It requires a VNF representing a
topological 2-manifold without border. So to compute the VD from the DT I
needed to add a "border face", a face with a consistent widing representing
the outside world of the DT. The resulting VNF of the DT is then a
topological 2-manifold without border and easily dualizable (although a
strict dual would have a vertex associated to the border face). To cope
with the infinity edges of the VD far away vertices are added to the list
of circumcenters. In order to have closed VD cells, the far away vertices
are linked with additional edges and thus the VD itself may be represented
as a topological 2-manifold without border. The following picture shows the
results with the extra vertices of the VD closer enough to the point mass
for sake of illustration.

[image: Delaunay&Voronoi.PNG]

That data structure also makes it possible to implement the so-called
subdivision methods (like Catmull-Clark, Doo-Sabin and Loop's algorithm)
for VNFs without border with a worst case order of O(n log n). Its space
requirements are O(n).

Kenneth Sloan kennethrsloan@gmail.com wrote:

Did you use Guibas&Stolfi quad-edge for that?

Not most recently.  I did implement G&S a Long, Long time ago - but later
decided it was of more theoretical interest than practical.  My current
implementation is simpler.  Its beginnings were an attempt to rewrite Joe
O’Rourke’s C code in Java - mostly for pedagogic purposes.

Like so much code that I have written for classroom demos, I ended up using
it in real projects.

On Tue, Apr 13, 2021 at 14:48 Ronaldo Persiano rcmpersiano@gmail.com
wrote:

--
-Kenneth Sloan

Looks good.

To test numerical stability, try it on regular grids with many co-linear points.  A  hexagonal grid is good - a square grid is more challenging.  Start with 4 points at the vertices of a square and ramp  up from there.  Also challenging  is many points on (say) the x-axis, with 1 point  some distance away on the y axis.

Also, test with a wide  range of distances - change your uniform distribution over x and y to a Gaussian distribution.

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