Triangulation of polygons with holes: poly2tri class

Talking about Actionscript 3 and Flash.

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.addRectangle(0, 0, 640, 480);
			polygon.drawShape(this.graphics);
			stage.addEventListener(MouseEvent.CLICK,doHole);
		}
		private function doHole(e:MouseEvent):void {
			polygonHoles.push(new Point(mouseX,mouseY));
			graphics.clear();
			polygon.reset();
			polygon.addRectangle(0, 0, 640, 480);
			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.addHole(holeVector);
			}
			polygon.drawShape(graphics);
		}
	}
}

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

Download the source code and give it a try.