I'm planning to implement the Flip Algorithm
that is described in Bern & Eppsteins '85
paper, pg 12.(Sorry don't have the title
at the moment).
My question is the following:
For an edge e, not an input edge & not on the convex
hull, denote Qe the quadrilateral formed by the
two triangles on each side of e.
Qe is 'reversed' if e is not in the CDT of the
4 outside edges of the quadrilateral. Or, in other
words, Qe is 'reversed'
(1) if the angles at its uncut corners sum to more
than 180, or
(2) if e forms a smaller minimum angle with the
outside edges than the other diagonal does.
So for (1) to be true I assume for this picture:
/E\F/
/ \ B/
/ \ / e is the diagonal in this picture.
/ \ /
/_A_____D_\C/
A+B > 180 ....easy enough, I hope :/
And for (2) to be true, with the above picture:
MIN{D,C,E,F} < MIN{G,H,I,J} where G,H,I,and J
are the angles that would cut the outside edges if
another diagonal was drawn that intersected angles
A and B.
Does that sound ok? I'll probably be implementing
this shortly but I thought maybe somebody who has
gone through the pain, may catch something I may be
doing wrong. Also, any other references to fairly
easy to implement CDT algorithms are welcome.
Thanks,
DaveS
ps. Thanks to PeterPike Sloan for the Computational
Geometry links. They fixed some of my problems.
