Convex Polygon Triangulation

Hey all!

I was recently looking around, for a library to do polygon triangulation. I found some great ones, LibTess, Triangle, etc. but they were all a bit heavier than what I needed. I was just intending to do convex polygons, so I figured I could get away with less code to clutter up my folders.

I found an article on GameDev.net that struck my fancy. This article provided two simple examples, the ‘Triangle Soup’ method of making triangles from one point and then dividing them up from there. This mode is easy and simple, but as one commentor suggested, that it does not always make well formed triangles.

Convex


Following this suggestion I took a few minutes to modify the basic algorithm into the suggested method of adding a new central point to the polygon and fanning the polygons out from that as the central base. This method makes nice well formed triangles, but adds more of them than the ‘soup’ method.

Convex1


Hopefully someone out there will find this useful, as I needed it for a project. I have included the simple source example for you to do what you will with. 🙂

Download Sample .EXE and Source file

Convex2

Keep in mind the code is just quick and dirty as it was basically a test so there’s no “professional” coding scheme just basic conventions and trying to get it coded up as quickly as possible so it may be a little hackey, but hey it’s a nice learning example and maybe can help some people out as I did not see very many if any at all examples of simple Convex Polygon Triangulation. It’s not meant to do any damage, but I am not liable for any, and use at your own risk.

Enjoy!
-Jinroh.

Leave a Reply

Your email address will not be published. Required fields are marked *