# Polygon Triangulation

Actionscript:
1. var triangulate:Triangulate = new Triangulate();
2.
3. var poly:Array=[];
4.
6. function onDown(evt:MouseEvent):void {
7.     poly.push(new Pnt(mouseX, mouseY));
8. }
9.
11. function onLoop(evt:Event):void {
12.     var i:int;
13.     graphics.clear();
14.     var verts:Array=triangulate.process(poly);
15.
16.     if (verts==null) {
17.         // draw a red polygon if there is some kind of error,
18.         // or if there are too few points on the poly
19.         if (poly.length>1) {
20.             graphics.lineStyle(0,0xFF0000);
21.             graphics.moveTo(poly[0].x, poly[0].y);
22.             for (i = 1; i<poly.length; i++) {
23.                 graphics.lineTo(poly[i].x, poly[i].y);
24.             }
25.         }
26.     }else{
27.         // draw the triangulated polygon
28.         var tcount:int = verts.length / 3;
29.         graphics.lineStyle(0,0x000000);
30.         for (i = 0; i<tcount; i++) {
31.             var index:int = i * 3;
32.             var p1:Pnt=verts[index];
33.             var p2:Pnt=verts[index+1];
34.             var p3:Pnt=verts[index+2];
35.             graphics.moveTo(p1.x,p1.y);
36.             graphics.lineTo(p2.x,p2.y);
37.             graphics.lineTo(p3.x,p3.y);
38.             graphics.lineTo(p1.x,p1.y);
39.         }
40.     }
41. }

The above demo's a class that triangulates a polygon given a list of points. To test this snippet you'll need the Pnt and Triangulate Classes, which you can download or copy from below.

Polygon triangulation is useful for lots of things... I first found that I needed it back in my Director days. I wanted to be able to draw a polygon and then extrude it into 3D space - in order to do this I needed to triangulate the polygon that was drawn. Luckily there was an undocumented feature in Lingo that did the triangulation. I'll probably do an extrusion demo soon. I've been looking into this to make the QuickBox2D polygon stuff a little easier.

Take a look at the swf here

Here is the Triangulate class:

