Triangulating non-convex polygon

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Triangulating non-convex polygon

Tekel
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:
<http://cgal-discuss.949826.n4.nabble.com/file/t376023/polygon.png>

However when I use the Triangulation provieded by   CGAL what I get is a
triangulation that includes incorrect faces as seen:

<http://cgal-discuss.949826.n4.nabble.com/file/t376023/tpolygon.png>

Whilst the real triangulation is this one:
<http://cgal-discuss.949826.n4.nabble.com/file/t376023/geogebra-export.png>

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


Reply | Threaded
Open this post in threaded view
|

Re: Triangulating non-convex polygon

MaelRL

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:
<http://cgal-discuss.949826.n4.nabble.com/file/t376023/polygon.png> 

However when I use the Triangulation provieded by   CGAL what I get is a
triangulation that includes incorrect faces as seen:

<http://cgal-discuss.949826.n4.nabble.com/file/t376023/tpolygon.png> 

Whilst the real triangulation is this one:
<http://cgal-discuss.949826.n4.nabble.com/file/t376023/geogebra-export.png> 

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/


Reply | Threaded
Open this post in threaded view
|

Re: Triangulating non-convex polygon

Tekel
Hello and thank you for your concern, last night I gave Constrained
triangulations a try and guess what?
<http://cgal-discuss.949826.n4.nabble.com/file/t376023/tpolygon.png>

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
<https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2polygon_triangulation_8cpp-example.html>  
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