CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

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