Delaunay.ts

/// <reference path="defs/easeljs.d.ts" />

module djankey {
    export class Delaunay extends createjs.Shape {
        public EPSILON:number = Number.MIN_VALUE;
        public SUPER_TRIANGLE_RADIUS:number = 1000000000;
        private indices:Array<number>;
        private circles:Array<number>;
        private g:createjs.Graphics;

        constructor() {
            super();
        }

        public compute = (points:Array<createjs.Point>):Array<number> => {
            var nv:number = points.length;
            if (nv < 3) return null;

            var d:number = this.SUPER_TRIANGLE_RADIUS;
            points.push(new createjs.Point( 0, -d ), new createjs.Point( d, d ), new createjs.Point( -d, d ));

            this.indices = [ points.length-3, points.length-2, points.length-1 ];
            this.circles = [ 0, 0, d ];

            var edgeIds:Array<number> = [];
            var i:number, j:number, k:number, id0:number, id1:number, id2:number;
            for ( i = 0; i < nv; i++)
            {
                for ( j = 0; j < this.indices.length; j+=3 )
                {
                    if (this.circles[ j + 2 ] > this.EPSILON && this.circleContains(j, points[ i ]))
                    {
                        id0 = this.indices[ j ];
                        id1 = this.indices[ j + 1 ];
                        id2 = this.indices[ j + 2 ];
                        edgeIds.push( id0, id1, id1, id2, id2, id0 );
                        this.indices.splice( j, 3 );
                        this.circles.splice( j, 3 );
                        j -= 3;
                    }
                }
                for ( j = 0; j < edgeIds.length; j+=2 )
                {
                    for ( k = j + 2; k < edgeIds.length; k+=2 )
                    {
                        if( (edgeIds[ j ] == edgeIds[ k ] && edgeIds[ j + 1 ] == edgeIds[ k + 1 ]   )
                            ||  (edgeIds[ j + 1 ] == edgeIds[ k ] && edgeIds[ j ] == edgeIds[ k + 1 ]   )   )
                        {
                            edgeIds.splice( k, 2 );
                            edgeIds.splice( j, 2 );
                            j -= 2;
                            k -= 2;
                            if ( j < 0 ) break;
                            if ( k < 0 ) break;
                        }
                    }
                }
                for ( j = 0; j < edgeIds.length; j+=2 )
                {
                    this.indices.push( edgeIds[ j ], edgeIds[ j + 1 ], i );
                    this.computeCircle( points, edgeIds[ j ], edgeIds[ j + 1 ], i );
                }
                edgeIds.length = 0;

            }
            id0 = points.length - 3;
            id1 = points.length - 2;
            id2 = points.length - 1;
            for ( i = 0; i < this.indices.length; i+= 3 )
            {
                if ( this.indices[ i ] == id0 || this.indices[ i ] == id1 || this.indices[ i ] == id2
                    ||   this.indices[ i + 1 ] == id0 || this.indices[ i + 1 ] == id1 || this.indices[ i + 1 ] == id2
                    ||   this.indices[ i + 2 ] == id0 || this.indices[ i + 2 ] == id1 || this.indices[ i + 2 ] == id2 )
                {
                    this.indices.splice( i, 3 );
                    i-=3;
                    continue;
                }
            }
            points.pop();
            points.pop();
            points.pop();
            return this.indices;
        }

        circleContains = ( circleId:number, p:createjs.Point ):boolean => {
            var dx:number = this.circles[ circleId ] - p.x;
            var dy:number = this.circles[ circleId + 1 ] - p.y;
            return this.circles[ circleId + 2 ] > dx * dx + dy * dy;
        }

        computeCircle = ( points:Array<createjs.Point>, id0:number, id1:number, id2:number ):void => {
            var p0:createjs.Point = points[ id0 ];
            var p1:createjs.Point = points[ id1 ];
            var p2:createjs.Point = points[ id2 ];
            var A:number = p1.x - p0.x;
            var B:number = p1.y - p0.y;
            var C:number = p2.x - p0.x;
            var D:number = p2.y - p0.y;
            var E:number = A * (p0.x + p1.x) + B * (p0.y + p1.y);
            var F:number = C * (p0.x + p2.x) + D * (p0.y + p2.y);
            var G:number = 2.0 * (A * (p2.y - p1.y) - B * (p2.x - p1.x));
            var x:number = (D * E - B * F) / G;
            this.circles.push( x );
            var y:number = (A * F - C * E) / G;
            this.circles.push( y );
            x -= p0.x;
            y -= p0.y;
            this.circles.push( x * x + y * y );
        }

        public render = ( graphics:createjs.Graphics, points:Array<createjs.Point>, indices:Array<number> = [] ):void => {
            var id0:number, id1:number, id2:number;
            for ( var i:number = 0; i < indices.length; i+=3 )
            {
                id0 = indices[ i ];
                id1 = indices[ i + 1 ];
                id2 = indices[ i + 2 ];
                graphics.moveTo( points[ id0 ].x, points[ id0 ].y );
                graphics.lineTo( points[ id1 ].x, points[ id1 ].y );
                graphics.lineTo( points[ id2 ].x, points[ id2 ].y );
                graphics.lineTo( points[ id0 ].x, points[ id0 ].y );
            }
        }
    }
}