CDT Insert constraint error

[CARabelo]

I'm constructing a terrain with constraints that can intercept themselves, so I changed the third parameter of CDT to CGAL::Exact_intersections_tag. I supouse that the only reason to got an error in insert constraint is this, crossing constraint without the correct tag but is still occurring erros on CDT::insert_constraint. The exception text comes empty so I got stucked and can´t verify the reason and fix the code. the insertion code is:

ct.insert_constraint(P.vertices_begin(), P.vertices_end(), closed); closed is a boolean that is true when the constraint is closed (polygon).

Is a big surface with almost 500.000 points. On my code the error occurs on:

ct.insert_constraint(P.vertices_begin(), P.vertices_end(),closed);

the error occur on CGAL file Polyline_constraint_hierarchy_2.h.

the exceptin data is:

expr -> false file -> file = 0x00007ffbeb81d6b0 "C:\\dev\\CGAL- 5.0\\include\\CGAL\\Triangulation_2\\internal\\Polyline_constraint_hierarchy_2.h" line -> 1016 msg -> ""

The code on the file Polyline_constraint_hierarchy_2.h is:

template <class T, class Compare, class Data> void Polyline_constraint_hierarchy_2<T,Compare,Data>:: add_Steiner(T va, T vb, T vc){ Context_list* hcl=nullptr; if(!get_contexts(va,vb,hcl)) CGAL_triangulation_assertion(false); <<--- here

Context_list* hcl2 = new Context_list;

Vertex_it pos;

Sure the problem is on get_contexts;

Digging a litle more I got:

I tried to bypass this error just ignoring the polygons that cause an exception using a try catch block. This should solve the problem. The next step on my code (not shown in the sample) is simplify the lines.

PS::simplify(ct, CostSquare(), Stop(0.5),true);

But the program got stuck on an endless loop in file simplify.h line 206:

uh, vh, wh perform a right turn const Point& up = uh->point(); const Point& wp = wh->point(); Vertex_circulator circ = pct.incident_vertices(vh); while(circ != uh){ //<<<------- LINE 206 STUCKED HERE!!! ++circ; } ++circ; if(circ == wh){ typename PCT::Edge e;

• Operating system: Windows 10:
• Compiler: Microsoft Visual C++ 2019
• Release or debug mode: Debug
• Specific flags used (if any):
• CGAL version: CGAL-5.0
• Boost version: 1.71.0
• Other libraries versions if used (Eigen, TBB, etc.): Not Used

TesteCGAL.zip is my sample file. CampoGolf.zip is my points file with the polygons (open or closed) every line preceding the polygon is composed of <aaa,b,ccc> being:

aaa : sequential. b: boolean ( if polygon is closed or not) ccc: number of points belonging to this polygon

TesteCGAL.zip CampoGolf.zip

Hope it helps!

Thank you

Carlos A. Rabelo

[sloriot]

Could you try replacing Exact_predicates_inexact_constructions_kernel with Exact_predicates_exact_constructions_kernel? If you have intersection between constraints, then you need exact constructions to have a robust CDT.

[lrineau]

Check the documentation of CGAL::Exact_intersections_tag:

Intersection tag for constrained triangulations, if exact predicates and exact constructions are provided.

But your issue has nothing to do with the tag (CGAL::Exact_intersections_tag or CGAL::Exact_predicates_tag). I have reduced it to three polygons, using CGAL::Exact_intersections_tag and the kernel CGAL::Exact_predicates_inexact_constructions_kernel:

https://gist.github.com/lrineau/2773b59c223baa417a8d2107108c9b53

With CGAL-5.0, or CGAL-5.3-dev (from master), that leads to an infinite loop.

I am still working on the issue...

[CARabelo]

Please inform me Mr. Irineau:

you said that: "With CGAL-5.0, or CGAL-5.3-dev (from master), that leads to an infinite loop."

in version 5.2 this bug is not ocurring?

Thank you

[lrineau]

Please inform me Irineau:

you said that: "With CGAL-5.0, or CGAL-5.3-dev (from master), that leads to an infinite loop."

in version 5.2 this bug is not ocurring?

Actually, I have not tried. I have tried CGAL-5.0, because that was the version you tested, and I wanted to test if the bug was still in the master branch of CGAL (targeting CGAL-5.3).

[CARabelo]

Dear Mr Irineau I´m trying to work around this issue and decided simplify the polylines one by one. I tried to use the version of simplify that work with single polylines . Now I´m facing another problem depicted on stack overflow : https://stackoverflow.com/questions/66194851/pssimplification-with-3d-points but I got no help. Perhaps you can enlight me to find a solution: the version of Simplify I´m using is _PS::simplify(P1.begin(), P1.end(), CostSquare(), Stop(0.5), std::back_inserter(Result),Closed);_ (P1 is a polyline and Result is a 3d point std::deque) that has as 1st and 2nd parameters the begin and the end of the polyline (3d points) but the third parameter is a 3d point container but the PS::Simplify is not accepting a 3d point (Result). I guess that back inserter also should be a 3d point container. Could you please take a look on this? I will appreciate that. Thank you very much!

[sloriot]

The infinite loop is gone in master but now the following assertion fails:

terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: n >= 2
File: /home/sloriot/CGAL/git/master/Triangulation_2/include/CGAL/Constrained_triangulation_plus_2.h
Line: 615
Aborted

@lrineau @afabri what milestone should we put on this issue?

[lrineau]

@sloriot Can you please sum up how to reproduce the error?

[CARabelo]

I remember that ther error ocurred on simplify this terrain that is on campogolf.zip file. (This is a file of levelling curves all polylines, On the circular polylines the first point is equal to the last point). No matter if I simplify one by one or not the error ocurred. I Updated the version of CGAL and this problem did not happen anymore.

[sloriot]

@lrineau I think I took the original report and that's all.

[afabri]

The problem is in the user code.

  while (ArqTrian.good())
  {
    ArqTrian >> i >> Separator >> Closed >> Separator;
    Polygon_2_2 P;
    double x, y, z;

    for (ArqTrian >> QtdPoints; QtdPoints; --QtdPoints)
    {
      ArqTrian >> x >> Separator >> y >> Separator >> z;

      P.push_back(Point(x, y, z));
    }
    ct.insert_constraint(P.vertices_begin(), P.vertices_end(), (bool)Closed);
  }

When the last line with the coordinates is read the stream is still good() so we enter one more time in the whileloop. Then the operator>> do not read anything, the polygon P is empty and we get the assertion that a constraint must have at least two points.
Just write while( ArqTrian >> i >> Separator >> Closed >> Separator ) or test that P.size() >= 2 and it works,.