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
			addChild(theCanvas);
			// 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.

Download the source code.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers