# 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:

```package {
import flash.display.Sprite;
import flash.geom.Point;
public class Main extends Sprite {
// thePoly is the vector of points making the polygon. They must be in clockwise or counter-clockwise order
private var thePoly:Vector.=new Vector.();
// discardedPoints is the vector of indexes of leftmost points discarded because the triangle includes other vertices
private var discardedPoints:Vector.=new Vector.();
// theCanvas is just the sprite where we will draw the polygon and the triangles
private var theCanvas:Sprite=new Sprite();
public function Main() {
// adding the sprite where to draw
// definePoly function pushes polygon points into thePoly vector
definePoly();
// drawPoly function just draws the polygon on theCanvas sprite
drawPoly();
// triangulate is the core of the script, the recursive function which triangulates the polygon
triangulate();
}
private function triangulate():void {
// success is a Boolean variable which will say if we found a valid triangle
var success:Boolean = true;
// triangleA is the leftmost vertex of the polygon, according to discarded points
var triangleA:int = leftmostPoint();
// triangleB is next vertex
var triangleB:int = (triangleA + 1) % thePoly.length;
// triangleC is previous vertex so in the end we have a triangle
var triangleC:int = (triangleA - 1);
if (triangleC<0) {
triangleC = thePoly.length - 1;
}
// now it's time to see if any of the remaining vertices is inside the triangle
for (var i:int=0; i();
}
// if there are still more than three points in the polygon (it's not a triangle) then execute triangulate function once more
if (thePoly.length > 3) {
triangulate();
}
else {
// otherwise draw the remaining triangle
drawTriangle(0,1,2);
}
}
// here points are pushed into the polygon
private function definePoly():void {
thePoly.push(new Point(220,140));
thePoly.push(new Point(420,140));
thePoly.push(new Point(420,340));
thePoly.push(new Point(320,210));
thePoly.push(new Point(220,340));
thePoly.push(new Point(100,240));
}
// this function just draws a polygon
private function drawPoly():void {
theCanvas.graphics.lineStyle(5,0x000000);
theCanvas.graphics.moveTo(thePoly[0].x,thePoly[0].y);
for (var i:int=1; i
And this is the result:

Feel free to change the polygon and share your thoughts.
```
215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 10000000
// 2 Cars
// 2048
// Avoider
// Ballz
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Breakout
// Bricks
// Columns
// CubesOut
// Dots
// DROP'd
// Dudeski
// Eskiv
// Filler
// Fling
// Globe
// HookPod
// Hundreds
// InkTd
// Iromeku
// Lumines
// Magick
// MagOrMin
// Maze
// Memdot
// Nano War
// Nodes
// o:anquan
// Ononmin
// Pacco
// Phyballs
// Platform
// Poker
// Pool
// Poux
// Pudi
// qomp
// Racing
// Renju
// SameGame
// Security
// Sling
// Slingy
// Sokoban
// Splitter
// Sproing
// Stack
// Stairs
// Stringy
// Sudoku
// Tetris
// Threes
// Toony
// Turn
// TwinSpin
// vvvvvv
// Wordle
// Worms
// Yanga
// Zhed
// zNumbers