Triangulation and holes are inverted for certain meshes

[GlassBeaver]

Hi, first of all thanks so much for CDT, it's an excellent library. I have an issue with the lib "inverting" certain meshes - it's confusing normal triangles with hole triangles:

The filled areas are what I'm getting but I want exactly the inverse. I'm running CDT like this:

CDT::RemoveDuplicatesAndRemapEdges(pointsCDT, edgesCDT);
CDT::Triangulation<float> cdt;
cdt.insertVertices(pointsCDT);
cdt.insertEdges(edgesCDT);
cdt.eraseOuterTrianglesAndHoles();

Not sure if it helps but I've attached the vertices and edges I'm supplying it with:

vertices_and_edges.txt

It works perfectly with almost all of my other meshes so I'm very happy to be using it.

[artem-ogre]

Hi, David,

Thanks for using CDT and for opening the issue. What you experience is caused by the intersecting constraint edges in your input:

Please check the README for preconditions when CDT guarantees the correct result:

Pre-conditions:

No duplicated points (use provided functions for removing duplicate points and re-mapping edges) No two constraint edges intersect each other (overlapping boundaries are allowed)

You have few ways to approach this problem:

• provide an input that does not contain intersecting edges
• pass CDT::IntersectingConstraintEdges::Resolve to Triangulation constructor. For example:

  auto cdt = Triangulation(
          CDT::VertexInsertionOrder::Randomized,
          CDT::IntersectingConstraintEdges::Resolve,
          1e-6);

  Then CDT will try to automatically resolve intersecting edges. It will work for most of the cases, but since resolving intersection requires calculating position of intersection and inserting it into the triangulation it is no longer possible to guarantee 100% correct result (due to rounding errors). With CDT::IntersectingConstraintEdges::Resolve I get this result:

Please let me know if this solves your issue.

[GlassBeaver]

Thanks very much for getting back and on such a short notice too, CDT::IntersectingConstraintEdges::Resolve has indeed fixed the issue.

In the meantime I've found out that using conformToEdges() instead of insertEdges() will also result in the correct triangulation. What's the subtle difference between conformToEdges() and insertEdges()+CDT::IntersectingConstraintEdges::Resolve?

[artem-ogre]

conformToEdges enforces constraints by recursively inserting edge mid point into the triangulation until the edge is present (as a sum of its subdivided parts). On the other hand, insertEdges enforces the edge by re-triangulating a polygon formed by all triangles intersected by the edge.

Keep in mind that, as with resolving the edges, conform-to-edge requires calculation of new points (not present in the input) at the middle of the edge. So it is no longer possible to guarantee 100% correct result (due to the rounding errors introduced when calculating new points).