artem-ogre/CDT

Unexpected new vertices created; potential issues (or misuse of the API?)

jerstlouis opened this issue · 5 comments

jerstlouis commented

Thank you for this great library.

I am evaluating whether this library serves our tesselation purposes and running into some issues.

It might be that I am misunderstanding how to use the API...

I am using the following code to tesselate a single polygon (Canada1.geojson.zip)
with a single outer contour (no hole in this simple case, though support for holes is important). I don't believe the polygon has any self-intersection.

   CDT::Triangulation<double> cdt(
      CDT::VertexInsertionOrder::AsProvided,
      CDT::IntersectingConstraintEdges::NotAllowed, 1E-20);
   cdt.insertVertices(...);
   cdt.conformToEdges(...);
   cdt.eraseOuterTrianglesAndHoles();
   CDT::TriangleVec & triangles = cdt.triangles;

I should add that edge indices using any vertices with identical or < 1E-20 coordinates would already be mapped to the same vertex in the inserted vertices. There are cases in the polygon where the outer contour goes back on the same vertex, but it should be doing so following the validity rules (not intersecting itself).

There are two things confusing about the output:

  • There are more output vertices than provided in the input with cdt.insertVertices() (indices past the number of vertices added, that do not correspond to any existing vertex), which are referenced in the resulting triangles.
  • When matching those mismatched vertices to the closest original vertices, the result is what looks like inner contours and/or self-intersecting edges.

e.g., where this is expected (where blue lines represent the tesselation, and cyan lines represent outer contour edges identified from the tesselation result):

expected

resultExpectedFilled

the result is this:

cdtResult

resultFilled

Whereabouts of zoomed in area in overall polygon:

canada

Notice the missing triangulated area and the narrow spaces outside the outer contours that became inner holes.
Some of this might be a result of matching the output vertices to the closest input ones, but I don't understand why the tesselation creates these unwanted new vertices in the first place?

Thank you for any insights you could provide about this!

artem-ogre commented

Hello, @jerstlouis,

Thank you for looking into CDT and taking all the time to describe the issues you are facing in detail. I feel like most of these questions are answered in the documentation in one way or another.

  • Additional points are created because conformToEdges is used. To only triangulate input points one should use insertEdges instead. Former produces conforming Delaunay triangulation and latter produces constraint triangulation (here's the explanation of differences). Please take the time to read documentation of the methods for more details: insertEdges, conformToEdges
  • Please read about vertex insertion order. You probably want to use Auto as it's generally faster.
  • If you input is valid: no intersecting edges and no duplicate points, you don't need to set minDistToConstraintEdge at all, or can set it to zero.

Given all the points above the usage snippet should look something like this:

CDT::Triangulation<double> cdt;
cdt.insertVertices(...);
cdt.insertEdges(...);
cdt.eraseOuterTrianglesAndHoles();

Please let me know if this answers your questions or if you have further questions.
I'm closing the issue for now.

jerstlouis commented

@artem-ogre Thank you so much for the detailed explanation, and again for this library, which now seems to work great when using it properly! ;)

Apologies for not reading / understanding the documentation properly.

I had tried at first with insertEdges(), but at that time was missing the eraseOuterTrianglesAndHoles(), switched to
conformToEdges() before adding the erase, and failed to try again with insertEdges(). I must admit I did not understand the difference between those two methods.

If I may suggest, perhaps the documentation could benefit from some improvements to make this more obvious to people less familiar with CDT and this distinction between CDT and CCDT (and somewhat neurodivergent affecting how their brain (fail to) "read" docs). The main description says:

insertEdges(): Insert constraint edges into triangulation.

conformToEdges(): Ensure that triangulation conforms to constraints (fixed edges)

The distinction strictly between those two descriptions (which is what my brain focused on trying to understand the difference) is really not obvious. The way I (mis)understood this is that fixed edges is what I want (these edges I provide actually need to be in the tesselation result).

The Notes have more information (such as New vertices are inserted / No new vertices are inserted -- in bold even!), but somehow the fact that this information was inside a "note" averted my attention when trying to understand the distinction between those two methods.

Something else that threw me off was the title in the example of interest that says Constrained Delaunay triangulation (auto-detected boundaries and holes). I somehow (mis)understood that auto-detect is not what I want, since I already know and provide my boundaries and holes.

What I would suggest in terms of improvements to the docs is to extend that main description for the methods (not in the Note) with some text that clearly explains the distinction between insertEdges() and conformToEdges(), and/or points to explanation/picture of CDT vs CCDT. For example:

insertEdges(): Insert constraint edges into triangulation for Constrained Delaunay Triangulation (see example picture of CDT). Uses only original vertices.

conformToEdges(): Insert constraint edges into triangulation for Conforming Constrained Delaunay Triangulation (see example picture of CCDT). Introduces new vertices.

What I should have done is spend more time looking at the main example picture at the top, where the difference is obvious! :)

https://raw.githubusercontent.com/artem-ogre/CDT/master/docs/images/show-case.png

In any case, very happy now that this is working great, and will keep testing out the library which may just be perfect for our use case!

Thanks so much again!

  • 👍1
artem-ogre commented

Thank you for the detailed feedback! ❤️ I will try to improve the documentation.

  • ❤️1