Hi Aph3x,

I appreciate the new, non-hijacked thread!

Ha, ha, yes, I realize what Stolfi is doing. I should have
mentioned that. The thing is this. Stolfi's code basically
requires that: a) the word size on the machine is 32 bits; and
b) objects are word-aligned. Both of these assumptions are
reasonable on 32-bit Intel hardware, e.g. Pentium class
machines with the compiler set to its normal object packing
rules.

The magical thing that happens (and you may already realize
what's going on) is that when the objects are word-aligned,
then the lower few bits of a pointer are always zero. Stolfi
exploits this. His edge_ref integer value encodes BOTH a
pointer to an edge_struct object, AND an orientation
flag that determines the orientation of the edge. The upper 30
bits are the pointer and the bottom 2 bits are the flag. So,
when you get an edge_ref in return, you have the following:

edge_struct *object = (edge_struct*)(edgeref_value & 0xffffffc);

and,

orientation = edgeref_value & 3;

To really understand what is going on here, with the
orientation, you're going to have to read up on the quad edge
data structure that is the basis for Stolfi's algorithm. Paul
Heckbert has a good web page on it somewhere, and also wrote
code for one of the Graphics Gems books (I think the 4th book)
that talks about quad edge more intuitively than Guibas and
Stolfi.

I know the word-aligned 32-bit pointer + orientation = edge_ref
= unsigned int thing is bizarre and nonportable. But, it works.
If you really want to understand divide-and-conquer Delaunay
then Guibas and Stolfi's paper is kind of the definitive work.

I can say that if you look at Heckbert's implementation of Quad-
Edge (which is also available on the web and I think is
freeware for noncommercial use), you will find something more
normal, e.g., he does none of this weird embedding.

If you don't care that sometimes the triangulation will run
slowly, then you may just want to drop back to the simple
incremental insertion algorithm. Its somewhat more
straightforward to implement, but can be slow in some cases. To
make it reasonably fast you need to randomize the order in
which your points get inserted into the triangulation. There
are a good number of web docs that illustrate the incremental
insertion algorithm.

One more thing I should say about Stolfi's code....it never
actually produces triangles. Hmmm. It only gives you edges.
Hmmm. But, from the edges you can create triangles. How to do
it is this. When you create the edges initialize the left and
right faces to be zero. Then, use Stolfi's code to walk through
all the edges, visiting each edge exactly once. As you visit an
edge, do this for each edge a:

1) If the edge's left face is nonzero, skip to the next edge,    otherwise continue. Pseudocode:edge_ref a = current edgeif (LEFT(a) != 0) continue;2) Set its left face to be == 1. Pseudocode:LEFT(a) = 1;3) Now, walk around the edges connected on the left edge of the edge a. You will find 3 edges, a being the first. Say  your 3 edges are a, b, c. Create a new triangle using the 3 vertices common to a, b, and c. And, set the left face of a, b, and c to be 1 (so that you don't create the same triangle again). Pseudo-code for this is:edge_ref a = the current edge from the outer loop;edge_ref b = LNEXT(a) = the next edge counterclockwise from aedge_ref c = LNEXT(b) = the next edge counterclockwise from bc closes the triangleCreate triangle using vertices of a, b, c.LEFT(b) = 1LEFT(c) = 1 4) Continue to the next edge using Stolfi's code.

Hope this helps.

Thin triangles cause problems with the divide-and-conquer method as well (which I know very well based on recent annoying experiences), but it seems with divide-and-conquer it may be easier to deal with them. I found with incremental insertion, it was quite easy to create so many edge flips that there would be a stack overflow or at least very slow searches for a containing triangle or edge at the next insertion. Eberly, Guibas and Stolfi, and Shewchuk, all discuss better ways to the container search for incremental insertion.

The biggest problems will arise when you have uniformly-spaced input points. If the points are really random, things will work 99.9% of the time.

I'll note that Stolfi's code includes an incremental insertion implementation as well, though if you don't like the weird pointer mangling you won't want to use it.

I played around with Eberly's old Delaunay implementation, but not his "2" version.