Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] polygon intersection

Subject: CGAL users discussion list

List archive

[cgal-discuss] polygon intersection


Chronological Thread 
  • From: Hoang Giang Bui <>
  • To:
  • Subject: [cgal-discuss] polygon intersection
  • Date: Tue, 17 Nov 2015 22:00:07 +0100
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-phdr: 9a23:/my/XBzUHCR9NZTXCy+O+j09IxM/srCxBDY+r6Qd0e4VIJqq85mqBkHD//Il1AaPBtWGra8VwLOM4ujJYi8p39WoiDg6aptCVhsI2409vjcLJ4q7M3D9N+PgdCcgHc5PBxdP9nC/NlVJSo6lPwWB6kO74TNaIBjjLw09fr2zQd6PyZnmnLnoqtX6WEZhunmUWftKNhK4rAHc5IE9oLBJDeIP8CbPuWZCYO9MxGlldhq5lhf44dqsrtY4q3wD86Fpy8kVWqrze+E0TKdTES89G2Ez/szi8xfZHiWV4X5JcmIflBUALAnM6h6ydIrw+n/6ueB+gnHCbeX5SLk1XXKp6KI9G0ygszsOKzNsqDKfscd3lq8O+B8=

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




Archive powered by MHonArc 2.6.18.

Top of Page