CGAL users discussion list

[Olivier Devillers <>]

 a écrit :
> Hi,
>
> first of sorry for asking a question which is even covered in the CGAL-faq, 
> but
> I cant find any info on the following:
>
> My question is about triangulating the interior of a polygon. I use the
> constrained triangulation to get the triangulation of the convex hull with the
> edges of the polygons as constrained edges.
> How do I detect those faces which are inside/outside the area of the polygon?
>
> All I can think of is to check for each vertex of each face whether it is
> possible to
> reach the infinity vertex without crossing any constrained edge. But this
> approach
> looks quite awkward to me. Can somebody give me a hint how to do it ?
>
> Thank you very much in advance,
> David
>   

add a field "type"  in your faces  (e.g.  with the   with_info stuff)
with possible values  unknown  inside outside

then traverse the triangulation exploring all triangles through the
->neighbor(0)   ->neighbor(1)  ->neighbor(2) 
stopping the exploration if the triangle is statius is known
and giving the right status to the triangle othorwise
(from status of previous face and the fact that the edge is or not 
constrained)