Subject: CGAL users discussion list
List archive
[cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions
Chronological Thread
- From: Panaghis Mavrokefalos <>
- To:
- Subject: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions
- Date: Fri, 9 Oct 2015 08:36:00 +0300
- Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
- Ironport-phdr: 9a23:46ZepxQygjzhfMp9Cg2FchcASNpsv+yvbD5Q0YIujvd0So/mwa64YReN2/xhgRfzUJnB7Loc0qyN4/ymBDRIyK3CmU5BWaQEbwUCh8QSkl5oK+++Imq/EsTXaTcnFt9JTl5v8iLzG0FUHMHjew+a+SXqvnYsExnyfTB4Ov7yUtaLyZ/ni6bvo9X6WEZhunmUWftKNhK4rAHc5IE9oLBJDeIP8CbPuWZCYO9MxGlldhq5lhf44dqsrtY4q3wD86Fpy8kVWqrze+E0TKdTES89G2Ez/szi8xfZHiWV4X5JamwQmxVIAhONyRjkRJDyvyXzsu1mkH2CNMv/QrA1QjGr8b1sSxLmgSMALBY29WjWjop7i6cN80HpnAB234OBONLdD/F5ZK6IJd4=
Hello,
I have been using the minkowski_sum_2() function from the 2D Minkowski Sums
package to compute the sums of some non-convex, but simple polygons. In some of
my test cases, I noticed CGAL assertion failures (pre- and post-condition
failures) at runtime, which I traced to calls of that function. I am aware that
these sort of errors occur when using a kernel with inexact consrtuctions, but
I made sure I was using the Exact_predicates_exact_constructions_kernel. At
first, I tried replacing the default (convolution) strategy with a
decomposition strategy (I chose Greene_convex_decomposition_2), but then the
errors occurred in another test case.
A test file is attached, reproducing the cases which triggerred the errors. The
CMakeLists.txt file is generated using `cgal_create_CMakeLists -s main`. I am
building with g++ version 4.8.4 and using CGAL version 4.5.1, configured with
CMAKE_CXX_FLAGS=-frounding-math -std=c++11.
There are four different test cases, corresponding to the first command line
argument of the executable equal to 0 through 3. The simplicity of the input
polygons to the minkowski_sum_2() function is explicitly tested before the
call. For each test case, the output of the run of the executable is shown:
./main 0
p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Precondition_exception'
what(): CGAL ERROR: precondition violation!
Expr: nodeP != NULL && nodeP->is_valid()
File: /usr/local/include/CGAL/Multiset.h
Line: 339
Aborted
./main 1
p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Assertion_exception'
what(): CGAL ERROR: assertion violation!
Expr: (!is_valid(i)) || (!is_valid(s)) || (!(i>s))
File: /usr/local/include/CGAL/Interval_nt.h
Line: 139
Explanation: Variable used before being initialized (or CGAL bug)
Aborted
./main 2
p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Precondition_exception'
what(): CGAL ERROR: precondition violation!
Expr: nodeP != NULL && nodeP->is_valid()
File: /usr/local/include/CGAL/Multiset.h
Line: 339
Aborted
./main 3
p is simple
q is simple
Computing the Minkowski sum of p and q using the Greene decomposition strategy
terminate called after throwing an instance of 'CGAL::Postcondition_exception'
what(): CGAL ERROR: postcondition violation!
Expr: convex_partition_is_valid_2(polygon.vertices_begin(), polygon.vertices_end(), res.output_so_far_begin(), res.output_so_far_end(), traits)
File: /usr/local/include/CGAL/Partition_2/partition_greene_approx_convex_2.h
Line: 834
Aborted
Since, as mentioned before, I am using an exact constructions kernel, and a
variety of different errors are produced, I am at a loss as to what is wrong.
Any help would be greatly appreciated.
I have been using the minkowski_sum_2() function from the 2D Minkowski Sums
package to compute the sums of some non-convex, but simple polygons. In some of
my test cases, I noticed CGAL assertion failures (pre- and post-condition
failures) at runtime, which I traced to calls of that function. I am aware that
these sort of errors occur when using a kernel with inexact consrtuctions, but
I made sure I was using the Exact_predicates_exact_constructions_kernel. At
first, I tried replacing the default (convolution) strategy with a
decomposition strategy (I chose Greene_convex_decomposition_2), but then the
errors occurred in another test case.
A test file is attached, reproducing the cases which triggerred the errors. The
CMakeLists.txt file is generated using `cgal_create_CMakeLists -s main`. I am
building with g++ version 4.8.4 and using CGAL version 4.5.1, configured with
CMAKE_CXX_FLAGS=-frounding-math -std=c++11.
There are four different test cases, corresponding to the first command line
argument of the executable equal to 0 through 3. The simplicity of the input
polygons to the minkowski_sum_2() function is explicitly tested before the
call. For each test case, the output of the run of the executable is shown:
./main 0
p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Precondition_exception'
what(): CGAL ERROR: precondition violation!
Expr: nodeP != NULL && nodeP->is_valid()
File: /usr/local/include/CGAL/Multiset.h
Line: 339
Aborted
./main 1
p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Assertion_exception'
what(): CGAL ERROR: assertion violation!
Expr: (!is_valid(i)) || (!is_valid(s)) || (!(i>s))
File: /usr/local/include/CGAL/Interval_nt.h
Line: 139
Explanation: Variable used before being initialized (or CGAL bug)
Aborted
./main 2
p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Precondition_exception'
what(): CGAL ERROR: precondition violation!
Expr: nodeP != NULL && nodeP->is_valid()
File: /usr/local/include/CGAL/Multiset.h
Line: 339
Aborted
./main 3
p is simple
q is simple
Computing the Minkowski sum of p and q using the Greene decomposition strategy
terminate called after throwing an instance of 'CGAL::Postcondition_exception'
what(): CGAL ERROR: postcondition violation!
Expr: convex_partition_is_valid_2(polygon.vertices_begin(), polygon.vertices_end(), res.output_so_far_begin(), res.output_so_far_end(), traits)
File: /usr/local/include/CGAL/Partition_2/partition_greene_approx_convex_2.h
Line: 834
Aborted
Since, as mentioned before, I am using an exact constructions kernel, and a
variety of different errors are produced, I am at a loss as to what is wrong.
Any help would be greatly appreciated.
#include <iostream> #include <string> #include <vector> #include <CGAL/Exact_predicates_exact_constructions_kernel.h> #include <CGAL/Polygon_2.h> #include <CGAL/Aff_transformation_2.h> #include <CGAL/minkowski_sum_2.h> #include <CGAL/Polygon_convex_decomposition_2.h> using K = CGAL::Exact_predicates_exact_constructions_kernel; using Point = K::Point_2; using Vector = K::Vector_2; using Segment = K::Segment_2; using Direction = K::Direction_2; using Polygon = CGAL::Polygon_2<K>; using Polygon_with_holes = CGAL::Polygon_with_holes_2<K>; using Transformation = CGAL::Aff_transformation_2<K>; std::vector<Polygon> polys; std::vector<std::vector<Point>> pts { { {9, 0}, {31, 0}, {31, 1}, {33, 3}, {34, 3}, {36, 5}, {38, 5}, {38, 7}, {39, 8}, {40, 8}, {41, 9}, {41, 11}, {42, 12}, {42, 18}, {43, 19}, {44, 19}, {44, 23}, {43, 24}, {42, 24}, {41, 25}, {41, 28}, {40, 29}, {40, 30}, {39, 31}, {39, 35}, {40, 35}, {40, 39}, {39, 40}, {39, 43}, {40, 43}, {40, 44}, {42, 46}, {43, 46}, {44, 47}, {44, 54}, {34, 54}, {33, 53}, {32, 53}, {31, 52}, {30, 52}, {30, 53}, {28, 53}, {27, 54}, {25, 54}, {24, 55}, {23, 55}, {22, 56}, {20, 56}, {19, 57}, {9, 57}, {7, 55}, {7, 53}, {6, 52}, {6, 48}, {5, 47}, {1, 47}, {0, 46}, {0, 33}, {1, 33}, {2, 32}, {5, 32}, {7, 30}, {1, 30}, {0, 29}, {0, 18}, {1, 17}, {2, 17}, {4, 15}, {4, 6}, {5, 5}, {5, 4} }, { {-9, 0}, {-31, 0}, {-31, -1}, {-33, -3}, {-34, -3}, {-36, -5}, {-38, -5}, {-38, -7}, {-39, -8}, {-40, -8}, {-41, -9}, {-41, -11}, {-42, -12}, {-42, -18}, {-43, -19}, {-44, -19}, {-44, -23}, {-43, -24}, {-42, -24}, {-41, -25}, {-41, -28}, {-40, -29}, {-40, -30}, {-39, -31}, {-39, -35}, {-40, -35}, {-40, -39}, {-39, -40}, {-39, -43}, {-40, -43}, {-40, -44}, {-42, -46}, {-43, -46}, {-44, -47}, {-44, -54}, {-34, -54}, {-33, -53}, {-32, -53}, {-31, -52}, {-30, -52}, {-30, -53}, {-28, -53}, {-27, -54}, {-25, -54}, {-24, -55}, {-23, -55}, {-22, -56}, {-20, -56}, {-19, -57}, {-9, -57}, {-7, -55}, {-7, -53}, {-6, -52}, {-6, -48}, {-5, -47}, {-1, -47}, {0, -46}, {0, -33}, {-1, -33}, {-2, -32}, {-5, -32}, {-7, -30}, {-1, -30}, {0, -29}, {0, -18}, {-1, -17}, {-2, -17}, {-4, -15}, {-4, -6}, {-5, -5}, {-5, -4} }, { {0, 0}, {2, 0}, {3, 1}, {3, 2}, {4, 3}, {4, 4}, {5, 5}, {5, 3}, {6, 3}, {7, 2}, {7, 0}, {17, 0}, {17, 2}, {18, 3}, {19, 3}, {20, 4}, {20, 5}, {21, 6}, {21, 2}, {22, 1}, {22, 0}, {28, 0}, {29, 1}, {32, 1}, {34, 3}, {34, 18}, {33, 19}, {31, 19}, {30, 20}, {27, 20}, {26, 21}, {26, 23}, {25, 24}, {25, 25}, {24, 26}, {24, 27}, {23, 28}, {23, 32}, {22, 33}, {22, 36}, {23, 36}, {23, 41}, {13, 41}, {12, 40}, {12, 39}, {11, 38}, {7, 38}, {6, 37}, {2, 37}, {2, 36}, {1, 35}, {1, 33}, {0, 32}, {0, 25}, {1, 24}, {1, 22}, {0, 22} } }; void test(std::size_t i, std::size_t j, bool default_strategy) { const Polygon& p{polys[i]}; const Polygon& q{polys[j]}; std::cout << "p is " << (p.is_simple() ? "" : "not") << "simple\n"; std::cout << "q is " << (q.is_simple() ? "" : "not") << "simple\n"; std::cout << "Computing the Minkowski sum of p and q using "; if (default_strategy) { std::cout << "the default strategy\n"; Polygon_with_holes ms_default{minkowski_sum_2(p, q)}; } else { std::cout << "the Greene decomposition strategy\n"; Polygon_with_holes ms_greene{minkowski_sum_2(p, q, CGAL::Greene_convex_decomposition_2<K>())}; } std::cout << "Success\n"; } int main(int argc, char* argv[]) { CGAL::set_pretty_mode(std::cout); std::transform(pts.begin(), pts.end(), std::back_inserter(polys), [](const std::vector<Point>& p){ return Polygon{p.begin(), p.end()}; }); if (argc != 2) { std::cerr << "The test case number argument is required\n"; return -1; } int test_case{std::stoi(argv[1])}; // All calls below cause a CGAL assertion failure: switch (test_case) { case 0: test(0, 1, true); break; case 1: test(1, 1, true); break; case 2: test(0, 2, true); break; case 3: test(0, 2, false); break; default: std::cerr << "Invalid test case number\n"; return -1; } }
- [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Panaghis Mavrokefalos, 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Sebastien Loriot (GeometryFactory), 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Panaghis Mavrokefalos, 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Efi Fogel, 10/10/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Panaghis Mavrokefalos, 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Sebastien Loriot (GeometryFactory), 10/09/2015
Archive powered by MHonArc 2.6.18.