CGAL users discussion list

[Winnie Hellmann <>]

Hi list!

Is there a way to find out whether a point is in the interior of a 
polygon (with holes) stored in an 2D arrangement? I.e. I want to 
determine if the point is inside the outer boundary of an arrangement, 
but not inside any of it's holes. I assume that all arrangements I want 
to process are actually polygons with holes (so no crossing edges, no 
isolated vertices, only closed components).

I thought about vertical ray shooting, but since it does not return the 
feature a query point is located nor all edges/vertices above or below, 
I can't count the intersected CCBs that way. I can't make multiple ray 
shoots either since the total query should be of linear complexity.

Also I thought of checking whether the point is to the left of every 
edge in the arrangement. But since I can not decide if an edge belongs 
to a hole (or can I?), I don't know when the point has to be on the 
right side (as far as I know CCBs are always counter-clock-wise).

I could also do point location, but as far as I know all point location 
algorithms in CGAL that can handle points outside the convex hull of the 
arrangement have more than linear complexity.

Can anybody give me a hint on what to do? Obviously copying all my stuff 
into a Polygon_with_holes_2 just for the check is not a good idea when 
it comes to multiple hundreds of vertices...

Thanks in advance!
Winnie