[1.3.3] Issue with edge insertion (CDT::IntersectingConstraintEdges::Resolve)

[egladil86]

There seems to be a problem with edge insertion in [1.3.3] that worked fine in [1.3.0].

It triggers the assertion assert(triStart != noNeighbor); in Triangulation.hpp (line 1959) in Debug, or dereferences triangles[noNeighbor] in Release.

There are two intersecting edges AB and MN. CDT inserts the intersection point X and splits the two edges accordingly:

AB -> {AX, XB}
MN -> {MX, XN}

The problem occurs, when an edge BC (concatenating AB) is inserted, because the previous split set m_vertTris[B] = noNeighbor (only in [1.3.3]).

I was not able to reproduce this with a minimal example. Please find attached an example program triggering the issue: CdtEdgeInsertIssue.zip

By default it uses [1.3.3] and crashes. Configuring cmake with -DCDT_TAG=1.3.0 the triangulation works fine.

If this is not an code issue, but a problem with my input data, I would like to know how to determine that.

[artem-ogre]

Hello, @egladil86,

Thank you very much for opening the issue. Could you please format input as a text file that I could load into CDT visualizer? You can find some examples here: https://github.com/artem-ogre/CDT/tree/master/visualizer/data

The format is

NUMBER_OF_VERTICES NUMBER_OF_EDGES
X Y # first vertex, vertex index is 0
...
X Y # last vertex
START_VERTEX_INDEX END_VERTEX_INDEX # first edge
...
START_VERTEX_INDEX END_VERTEX_INDEX # last edge

for example a single triangle is written as:

3 3
-1 0
 1 0
 0 1
0 1
1 2
2 0

[artem-ogre]

There is a chance that the bug is introduced after 1.3.0

[egladil86]

Thanks for the fast reply. Here are the inputs in the visualizer format: CdtEdgeInsertIssue.txt

[artem-ogre]

@egladil86 Could you please check the bugfix branch? Does this work for your test cases? https://github.com/artem-ogre/CDT/tree/148-fix-bug-when-resolving-intersections

This bug was introduced as a merge error when I was rebasing a branch. Thank you very much for spotting it and more importantly opening such an easy to work with issue. :heart:

If your tests are passing, I will merge this ASAP, make a new release. For now I marked 1.3.3 as not ready for production.

[egladil86]

@artem-ogre Yes the fix works for this and all my other testcases. Thank you very much the fast solution.

[artem-ogre]

Thank you @egladil86. The fix is merged, I added you are on the contributors list.