flash on 2012-7-25

/**
 * Copyright Joao.Paulo.Marquesini ( http://wonderfl.net/user/Joao.Paulo.Marquesini )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/xGR9
 */

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.<Point>=new Vector.<Point>();
        // discardedPoints is the vector of indexes of leftmost points discarded because the triangle includes other vertices
        private var discardedPoints:Vector.<int>=new Vector.<int>();
        // 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<thePoly.length; i++) {
                if (i!=triangleA && i!=triangleB && i!=triangleC) {
                    if (isInsideTriangle(thePoly[triangleA],thePoly[triangleB],thePoly[triangleC],thePoly[i])) {
                        // if one vertex is inside the triangle, we discard the leftmost point just found
                        discardedPoints.push(triangleA);
                        // then we set success variable to false
                        success = false;
                        break;
                    }
                }
            }
            if (success) {
                // if we have just found a valid triangle, we draw it
                drawTriangle(triangleA,triangleB,triangleC);
                // then we remove the leftmost point found from the polygon, obtaining a smaller polygon
                thePoly.splice(triangleA,1);
                // we also clear the vector of discarded points
                discardedPoints=new Vector.<int>();
            }
            // 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(100,0));
            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(300,50));
            thePoly.push(new Point(220,340));
            thePoly.push(new Point(100,240));
            thePoly.push(new Point(200,200));
        }
        // 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<thePoly.length; i++) {
                theCanvas.graphics.lineTo(thePoly[i].x,thePoly[i].y);
            }
            theCanvas.graphics.lineTo(thePoly[0].x,thePoly[0].y);
        }
        // and this function just draws a triangle
        private function drawTriangle(a:int,b:int,c:int):void {
            theCanvas.graphics.lineStyle(1,0xff0000);
            theCanvas.graphics.moveTo(thePoly[a].x,thePoly[a].y);
            theCanvas.graphics.lineTo(thePoly[b].x,thePoly[b].y);
            theCanvas.graphics.lineTo(thePoly[c].x,thePoly[c].y);
            theCanvas.graphics.lineTo(thePoly[a].x,thePoly[a].y);
        }
        // function to find the leftmost point
        private function leftmostPoint():int {
            // first, I look for the first undiscarded point
            for (var i:int=0; i<thePoly.length; i++) {
                if (discardedPoints.indexOf(i) == -1) {
                    var minIndex:int = i;
                    break;
                }
            }
            // then I check for all undiscarded points to find the one with the lowest x value (the leftmost)
            for (i=0; i<thePoly.length; i++) {
                if (discardedPoints.indexOf(i) == -1 && thePoly[i].x < thePoly[minIndex].x) {
                    minIndex = i;
                }
            }
            return minIndex;
        }
        // these two functions have already been explained in the post "Algorithm to determine if a point is inside a triangle with mathematics (no hit test involved)"
        private function isInsideTriangle(A:Point,B:Point,C:Point,P:Point):Boolean {
            var planeAB:Number = (A.x-P.x)*(B.y-P.y)-(B.x-P.x)*(A.y-P.y);
            var planeBC:Number = (B.x-P.x)*(C.y-P.y)-(C.x - P.x)*(B.y-P.y);
            var planeCA:Number = (C.x-P.x)*(A.y-P.y)-(A.x - P.x)*(C.y-P.y);
            return sign(planeAB)==sign(planeBC) && sign(planeBC)==sign(planeCA);
        }
        private function sign(n:Number):int {
            return Math.abs(n)/n;
        }
    }
}