CGAL users discussion list

[Hoang Giang Bui <>]

Dear list

I have a question regarding the robustness of the intersection algorithm of 2 polygons using CGAL. For the example below, CGAL failed to produce the correct result

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

int main(void)

{

    double data1[] = {

         -1.637348598514268e+01,-15,

         -1.080050138869282e+01,-15,

         -1.080050138869283e+01,15,

         -1.637348598514268e+01,15};

    double data2[] = {

         -1.216086355952537e+01,15,

         -1.216086355952538e+01,-15,

         -6.925474894430892e+00,-15,

         -6.925474894430885e+00,15

         };

    std::vector<Point> points;

    for(int i = 0; i < 4; ++i)

        points.push_back(Point(data1[2*i], data1[2*i+1]));

    std::vector<Point> points2;

    for(int i = 0; i < 4; ++i)

        points2.push_back(Point(data2[2*i], data2[2*i+1]));

    Polygon_2 poly1(points.begin(), points.end());

    if(poly1.orientation() == CGAL::CLOCKWISE)

    {

        poly1.reverse_orientation();

        std::cout << "poly1 is reversed" << std::endl;

    }

    Polygon_2 poly2(points2.begin(), points2.end());

    if(poly2.orientation() == CGAL::CLOCKWISE)

    {

        poly2.reverse_orientation();

        std::cout << "poly2 is reversed" << std::endl;

    }

    //CGAL::General_polygon_with_holes_2<K> poly3;

    std::list<Polygon_with_holes_2> polyI;

    CGAL::intersection(poly1, poly2, 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();

        std::cout << lit->outer_boundary() << std::endl;

        std::cout << std::endl;

    }

    std::cout << "TotalArea: " << totalArea << std::endl;

}

If we change the data1 slightly to

double data1[] = {

         -1.637348598514268e+01,-15,

         -1.080050138869283e+01,-15,

         -1.080050138869283e+01,15,

         -1.637348598514268e+01,15};

The correct result is reproduced. This shows that the result is quite sensitive with the input. Although this example is a degenerate case where the rectangles are overlapping on horizontal edge. But I think the intersection algorithm should be able to handle this. In case that is the default behaviour of CGAL, what should I do to improve the result of the degenerate case?

Giang Bui