CGAL users discussion list

[Efraim Fogel <>]

Winnie Hellmann wrote:
> 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.
If you shoot, say upwards, then you get the unbounded face if there is 
nothing above the query point. If you hit an edge, the query point is 
inside the face incident to the edge. Otherwise, you hit a vertex. In 
this case you need to find the edge incident to the vertex, directed 
from left to right, such that its next edge (in the ccb) is also 
directed left to right; the query point is inside the face incident to 
this edge.
> 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
--
 ____  _        ____             _
/_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                       _/