Build 10 classic Flash games and learn game development along the way with this ultra-fast paced game development course.

If you love this blog, this is the book for you.

Get the source code of 12 commercial Flash games, which have been loaded more than 50 million times!

Learn from real world successful examples.

Get it now

Box2D for Flash Games teaches you how to make Flash physics games from scratch with the most advanced features.

Create the new Flash game smashing hit.

# Polygon triangulation: decomposition of a polygon into triangles with AS3

In some cases, better said in most cases, dealing with arbitrary polygons is harder than dealing with a given number of triangles forming such polygons. That’s why polygon triangulation, the decomposition of a polygonal area into a set of triangles which may have vertices only at the vertices of the starting polygon, is a must know.

There are several ways to split a polygon into triangles, and in this post I am trying to do the easiest, but also suboptimal way. It’s just the beginning so there’s no need to start with complex concepts at the moment.

When i said “suboptimal”, it’s because of two main reasons:

1) It won’t work with nonsimple polygons (polygons whose edge intersect)

2) It won’t work with polygons with holes

Obviously, during next posts, I will show you how to triangulate any kind of polygon, and above all some practical examples of stuff you can do with triangulation.

At the moment, we will triangulate a polygon following these steps:

1) Find the leftmost vertex

2) Consider the triangle formed by the leftmost vertex, the previous and the next vertices

3) If any of the other vertices is into this triangle, then restart from step 1, finding the next leftmost vertex

4) If no other vertices are inside the triangle, draw the triangle and apply the whole process to the polygon resulting by the starting polygon without the lefmost vertex found

As you can see, it’s a recursive process which can be easily turned into an algorithm, assuming you already know the algorithm to determine if a point is inside a triangle with mathematics.

Here is the script:

And this is the result:

Feel free to change the polygon and share your thoughts.

Rate this post: (5 votes, average: 5.00 out of 5)
Flash Templates provided by Template Monster are pre-made web design products developed using Flash technology.
They can be easily customized to meet the unique requirements of your project.

## This post has 4 comments

1. ### Wilson Silva

on June 28, 2012 at 7:19 pm

I have needed this algorithm some months ago, but I since I was short on time, and didn’t find a proper way to do this, I decided to drop the feature I was developing. Now I’m coding the next release of the same solution and this code will be very, very handy. Many thanks :D

2. ### Paolo Di Stefano

on June 28, 2012 at 7:36 pm

Grazie! And good work with the low linecount too!

3. ### Rinalds

on July 15, 2012 at 12:43 pm

Is this method of collision detection faster then Seperaring Axis Theorem?

on March 20, 2013 at 5:46 am

I don’t think this algorithm works for all simple polygons.
Don’t have flash installed atm, so I can’t test it though.
Could someone try running it with the the following vertices (assuming 0,0 is bottom left):
– x , y
A: 0 , 0
B: 50,100
C: 45,50
D: 60,60
E:200,40
This is what I assume should happen:
ABE is tested and found to be invalid.
A is discarded, next leftmost point is C.
BCD is tested and found to be valid and drawn.
This is wrong. Drawing BCD would be mean drawing a line between B and D which is outside of the polygon.

I might be missing something but that’s what it looks like to me. Could someone either correct me or point me to a fix for this problem?