Sign in to follow this  

Creation of triangular fans out of concave polygons.

This topic is 3490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, i am looking out for an algorithm to create triangular fans out of a simple concave polygon. One option i could think of is looking out for the reflex vertices within the polygon (i.e the vertices that actually make the polygon concave) and then using this as the pivot construct triangular fans. However i do feel this might not be the most efficient way of doing it. Is anyone aware of the other alternatives that i could use... Cheers! Sup

Share this post


Link to post
Share on other sites
A common technique, and your brief description sounds like this is what you plan to do, is called ear-clipping (with the caveat that oliii mentioned). I'll add that you will get better quality triangulations if when testing to see if an ear is an ear....look for ears that are "Delaunay" ears first, e.g., ears for which there is no other point inside the ear's circumcircle rather than ears for which there is no other point inside the ear itself. Only if you cannot find a Delaunay ear should you pick an ear that merely has no points inside the triangle. Er, a figure would help but I never have time to illustrate these ideas adequately. Just trust me, you'll get higher quality tessellations if you do as I suggest. Search on Delaunay and Circumcircle or circumscribed circle and hopefully a web site will pop up that clarifies, if any of this is unfamiliar to you.

Share this post


Link to post
Share on other sites

This topic is 3490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this