## Re: [Algorithms] Constrained Delaunay Triangulations

 Re: [Algorithms] Constrained Delaunay Triangulations From: Dave Smith - 2000-11-02 14:48:16 ```> (2) if e forms a smaller minimum angle with the > outside edges than the other diagonal does. > I don't see how this is supposed to work at all given John H.'s example. Either I have misinterpreted the statement above or my implementation is goofed (which it might very well be). Looking at any concave quad formed by two triangles, why would you ever flip the edge? In my example, I have two perpindicular line segments, not touching, and depending on how long you make them, you can get (2) to be true or false.(Basically your making the minimum angles smaller for one diagonal than the other) So now, I'm stuck in a dilemma. Abandon this so called "easy" algorithm, or find another. I've read Chew's algorithm(the O(nlogn) one). The first thing that jumps out at me is that he sorts according to a dimension(x or y) and if you can't find a unique line for every coordinate(which you most likely never will), you must rotate the input set. Well that doesn't guarantee you will get a unique line plus finding how much to rotate isn't exactly straight forward. In the meantime I'll start browsing Shewchucks stuff, but if anyone can enlighten me on any of the above, I would appreciate it. Thanks, -DaveS ```

 [Algorithms] Constrained Delaunay Triangulations From: Dave Smith - 2000-10-30 20:45:39 ```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 Peter-Pike Sloan for the Computational Geometry links. They fixed some of my problems. ```
 Re: [Algorithms] Constrained Delaunay Triangulations From: Dave Smith - 2000-11-02 14:48:16 ```> (2) if e forms a smaller minimum angle with the > outside edges than the other diagonal does. > I don't see how this is supposed to work at all given John H.'s example. Either I have misinterpreted the statement above or my implementation is goofed (which it might very well be). Looking at any concave quad formed by two triangles, why would you ever flip the edge? In my example, I have two perpindicular line segments, not touching, and depending on how long you make them, you can get (2) to be true or false.(Basically your making the minimum angles smaller for one diagonal than the other) So now, I'm stuck in a dilemma. Abandon this so called "easy" algorithm, or find another. I've read Chew's algorithm(the O(nlogn) one). The first thing that jumps out at me is that he sorts according to a dimension(x or y) and if you can't find a unique line for every coordinate(which you most likely never will), you must rotate the input set. Well that doesn't guarantee you will get a unique line plus finding how much to rotate isn't exactly straight forward. In the meantime I'll start browsing Shewchucks stuff, but if anyone can enlighten me on any of the above, I would appreciate it. Thanks, -DaveS ```
 Re: [Algorithms] Constrained Delaunay Triangulations From: Dave Smith - 2000-11-02 19:28:17 ```> In the meantime I'll start browsing Shewchucks > stuff, but if anyone can enlighten me on any of the > above, I would appreciate it. > Shewchuk's thesis chapter 2: "Not all triangulation edges are flippable,.. ,because the containing quadrilateral of an edge might not be convex" Makes sense. :-) -DaveS ```