neighbor of neighbor can violate Delaunay, not fixable by flip, since flip only involves immediate neighbor

[GoogleCodeExporter]

C# version. shape cut out of a terrain mesh (lots of interior points, on an 
approximately square-gridded mesh, distorted by a geographical projection 
remapping).
Seeing some visual glitches, examining the triangulation, there were some 
visually obvious violations of Delaunay. Added test logic to check "neighbors 
of neighbors" for points that violate Delaunay. Sure enough, such points do 
happen -- I see nothing in poly2tri that guarantees true Delaunay validity -- 
only immediate neighbor triangles are checked. Consider triangle ABC with 
neighbor triangles ABD, BCE, CAF. Consider another point G, which is part of a 
neighbor's neighbor, e.g. BDG. At end of Triangulation I added check whether G 
is within ABC's circumcircle, for all triangles and all neighbor-of-neighbor 
G's (excluding self). Got positive responses (which is bad). I have not reduced 
this down to a simple test case yet, at this time I am simply reporting that 
poly2tri lacks proper safety checks to guarantee true Delaunay validity. ~ 
ToolmakerSteve.

Original issue reported on code.google.com by Toolmake...@gmail.com on 16 Mar 2012 at 4:45

[GoogleCodeExporter]

If you cut out a shape that gives you a polygon. The edges makes it a 
constrained DT and the constraints makes the triangulation not a "true" 
delaunay triangulation. 

There is something called a Conforming DT that is a Constrained DT where you 
split the edges such that you get a "true" delaunay triangulation. 

see: http://www.cs.cmu.edu/~quake/triangle.defs.html

This lib has no implementation to make a Constrained DT into a Conforming DT :(

Original comment by thahlen@gmail.com on 16 Mar 2012 at 9:13

[GoogleCodeExporter]

Good point. Hence my proposed test would need to be more complex, to avoid 
complaining about situations which can't be fixed, due to a constrained edge.
However, there is an actual (rare) problem, which I have tracked down after two 
days of tracing through the code).  See attached "before" image for the poor 
triangulation. After the fix, the result is a perfect grid of (triangulated) 
squares everywhere.
Fix is attached -- I've extracted the changed methods of DTSweep.cs.
What the fix accomplishes: better decision-making about when to Fill hole.

Original comment by Toolmake...@gmail.com on 20 Mar 2012 at 12:56

Attachments:

• DTSweep.cs
• [Poly2tri slashes in cut shape.jpg](https://storage.googleapis.com/google-code-attachments/poly2tri/issue-48/comment-2/Poly2tri slashes in cut shape.jpg)

[GoogleCodeExporter]

Also note that this suggested change reduces the amount of triangle flipping 
required (IMHO), in some situations. Reason: fills holes earlier, for cases 
that the original algorithm needed to correct later (by flipping).

Original comment by Toolmake...@gmail.com on 20 Mar 2012 at 1:01

[GoogleCodeExporter]

Clarification: what was passed to Poly2Tri was a polygon (the edge of the blue 
shape seen) plus grid points in the interior of the polygon (safely away from 
the edge). Did not ask Poly2Tri to cope with any additional constraints -- only 
constraints are the edge of the polygon.

Original comment by Toolmake...@gmail.com on 20 Mar 2012 at 1:26

[GoogleCodeExporter]

That is a great catch!

The paper from which I implemented the sweepline algorithm just said to fill 
basins while building the front without any more explanation or examples. I 
guess my implementation wasn't 100% :)

Original comment by thahlen@gmail.com on 20 Mar 2012 at 2:51

• Changed state: Accepted

[GoogleCodeExporter]

Updated the C++ version. Thanks!

Original comment by mason.gr...@gmail.com on 7 Apr 2012 at 2:44

[GoogleCodeExporter]

I was finally going to get around to implement this in the Java version. But it 
seems it will create some stability issues and some triangulations will fail.

Still haven't managed to create a polygon with steiner points that has those 
artifacts. If someone has a point set with same issues as in the above image 
please attach it so I can try to understand the problem.

Original comment by thahlen@gmail.com on 9 Oct 2012 at 5:16

[GoogleCodeExporter]

Adding additional data to this issue with an unsolved case:

Original comment by thahlen@gmail.com on 7 Feb 2014 at 3:46

Attachments:

• poly2tri.png
• contour.txt
• points.txt
• hole.txt

[GoogleCodeExporter]

I don't know whether it is the same problem (no Steiner points),
but the following thet data set (16 points enclosing a square)
is problematic for the C++ version:

4 4
5 4
6 4
7 4
8 4
8 5
8 6
8 7
8 8
7 8
6 8
5 8
4 8
4 7
4 6
4 5

the triangulation produced is not a cdt.

A problem is that when 'Sweep::Legalize' returns not all
'delaunay_edge' flags are cleared, successive Legalizations
will fail to test edges that are incorrectly supposed to
be already tested.

Original comment by mvalenti...@gmail.com on 8 Apr 2014 at 4:47

[GoogleCodeExporter]

Do you have a fix? I can't find the problem looking at the code.

Original comment by thahlen@gmail.com on 8 Apr 2014 at 5:14

[GoogleCodeExporter]

Yes! I see it now since I rotate the triangle pair during the legalize the 
reset of the Delaunay edge is using the wrong index!

For now just try this.

Instead of:
  t.dEdge[i] = false;
  ot.dEdge[oi] = false;
Replace with:
  t.dEdge[0] = false;
  t.dEdge[1] = false;
  t.dEdge[2] = false;
  ot.dEdge[0] = false;
  ot.dEdge[1] = false;
  ot.dEdge[2] = false;

I need to think about this a bit more if it can have some other impact!
But is solves your issue!

Original comment by thahlen@gmail.com on 8 Apr 2014 at 6:42

[GoogleCodeExporter]

My doubt is if during the recursion the mapping between vertex opposed
to a verified 'delaunay' edge and the edge effectively 'delaunay' is broken,
then it is possible to skip the legalization of a non 'delaunay' edge.

Unconditionally clearing all flags does not seem the right solution.

Original comment by mvalenti...@gmail.com on 9 Apr 2014 at 4:40

[GoogleCodeExporter]

Yes the clearing of all edges was not a final solution. This issue needs some 
deeper analysis. 

Original comment by thahlen@gmail.com on 9 Apr 2014 at 1:52

[GoogleCodeExporter]

yes the fix suggested above does not work for example with a square of 6 points
per side.

Anyway the use of the delaunay_edge flags is wrong. You flag the edges before
calling RotateTrianglePair, which 'rotates' 2 flags per triangle and among
these two there are the newly set. IMO it should either 'rotate' 1 or 3
flags per triangle because the 2 edges not involved by the flip are
equivalent and their delaunay_edge property should be preserved or cleared
in the same way for both triangles.

The comment

        // We now got one valid Delaunay Edge shared by two triangles
        // This gives us 4 new edges to check for Delaunay

suggests that both should be cleared, but that would pose the problem
to clear them also in their opposite triangles. Probably, you should use
an EPSILON for the Incircle predicate (to avoid an infinite loop for
4 cocircular points) and get rid of these flags.

Original comment by mvalenti...@gmail.com on 9 Apr 2014 at 3:31