CGAL users discussion list

[Panaghis Mavrokefalos <>]

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.

#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;
    }
}