RE: [Algorithms] Constrained Delaunay Triangulations

[John H. <jha...@di...>]

David,

> >                      B
> >                     /||\
> >                    / || \
> >                   /  ||  \
> >                  /  , C.  \
> >                 / ,     .  \
> >                /,         . \
> >               A             D
> >
> > You have just made triangle ABC by inserting vertex A in 
> some adjacent
> > triangle.  Edges BD and CD have previously beeen 
> constrained.  Yet vertex D
> > lies within the circumcircle of ABC.  This situation only 
> happens because of
> > the constraints.  Clearly we can't delete BC and make an 
> edge AD.  I was
> > suggesting a simple and fast supplement to the standard 
> circumcircle check
> > (which I posted to an earlier post).  It works for me.  You 
> are obviously
> > getting slivers at this point!
> 
> True!. And the diagonal edges intersection is one way. Now 
> there is another one
>  that I am using which so far seems to be very robust that I 
> would like to share
> with you:
> The in_circle test is *oriented* so in other words, the result of the
> determinant will be
> negative or positive depending on the orientation of the 3 
> vertices (CW, CCW).
> Let's assume that the triangles are oriented CCW.
> In your drawing, if I want to know whether I should build AD, 
> I take the
> circumcircle based
> on ACD (not ADC) and test B against it. The test will return 
> true which means
> that B is inside
> the circle oriented ACD and therefore BC must remain. You can 
> try it with any of
> the circumcircle
> possible, it works. BAC vs D, ACD vs B, CDB vs A and DBA vs C.

However this approach (which was the one that I used first) gives no
information about how close B and C are to AD, in other words an automatic
metric about how sliver-like the constructed triangles will be is given by
the method I currently use.  This is a win (in terms of processor cycles in
the way that I have been approaching the problem), because I don't need to
do golden ratio type checks to prevent more sliver triangles being created.


> in the triangulation or do you select your dataset so that 
> you will never have
> more than 2 triangles to flip to get the constraint inserted?

Hmmm, quick, fairly unscientific check...

3.2 triangles are being flipped per constraint.  High of 25.  Bound to be
different with a different dataset.
Plus, I seem to be doing closer to 1300 edges per frame than 3000 most of
the time.  I may peak at around 3000, but possibly if I was running at that
the whole time I might notice a hit on the slower machines - I haven't
checked.

I suspect a lot of the speed comes from early outs in the code and good
cache performance due to a compact localised mesh representation. 

> 
> Do you have any shots???

A mesh is a mesh is a mesh (just imagine lots of blue triangles with red
constrained edges)...

> Which method are you using for the point location? Guibas & 
> Stolfi's algorithm?
> Personally, I use a modified version of this algorithm since 
> it fails with
> constrained
> triangulations.

No. I do use a modified mesh walk using the sign of a rough triangle area
and a couple of tie break metrics though.  What modifications are you using
(asked in the hope that you have a neat trick which will fix my occasional
bad case :-))?  Most of my speed comes from some tricks to pick a good
starting triangle to walk from.

> Have you tried hierarchical Delaunay 
> triangulation? It appears
> to be
> be most efficient point location method by now..

The memory it uses up is my biggest issue with it.  Sure helps with
deletions though.

cheers,


John