CGAL: Intersection between a segment and a polygon?

Question

I have a set of polygons and I want to test intersection between it and a segment. I checked the manual but I cannot find a matching function. The intersection between points, lines, segments, triangles, planes do exist. And the intersection between polygons are also there. My question is:

1. Is there such a function?
2. If not, does it mean I need to break down the polygons into segments and do intersection among these segments? (The reason that I am reluctant to do this is, I thought CGAL might in fact use this way to do intersections between polygons. How come there is no such a function for intersecting a line and a polygon?) Or is there any other better way to do it?

Virilism

Answer 1

The easiest method is to create a Polygon_set_2 object which may contain several polygons. To test an intersection of an external polygon with this set you simply apply the do_intersect method.

For example:

typedef CGAL::Polygon_set_2<Kernel, std::vector<Kernel::Point_2>> Polygon_set_2;
Polygon_set_2 ps;
Polygon_2     poly;
Polygon_2     line; // line is a polygon defined by 2 points

ps.insert(poly);
bool intersect = ps.do_intersect(line);

More on polygon_set_2:

• http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Boolean_set_operations_2_ref/Class_General_polygon_set_2.html
• http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Boolean_set_operations_2_ref/Class_Polygon_set_2.html

I hope it's clear, Kiril

Compotation

Oh, I did not realize that a polygon can contain only two points. Seems works! – Virilism

is it ps.insert(poly); ps.insert(line); ? – Fairweather

I get this error: Explanation: The polygon boundary self overlaps. – Fairweather

It does not work for me. The error for me is Polygon_2 line; has only two points. Its says "Explanation: The polygon boundary self overlaps". As soon as I add a third point to this line, then it works. ANY SOLUTION???? – Fairweather

Yeah with CGAL 4.7 this definitely does not work. calling do_intersect() using a polygon with only two points in it fails with a message that "The polygon boundary self overlaps." and "The polygon is not simple." – Carmelitacarmelite

Polygon_set_2 working witk polygons with holes? For example add rectangle (with no holes stored in Polygon_with_holes) and add second rectangles (no intersections). How do it? How check is_simple polygons with holes and how check orientations – Namangan

Any solution to this? – Maggiore

I solved this problem by iterating over the edges of the polygon and intersecting every edge by itself. This is slow and doesn't handle the case of a segment contained completely in the polygon, but it worked in my case – Adamson