Actionscript:
1. /**
2. This code is a quick port of code written in C++ which was submitted to
3. flipcode.com by John W. Ratcliff  // July 22, 2000
5. http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
6.
7. ported to actionscript by Zevan Rosser
8. www.actionsnippet.com
9. */
10.
11. package {
12.
13.     public class Triangulate {
14.
15.         private const EPSILON:Number = 0.0000000001;
16.
17.         public function Triangulate(){}
18.
19.         public function process(contour:Array):Array{
20.             var result:Array = [];
21.             var n:int = contour.length
22.             if ( n <3 ) return null
23.
24.             var verts:Array = [];
25.
26.               /* we want a counter-clockwise polygon in verts */
27.             var v:int
28.
29.               if ( 0.0 <area(contour) ){
30.                 for (v=0; v<n; v++) verts[v] = v;
31.               }else{
32.                 for(v=0; v<n; v++) verts[v] = (n-1)-v;
33.               }
34.
35.               var nv:int = n;
36.
37.               /*  remove nv-2 vertsertices, creating 1 triangle every time */
38.               var count:int = 2*nv;   /* error detection */
39.              var m:int;
40.               for(m=0, v=nv-1; nv>2; )
41.               {
42.                 /* if we loop, it is probably a non-simple polygon */
43.                 if (0>= (count--)){
44.                   //** Triangulate: ERROR - probable bad polygon!
46.                   return null;
47.                 }
48.
49.                 /* three consecutive vertices in current polygon, <u,v,w> */
50.                 var u:int = v; if (nv <= u) u = 0;     /* previous */
51.                 v = u+1; if (nv <= v) v = 0;     /* new v    */
52.                 var w:int = v+1; if (nv <= w) w = 0;     /* next     */
53.
54.                 if ( snip(contour,u,v,w,nv,verts)){
55.                   var a:int,b:int,c:int,s:int,t:int;
56.
57.                   /* true names of the vertices */
58.                   a = verts[u]; b = verts[v]; c = verts[w];
59.
60.                   /* output Triangle */
61.                   result.push( contour[a] );
62.                   result.push( contour[b] );
63.                   result.push( contour[c] );
64.
65.                   m++;
66.
67.                   /* remove v from remaining polygon */
68.                   for(s=v,t=v+1;t<nv;s++,t++) verts[s] = verts[t]; nv--;
69.
70.                   /* resest error detection counter */
71.                   count = 2 * nv;
72.                 }
73.               }
74.
75.               return result;
76.         }
77.
78.         // calculate area of the contour polygon
79.         public function area(contour:Array):Number{
80.             var n:int = contour.length;
81.             var a:Number  = 0.0;
82.
83.             for(var p:int=n-1, q:int=0; q<n; p=q++){
84.                 a += contour[p].x * contour[q].y - contour[q].x * contour[p].y;
85.             }
86.             return a * 0.5;
87.         }
88.
89.         // see if p is inside triangle abc
90.         public function insideTriangle(ax:Number, ay:Number, bx:Number, by:Number, cx:Number, cy:Number,px:Number,py:Number):Boolean{
91.
92.               var aX:Number, aY:Number, bX:Number, bY:Number
93.               var cX:Number, cY:Number, apx:Number, apy:Number;
94.               var bpx:Number, bpy:Number, cpx:Number, cpy:Number;
95.               var cCROSSap:Number, bCROSScp:Number, aCROSSbp:Number;
96.
97.               aX = cx - bx;  aY = cy - by;
98.               bX = ax - cx;  bY = ay - cy;
99.               cX = bx - ax;  cY = by - ay;
100.               apx= px  -ax;  apy= py - ay;
101.               bpx= px - bx;  bpy= py - by;
102.               cpx= px - cx;  cpy= py - cy;
103.
104.               aCROSSbp = aX*bpy - aY*bpx;
105.               cCROSSap = cX*apy - cY*apx;
106.               bCROSScp = bX*cpy - bY*cpx;
107.
108.               return ((aCROSSbp>= 0.0) && (bCROSScp>= 0.0) && (cCROSSap>= 0.0));
109.         }
110.
111.         private function snip(contour:Array, u:int, v:int, w:int, n:int, verts:Array):Boolean{
112.               var p:int;
113.               var ax:Number, ay:Number, bx:Number, by:Number;
114.               var cx:Number, cy:Number, px:Number, py:Number;
115.
116.                   ax = contour[verts[u]].x;
117.                   ay = contour[verts[u]].y;
118.
119.                   bx = contour[verts[v]].x;
120.                   by = contour[verts[v]].y;
121.
122.                   cx = contour[verts[w]].x;
123.                   cy = contour[verts[w]].y;
124.
125.           if ( EPSILON> (((bx-ax)*(cy-ay)) - ((by-ay)*(cx-ax))) ) return false;
126.
127.               for (p=0;p<n;p++){
128.                     if( (p == u) || (p == v) || (p == w) ) continue;
129.                     px = contour[verts[p]].x
130.                     py = contour[verts[p]].y
131.                     if (insideTriangle(ax,ay,bx,by,cx,cy,px,py)) return false;
132.               }
133.               return true;
134.         }
135.     }
136. }

... and the Pnt class:

Actionscript:
1. // Point class, no reason to use AS3's build in Point
2. package{
3.     public class Pnt {
4.         public var x:Number;
5.         public var y:Number;
6.         public function Pnt(x:Number, y:Number){
7.             this.x = x;
8.             this.y = y;
9.         }
10.     }
11. }

I also found a nice description of the basic technique being employed here.

UPDATE:
This should be obvious, but I was targeting fp9 with this... thus the use of Array instead of Vector.

1. Posted May 30, 2009 at 2:41 am | Permalink

when i think about try doing something… next day you just did it! man! you can read my mind! love it! ;D

2. Posted May 30, 2009 at 9:48 am | Permalink

That’s funny You could try creating 3D extruded objects with this - I plan on doing that at some point soon, but probably won’ get around to it for the next few days….

3. Posted June 12, 2009 at 4:26 am | Permalink

hey Zevan , i think we need you on twitter, you already famous there

http://www.sakri.net/blog/2009/06/12/an-approach-to-triangulating-polygons-with-holes/

4. Posted June 12, 2009 at 3:35 pm | Permalink

heh… yeah I have a twitter account but I only use it to follow a bunch of people… so I see all the great links people post there. I may start a twitter where I actually post stuff… not sure… If I decide to start posting I’ll definitely post about it here

5. Sean
Posted June 2, 2010 at 9:36 pm | Permalink

Thanks a ton for this!!

6. Posted January 24, 2011 at 6:07 pm | Permalink

Thank you for the code. It really helped me out when I was trying to draw some concave shapes with box2d - http://chronosign.com/rant/yadurajiv/2011/01/694