# Triangulating non-convex polygon

3 messages
Open this post in threaded view
|

## Triangulating non-convex polygon

 Hello, I've been struggling with this problem for a while now and the information on the documentation and on the mailing list is not really helpful... I want to tryangulate a Fisk Polygon (the one that looks like a crown, used to proof Art Gallery theorem). Or any other non-convex polygon. Like this one: However when I use the Triangulation provieded by   CGAL what I get is a triangulation that includes incorrect faces as seen: Whilst the real triangulation is this one: What is the easiest way to avoid having those extra 4 faces? (the ones in the middle of each peak) Thanks in advance -- Sent from: http://cgal-discuss.949826.n4.nabble.com/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: Triangulating non-convex polygon

 Hello, According to https://doc.cgal.org/latest/Triangulation_2/index.html#title0, "the triangulations of CGAL are complete triangulations which means that their domain is the convex hull of their vertices". Your polygon is non-convex, and this is why these four faces are there. If you want to get the faces of the triangulation of your non-convex polygon, you can just start from a face that you know is inside (which can be found by using 'locate()' on a point you know is inside the polygon), and then using a spreading algorithm to "color" faces as long as they are not separated by a constrained edge. Best, Mael On 13/08/18 06:21, Tekel wrote: ```Hello, I've been struggling with this problem for a while now and the information on the documentation and on the mailing list is not really helpful... I want to tryangulate a Fisk Polygon (the one that looks like a crown, used to proof Art Gallery theorem). Or any other non-convex polygon. Like this one: However when I use the Triangulation provieded by CGAL what I get is a triangulation that includes incorrect faces as seen: Whilst the real triangulation is this one: What is the easiest way to avoid having those extra 4 faces? (the ones in the middle of each peak) Thanks in advance -- Sent from: http://cgal-discuss.949826.n4.nabble.com/ ```
Open this post in threaded view
|

## Re: Triangulating non-convex polygon

 Hello and thank you for your concern, last night I gave Constrained triangulations a try and guess what? The 'hardest' part was to obtain each vertex coordinate alone, say, for face 1 i wanted each of the three x's and the three y's by separate so I could write them to a gnu script and plot it. However,  the example for a nested polygon   given on the docs gave one way to access these faces. I used a constrained Delaunay triangulation and gave the vertices of my polygon as constraints. -- Sent from: http://cgal-discuss.949826.n4.nabble.com/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss