# Triangulation of polygons with holes: poly2tri class

I am always been very interested in a solid script to handle triangulation of polygons with holes, because it’s the first step to the generation of a physics destructible terrain with Box2D, something I always wanted to do.

Some time ago I published my attempt to triangulate a polygon but my script did not handle holes.

Now I found a 2D constrained Delaunay triangulation library called poly2tri originally written in C++ and Java but already ported in AS3 which seems to work with holes.

At the moment it needs some changes to perfectly fit to my needs, but it’s a great start to achieve my destructible terrain.

Look at this script:

We have a square as big as the stage, divided into two triangles. Try to click with the mouse inside to create a square hole and see the computed triangulation.

There is no limit to the amount of holes you can do, as long as a hole:

1) is entirely inside the big square

2) does not overlap any other hole

These two points are the ones I am working on now, meanwhile here is the script I made:

package {
import flash.display.Sprite;
import flash.events.MouseEvent;
import org.poly2tri.VisiblePolygon;
import org.poly2tri.Point;
public class Main extends Sprite {
private var polygon:VisiblePolygon = new VisiblePolygon();
private var polygonHoles:Vector.<Point>=new Vector.<Point>();
public function Main() {
polygon.reset();
polygon.drawShape(this.graphics);
}
private function doHole(e:MouseEvent):void {
polygonHoles.push(new Point(mouseX,mouseY));
graphics.clear();
polygon.reset();
for (var i:Number=0; i<polygonHoles.length; i++) {
var holeVector:Vector.<Point>=new Vector.<Point>();
holeVector.push(new Point(polygonHoles[i].x-10,polygonHoles[i].y-10));
holeVector.push(new Point(polygonHoles[i].x+10,polygonHoles[i].y-10));
holeVector.push(new Point(polygonHoles[i].x+10,polygonHoles[i].y+10));
holeVector.push(new Point(polygonHoles[i].x-10,polygonHoles[i].y+10));
}
polygon.drawShape(graphics);
}
}
}

As you can see, it’s just a matter of addRectangle and addHole methods provided by VisiblePolygon class.

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