Re: [Algorithms] Constrained Delaunay Triangulations

[Dave S. <Dav...@sd...>]

In the words of Troy McClure: "That's fantastic, Baby!"

Really, thanks.  That was a quick reply for something
that specific.  I have some more questions below, if you 
don't mind.

> 
> CDT is tricky to keep robust.  A VERY important thing to remember is that
> your constrained mesh is no longer "Delaunay compliant".  You will end up
> with some concave quads (that I can't draw well in ASCII art), where you can
> not flip the joining edge, because your flipped edge would cross out of both
> triangles (passing through previously constrained edges).  

How could a flipped edge end up outside both triangles?  I thought
the choice was either diagonal of the quad?  


>  This paper (which I wish I had read when I wrote my code) is
> clearly trying to save you from the pain of this. 

When you say "this paper" are you referring to Bern & Eppsteins
"Mesh Generation and Optimal Triangulation" or Schewchuks?  
(I finally got home to read the title. :-P )

> You will also end up with slivers.  There is nothing you can do about this.
> You will need to have a sufficient delta on your calculations to cope with
> this.  This delta will be different depending upon the scale of your data
> and upon the precision you require.

How big a range of delta's are we talking about?  Just some
examples, 10e-5 to 10e-1 for example.

> 
> If you have the time you may wish to use slightly more rigorous metrics.
> Jonathan Shewchuk's papers are very sane references.  He has spent a lot of
> time thinking about it.
> 

I saw it float by yesterday on ACM.  We'll see if I find time. :-)

Thanks again,
-DaveS