CGAL users discussion list

[Hoang Giang Bui <>]

Thanks for the hint, it works

Bui

On Wed, Nov 18, 2015 at 8:59 AM, Sebastien Loriot (GeometryFactory) <> wrote:

The intersection function comes from the package
2D Regularized Boolean Set-Operations [1] where the operations
are regularized. In particular this implies that the intersection
of two polygons is ignored if its dimension is not 2.

Note that you must use a kernel with exact constructions such as CGAL:Exact_predicates_exact_constructions_kernel.

Sebastien.

[1] http://doc.cgal.org/latest/Boolean_set_operations_2/index.html

On 11/17/2015 10:00 PM, Hoang Giang Bui wrote:

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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

--

With Best Regards !
Giang Bui

To learn and to excel