P2T2/P3T3: Periodic Delaunay triangulations make wrong assumptions about edge length (was Assertion in Periodic_2_triangulation_2<Gt, Tds>::is_valid_too_long_edges )

[lrineau]

https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-4.12-Ic-163/Periodic_2_triangulation_2_Examples/TestReport_gimeno_CentOS6.gz

------------------------------------------------------------------
- ProgramOutput.p2t2_hierarchy.CentOS6
------------------------------------------------------------------
CGAL::Random()::get_seed() = 1517456653
insertion of 1000 random points
The number of vertices at successive levels
number_of_vertices 1000
number_of_vertices 37
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: result
File: /mnt/testsuite/include/CGAL/Periodic_2_triangulation_2.h
Line: 1792
./cgal_test_with_cmake: line 70:  4756 Aborted                 (core dumped) ./p2t2_hierarchy

The release that was tested was composed from integration, but there no PR touching to any 2D package.

[lrineau]

Also in 4.12-I-154 (master), on Windows: https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-4.12-I-154/Periodic_2_triangulation_2_Examples/TestReport_afabri_x64_Cygwin-Windows8_MSVC2012-Release-64bits.gz

------------------------------------------------------------------
- ProgramOutput.p2t2_hierarchy.x64_Cygwin-Windows8_MSVC2012-Release-64bits
------------------------------------------------------------------
CGAL::Random()::get_seed() = 1516588220
CGAL::Random()::get_seed() = 1516588220
insertion of 1000 random points
The number of vertices at successive levels
number_of_vertices 1000
number_of_vertices 37
number_of_vertices 1
number_of_vertices 0
number_of_vertices 0
Assertion failed: t.is_valid(true), file C:\CGAL\test\CGAL-4.12-I-154\cmake\platforms\x64_Cygwin-Windows8_MSVC2012-Release-64bits\test\Periodic_2_triangulation_2_Examples\p2t2_hierarchy.cpp, line 38

[lrineau]

I grepped in test results of master during the release cycles of 4.11 and 4.12, and it was first seen in https://cgal.geometryfactory.com/CGAL/testsuite/results-4.12-I-60.shtml#Periodic_2_triangulation_2

[lrineau]

Might be related to PR #2369 merged a few days before CGAL-4.12-I-60.

[lrineau]

PR #2369 was already in CGAL-4.12-Ic-30, that shows the same error.

[afabri]

Seeding the random number generator with the value of the testsuite, I can reproduce the error on Windows. It happens in level 1 of the triangulation hierarchy. I stored the points in level 1, and inserting them (or even a subset of them) into a periodic triangulation without hierarchy has the same error. I have put the condensed program here so that @MoniqueTeillaud or @MaelRL can debug it.

[MaelRL]

It crashes with that input since the dawn of time so it's not #2369.

[MaelRL]

The problem is that P2T2 wrongly assumes that the longest edge length can only decrease with the insertion of a point and is missing the update_cover_during_insertion() management system that is in P3T3 to deal with this case. Three solutions:

• A brute force fix, simply add use find_too_long_edges() and switch the cover if needed in the insert(). Fixes the issue.
• Add the cover management system like in P3DT3.
• Replace the criterion on edges by a criterion on circumsphere diameter, which is the "real" criterion in the paper. Tougher criterion but you don't need to check the new triangles because the diameter always decreases.

Not sure what to do between 2nd and 3rd. Probably 2nd because P2T2 has also fallen behind P3T3 (like Alpha_shape_2 has fallen behind Alpha_shape_3) and needs to be brought up to date and it's easier to keep symmetry with P3T3.

[lrineau]

I am not the one taking decisions, but I agree with you with the second option, because that seems the one improving the long-term maintainability of P2T2.

[MoniqueTeillaud]

As said in email, I would rather favor option 3. It is easier to do.

It is clean and does not compromise long term maintenance. The code will look simpler than when adding the cover management system like in 3d, so it is even potentially easier to maintain.

Symmetry with P3T3 does not look so important to me. T2 is also not aligned with T3...

[MaelRL]

For the record, option 3 is (slowly) being done in the following branch: https://github.com/MaelRL/cgal/tree/P2T2-Fix_edge_length_bound_condition-GF.

Additionally, I was mistaken above and P3_Delaunay_triangulation_3 is also affected (I had only looked at P3_regular_triangulation_3, which should be fine since it based on the weighted circumradius).

[MoniqueTeillaud]

Why is P3DT3 also affected? I had understood from the discussion above that the problem in 2d was due to the fact that there is no covering spaces.

[MaelRL]

P2T2 has covering spaces just like P3T3, what is different is the way conflict zones, remove, and insert are computed: P2T2 is based on T2 and uses flipping shenanigans while P3T3 is based on T3 and use helpers like "conflict_helper", "removal_helper", etc. to work with regular triangulations. This means that it has some type of "callback" functions that are hooking back from P3T3 to either P3DT3 or P3RT3, for example update_cover_during_insertion.

I looked too quickly and assumed this meant that the update_cover_during_insertion function would switch to 1 or 27 depending on the status of the too_long_edges container, but, if I remember correctly, it only does switches to 1-covers. Thus, you could very well have the same issue as for P2DT2: insert a point, edges become too long, cover is not changed.

It will be quick to fix for P3DT3: it's just changing the bound to be circumradii. P2DT2 is more annoying because I have to check in all the flipping functions when faces circumradii need to be checked.

(Reminder that the offset should be defined in the traits, and not directly via ::CGAL::P2Offset_2 in the Vb in P2T2_Vb)

[lrineau]

I have modified the title, to help future searches of this issue.