polygon_set_2_join.cpp doesn't always finish

[mglisse]

Issue Details

I compiled and ran polygon_set_2_join from benchmark/Boolean_set_operations_2 and ran it several times. Most of the time it runs fine in less than 10s, but it happened several times that it was still running after a minute. It had already printed

Time for 402 grid crossing polygons 0.265669

so I assume the problem was with "1000 random polygons".

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): linux x86_64
• Compiler: gcc 10.2
• Release or debug mode: -O3 -DNDEBUG
• CGAL version: 5.1
• Boost version: 1.71

[lrineau]

@sgiraudot I have assigned the issue to you, because you worked on Bool_op_2 recently.

[sgiraudot]

I've managed to isolate the bug, it actually comes from the random polygon generator, from the internal function make_simple_polygon to be precise (used by the documented random_polygon_2() function). This function does not seem to ever exit its while() loop in some specific cases.

Here is a self contained executable to reproduce the bug:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Random_polygon_2_sweep.h>
#include <fstream>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using FT = Kernel::FT;
using Point_2 = Kernel::Point_2;

int main (int argc, char** argv)
{
  std::vector<Point_2> points;
  std::ifstream ifile (argv[1]);

  FT x, y;
  while (ifile >> CGAL::iformat(x) >> CGAL::iformat(y))
    points.emplace_back (x, y);
  std::cerr << points.size() << " points read" << std::endl;

  CGAL::make_simple_polygon (points.begin(), points.end(), Kernel());

  return EXIT_SUCCESS;
}

And a data set that triggers it:

131770319/2147483648 404716703/2147483648
-7282203/1073741824 -503278921/2147483648
667025647/2147483648 -999173425/2147483648
-20908641/1073741824 -49933297/1073741824
-13031191/2147483648 -453624967/1073741824
-363419953/1073741824 -260292757/2147483648
33972111/134217728 -378506333/1073741824
-824649493/2147483648 115611005/1073741824
553102093/2147483648 -49580561/2147483648
-265019085/536870912 -510361557/2147483648
-640947983/2147483648 -200336167/536870912
-322557653/2147483648 131436069/2147483648
-129975275/536870912 -410432817/1073741824
-70484617/1073741824 -1429825/2147483648
-368330131/2147483648 -653688121/2147483648
-826034925/2147483648 -137972797/536870912
-18806861/268435456 72092115/2147483648
-343169117/1073741824 49529383/536870912
123629525/536870912 610647239/2147483648
54369187/536870912 125763975/536870912
99282295/536870912 -726925951/2147483648
-463819043/2147483648 -741935549/2147483648
169838955/2147483648 -81113333/268435456
466210865/2147483648 -108074753/2147483648
112313935/1073741824 54223289/134217728
-675501983/2147483648 20406423/2147483648
-24956567/67108864 903181439/2147483648
-715342723/2147483648 931919811/2147483648
807043239/2147483648 210138933/536870912
264796623/1073741824 -396494793/2147483648
673569933/2147483648 755152301/2147483648
16828991/67108864 733171899/2147483648
216790047/1073741824 -513725481/1073741824
384948719/1073741824 5764479/1073741824
-835372243/2147483648 46319851/268435456
1044096965/2147483648 639926225/2147483648
764675499/2147483648 -174742469/2147483648
-335805391/2147483648 55668729/134217728
-32944539/67108864 -696815245/2147483648
501460283/1073741824 268607469/1073741824
643800781/2147483648 -217736147/2147483648
-63566787/268435456 -352997871/2147483648
-970820295/2147483648 -15957615/67108864
-445371317/1073741824 105687727/2147483648
1052262771/2147483648 285187277/2147483648
-958814061/2147483648 38872553/134217728
85217069/1073741824 -852800107/2147483648
-798030601/2147483648 444855889/2147483648
-622009589/2147483648 222172213/2147483648
1036086089/2147483648 -420435781/1073741824
-87941327/268435456 130875481/536870912
-23465531/1073741824 -673032251/2147483648
128172995/536870912 151893733/2147483648
-146859427/1073741824 25543705/536870912
-500771235/1073741824 -287298271/1073741824

[sloriot]

Maybe a duplicate of https://github.com/CGAL/cgal/issues/1445

[sgiraudot]

Yes, it does seem to trigger the same infinite loop. Note that in the case I posted, the sequence of vertices that keeps being inverted and back again is not of size 1 (compared to what was analyze in #1445).