assertion violation! when adding a point to Constrained Delaunay Triangulation

[petersadro]

I've found an issue while inserting points into an already constructed and remeshed CDT.

The CDT is serialized in a preliminary stage, then stitched with adjacent meshes which may add new points on the edges. When I add some points, I get an exception. Looking at the point I am adding, it looks like it should be valid.

I'm creating the gist right now, and will attach.

[petersadro]

gist is here. https://gist.github.com/petersadro/e36140c6ee2fe6e8593d9c98c523f370

I couldn't add cdt.txt to gist, as it locked up chrome :). I put it on dropbox, and linked in gist.

Pete

[petersadro]

I forgot to show the assertion:

./flightgear-terragear/debug/src/BuildTiles/cgal_tests/cgaltritest cdt.txt add_point.txt CDT valid? 1 terminate called after throwing an instance of 'CGAL::Assertion_exception' what(): CGAL ERROR: assertion violation! Expr: false File: /usr/local/include/CGAL/Polyline_constraint_hierarchy_2.h Line: 1004 Aborted

[lrineau]

@afabri The test also fails with CGAL-4.5. The Polyline_constraint_hierarchy_2 cannot be responsible.

[lrineau]

I think the I/O of CGAL::Constrained_triangulation_plus_2 are broken: nothing restores the constraints hierarchy.

[lrineau]

I confirm. After the load of the CDT, if I print the hierarchy object, gdb displays:

(gdb) p hierarchy $2 = {comp = {tr_p = 0x7fffffffd330}, c_to_sc_map = std::map with 0 elements, sc_to_c_map = std::map with 0 elements, vertex_map = std::map with 0 elements}

[lrineau]

Same in CGAL-4.7. If I print the CGAL::Polyline_constraint_hierarchy_2 object, I get the empty one:

$3 = {comp = {tr_p = 0x7fffffffd350}, constraint_set = std::set with 0 elements, sc_to_c_map = std::map with 0 elements, constraint_map = std::map with 0 elements}

[lrineau]

@petersadro Try to deserialize to a non-plus triangulation. With this patch:

diff --git a/tritest.cxx b/tritest.cxx
index 6876044..93f4a27 100644
--- a/tritest.cxx
+++ b/tritest.cxx
@@ -78,7 +78,7 @@ int main(int argc, char* argv[])
         return -1;
     }

-    meshTriCDTPlus  cdt;
+    meshTriCDT  cdt;

     cdt_file >> cdt;
     cdt_file.close();

you test programs runs fine. The issue is that the hierarchy of constraints, in the _plus_2 triangulations, has no input/output methods.

[petersadro]

I will try tomorrow morning. This looks promising.

By the way, In my actual program, I am using my own serialization of the CDT. I am storing this ins ESRI 2d shapefile metadata. The triangulation can then be saved - and visualized. I based my serialization on Constrained_Delaunay_Triangulation_2 ( vertices, then facets, then constraints ) Is there something else I should be serializing?

[petersadro]

After looking into how I generate the constraints, I decided I don't need CDTPlus anyway. I am already using an arrangement so there shouldn't be any intersecting constraints.

After changing to plan CDT, I have no crash. I suppose this is still a bug worth fixing,however.

[lrineau]

@afabri This bug is flagged 4.8.1. Will you have a look at it? The bug is that the polyline hierarchy is not saved and restored, by the I/O functions of CDTplus_2.

[sloriot]

@afabri Any chance you can fix it before the end of the week or shall we postpone it to 4.9?

[afabri]

We have to postpone it.

[lrineau]

@afabri: It seems that the fix will not make into CGAL-4.10 either. Should we relabel this issue to yet another later release? Or should we close it because we will never implement a valid operator>> for CDT_plus_2?

[petersadro]

I'm ok, either way. I have a workaround.

[sloriot]

@afabri Is there any technical reason that makes it complicated to fix the IO? I did not follow the issue but if there is an issue with IO and the hierarchy the simplest solution I see is simply to drop the hierarchy while writing to a file.

[afabri]

In fact the operators do the right thing since this commit (PR: https://github.com/CGAL/cgal/pull/3891)