Subject: CGAL users discussion list
List archive
- 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
- [cgal-discuss] polygon intersection, Hoang Giang Bui, 11/17/2015
- Re: [cgal-discuss] polygon intersection, Sebastien Loriot (GeometryFactory), 11/18/2015
- Re: [cgal-discuss] polygon intersection, Hoang Giang Bui, 11/19/2015
- Re: [cgal-discuss] polygon intersection, Sebastien Loriot (GeometryFactory), 11/18/2015
Archive powered by MHonArc 2.6.18.