Jump to content
  • Advertisement
Sign in to follow this  
supriya

Creation of triangular fans out of concave polygons.

This topic is 3706 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
Advertisement
I've had a quick look. Granted you do not have a self-intersecting polygon, that sounds like a sensible solution.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!