I am using CGAL to compute the area of the intersection of two convex polygons. A short demo code for doing this was posted in the accepted answer to this question. However, when I modify that code to use the polygons that I am interested in, CGAL throws a runtime exception from deep in the CGAL::intersection() routine.
Here is a short example code, which is copy-and-paste from the SO question linked above, except that it uses my own polygons and it prints some diagnostics about each polygon to show that they are convex and use a CCW winding order.
#include <iostream>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2_algorithms.h>
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes_2;
using std::cout; using std::endl;
int main(){
bool IsSimple, IsConvex, IsClockwise;
double Area;
// Define the polygons. P is long and skinny, Q is 20 equally
// spaced points around a circle of radius 0.025. The top-right
// corner of P protudes into Q.
int np=7;
int nq=20;
Point points[]={
Point( 2.67905949256324049657e-02,-2.36307305336680428809e-02),
Point( 2.19804738309115066386e-02, 1.25954939609798088895e-02),
Point( 3.24142504626934169210e-03, 8.27109808759729503436e-03),
Point(-7.07297020897392769712e-02,-1.31780902623212625713e-01),
Point(-1.72945875771868884385e+00,-4.33625989924519217311e+00),
Point(-5.64696462817379796206e+00,-2.91346747524371210147e+01),
Point(-5.66016394049875870564e+00,-4.95259849820236013329e+01)};
Point points2[]={
Point( 2.50000000000000013878e-02, 0.00000000000000000000e+00),
Point( 2.37764129073788424429e-02, 7.72542485937368662852e-03),
Point( 2.02254248593736890571e-02, 1.46946313073118266929e-02),
Point( 1.46946313073118284276e-02, 2.02254248593736890571e-02),
Point( 7.72542485937368836324e-03, 2.37764129073788424429e-02),
Point( 1.53080849893419158600e-18, 2.49999999999999979183e-02),
Point(-7.72542485937368489379e-03, 2.37764129073788424429e-02),
Point(-1.46946313073118232234e-02, 2.02254248593736890571e-02),
Point(-2.02254248593736890571e-02, 1.46946313073118284276e-02),
Point(-2.37764129073788424429e-02, 7.72542485937368923060e-03),
Point(-2.50000000000000013878e-02, 3.06161699786838317201e-18),
Point(-2.37764129073788424429e-02,-7.72542485937368402643e-03),
Point(-2.02254248593736925266e-02,-1.46946313073118232234e-02),
Point(-1.46946313073118318970e-02,-2.02254248593736890571e-02),
Point(-7.72542485937369096533e-03,-2.37764129073788389734e-02),
Point(-4.59242549680257437283e-18,-2.50000000000000013878e-02),
Point( 7.72542485937368229171e-03,-2.37764129073788424429e-02),
Point( 1.46946313073118214887e-02,-2.02254248593736925266e-02),
Point( 2.02254248593736855877e-02,-1.46946313073118318970e-02),
Point( 2.37764129073788389734e-02,-7.72542485937369183269e-03)};
Polygon_2 polyP(points, points+np);
Polygon_2 polyQ(points2, points2+nq);
// Print some properties of polygon P. It is simple, convex, and CCW
// oriented
CGAL::set_pretty_mode(cout);
cout << "created the polygon P:" << endl;
cout << polyP << endl;
cout << endl;
IsSimple = polyP.is_simple();
IsConvex = polyP.is_convex();
IsClockwise = (polyP.orientation() == CGAL::CLOCKWISE);
Area = polyP.area();
cout << "polygon P is";
if (!IsSimple) cout << " not";
cout << " simple." << endl;
cout << "polygon P is";
if (!IsConvex) cout << " not";
cout << " convex." << endl;
cout << "polygon P is";
if (!IsClockwise) cout << " not";
cout << " clockwise oriented." << endl;
cout << "the area of polygon P is " << Area << endl;
cout << endl;
// Print some properties of polygon Q. It is simple, convex, and CCW
// oriented
cout << "created the polygon Q:" << endl;
cout << polyQ << endl;
cout << endl;
IsSimple = polyQ.is_simple();
IsConvex = polyQ.is_convex();
IsClockwise = (polyQ.orientation() == CGAL::CLOCKWISE);
Area = polyQ.area();
cout << "polygon Q is";
if (!IsSimple) cout << " not";
cout << " simple." << endl;
cout << "polygon Q is";
if (!IsConvex) cout << " not";
cout << " convex." << endl;
cout << "polygon Q is";
if (!IsClockwise) cout << " not";
cout << " clockwise oriented." << endl;
cout << "the area of polygon Q is " << Area << endl;
cout << endl;
// Compute the intersection
std::list<Polygon_with_holes_2> polyI;
CGAL::intersection(polyP, polyQ, std::back_inserter(polyI));
double totalArea = 0;
typedef std::list<Polygon_with_holes_2>::iterator LIT;
for(LIT lit = polyI.begin(); lit!=polyI.end(); lit++){
totalArea+=lit->outer_boundary().area();
}
cout << "TotalArea::" << totalArea;
return 0;
}
Here is the output of the test program.
created the polygon P:
Polygon_2(
PointC2(0.0267906, -0.0236307)
PointC2(0.0219805, 0.0125955)
PointC2(0.00324143, 0.0082711)
PointC2(-0.0707297, -0.131781)
PointC2(-1.72946, -4.33626)
PointC2(-5.64696, -29.1347)
PointC2(-5.66016, -49.526)
)
polygon P is simple.
polygon P is convex.
polygon P is not clockwise oriented.
the area of polygon P is 71.1027
created the polygon Q:
Polygon_2(
PointC2(0.025, 0)
PointC2(0.0237764, 0.00772542)
PointC2(0.0202254, 0.0146946)
PointC2(0.0146946, 0.0202254)
PointC2(0.00772542, 0.0237764)
PointC2(1.53081e-18, 0.025)
PointC2(-0.00772542, 0.0237764)
PointC2(-0.0146946, 0.0202254)
PointC2(-0.0202254, 0.0146946)
PointC2(-0.0237764, 0.00772542)
PointC2(-0.025, 3.06162e-18)
PointC2(-0.0237764, -0.00772542)
PointC2(-0.0202254, -0.0146946)
PointC2(-0.0146946, -0.0202254)
PointC2(-0.00772542, -0.0237764)
PointC2(-4.59243e-18, -0.025)
PointC2(0.00772542, -0.0237764)
PointC2(0.0146946, -0.0202254)
PointC2(0.0202254, -0.0146946)
PointC2(0.0237764, -0.00772542)
)
polygon Q is simple.
polygon Q is convex.
polygon Q is not clockwise oriented.
the area of polygon Q is 0.00193136
terminate called after throwing an instance of 'CGAL::Precondition_exception'
what(): CGAL ERROR: precondition violation!
Expr: (m_traits.compare_y_at_x_2_object()(p, cv) == EQUAL) && compare_xy(cv.left(), p) == SMALLER && compare_xy(cv.right(), p) == LARGER
File: /usr/local/include/CGAL/Arr_segment_traits_2.h
Line: 706
Aborted (core dumped)
I do not understand what is causing the error. Any help would be appreciated.
I can reproduce this error (using CGAL 4.9 on MacOS with clang++). As far as I understand, an uncaught exception of this type is not supposed to happen, in other words, you have uncovered a bug in CGAL. So, do file a bug report as instructed in the error message –– the part that you didn't post (or perhaps didn't get because of a different version?):
Explanation: Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html
libc++abi.dylib: terminating with uncaught exception of type CGAL::Precondition_exception: CGAL ERROR: precondition violation!
Expr: (m_traits.compare_y_at_x_2_object()(p, cv) == EQUAL) && compare_xy(cv.left(), p) == SMALLER && compare_xy(cv.right(), p) == LARGER
File: /usr/local/include/CGAL/Arr_segment_traits_2.h Line: 706
As far as I can see from that file, the function throwing splits a curve into two sub-curved given a split point. The pre-condition is that the split point lies on the curve and it not an end point. Clearly, whether this pre-condition is met or not is a matter of the caller, another CGAL routine. In other words, there is nothing wrong with your input. What's wrong is the CGAL implementation, or more precisely, its way of dealing with imprecision of the number representation used.
Edit following sloriot's comment.
If I replace
typedef CGAL::Simple_cartesian<double> K;
with
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
and use the appropriate type for Area and totalArea (I simply used auto and decltype(Area), respectively), the code compiles (you must link it against libgmp and libmpfr) and runs without crash, reporting
totalArea::0.000876944