Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] How do I get polygon intersection to work?

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] How do I get polygon intersection to work?


Chronological Thread 
  • From: Efi Fogel <>
  • To:
  • Subject: Re: [cgal-discuss] How do I get polygon intersection to work?
  • Date: Sat, 20 Jan 2007 11:30:19 +0200

Sounds like a classic case of limited precision problem.
Try to use an exact number type. For example:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;

Erik Engheim wrote:

I am using the Polygon_2 class. But I don't seem to get intersection tests with "do_intersect" from "Boolean_set_operations_2.h" to work properly. Most of the time it works but it doesn't seem to handle degenerate cases. In my case when the corner of a polygon intersects a line segment on another polygon.

I get the following assertion failure:
CGAL error: assertion violation!
Expr: *slIter == curve
File: /Users/Shared/CGAL-3.2.1/include/CGAL/Basic_sweep_line_2.h
Line: 591

Sometimes I have gotten this failure:
CGAL error: precondition violation!
Expr: Segment_assertions::_assert_is_point_on (p, cv, Has_exact_division()) && compare_xy(cv.left(), p) == SMALLER && compare_xy(cv.right(), p) == LARGER
File: /Users/Shared/CGAL-3.2.1/include/CGAL/Arr_segment_traits_2.h
Line: 730

The program below demonstrates the problem. When run I get the first assertion failure. Any suggestions to what is causing this? Am I using the library wrong or is this a bug in CGAL?

Cheers,
Erik

#include <CGAL/Cartesian.h>
#include <CGAL/basic.h>
#include <CGAL/Point_2.h>

#include <CGAL/Boolean_set_operations_2.h>

#include <iostream>

using namespace std;
using namespace CGAL;

typedef Cartesian<double> K;
typedef Point_2<K> Point2;
typedef Polygon_2<K> Polygon2;

int main()
{
Point2 small[] = {
Point2(3.0721924234843 , -1.0673205240039),
Point2(5.067320524004, -0.9278075765157),
Point2(4.9278075765157, 1.0673205240039),
Point2(2.9326794759961, 0.9278075765157)};

Point2 large[] = {Point2(-3,-3),
Point2(3,-3),
Point2(3,3),
Point2(-3,3)};

Polygon2 smallPoly(small, small+4);
Polygon2 largePoly(large, large+4);

cout << "do intersect? " << do_intersect(smallPoly, largePoly) << endl;
return 0;
}



--
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/







Archive powered by MHonArc 2.6.16.

Top of Page