convexhull2d.as

flex3d 的源码

/**
* project3D Engine
* @author John Sword
* @version 2 - AS3
*/

package engine.geom
{
	import flash.display.Graphics;

    public class convexHull2D
    {
    	
        public var screenZ:Number;
		public var H:Array = [];
		public var k:int = 10; // the approximation accuracy (large k = more accurate)
		
		private static var cP:Vector; // the current point being considered
		
		/*
		public var minX:int;
        public var maxX:int;
        public var minY:int;
        public var maxY:int;
        public var minZ:int;
        public var maxZ:int;
        public var boundlines:Array = [];
		*/
        public function convexHull2D ()
        
        public function build ( P:Array ) : int
        {
        	var n:int = P.length;
        	
        	if ( n < 3 ) return 0;
        	
            // the output array H[] will be used as the stack
		    var bot:int=0, top:int=(-1),  // indices for bottom and top of the stack
		    i:int;                // array scan index
		    
		    // Get the indices of points with min x-coord and min|max y-coord
		    var minmin:int = 0, minmax:int, xmin:int = P[0].x;
		    for (i=1; i<n; i++) {
		        if (P[i].x != xmin) break;
			    minmax = i-1;
			    if (minmax == n-1) {       // degenerate case: all x-coords == xmin
			        H[++top] = P[minmin];
			        if (P[minmax].y != P[minmin].y) // a nontrivial segment
			            H[++top] = P[minmax];
			        H[++top] = P[minmin];           // add polygon endpoint
			        return top+1;
			    }
		    }
		    
		    // Get the indices of points with max x-coord and min|max y-coord
		    var maxmin:int, maxmax:int = n-1,  xmax:int = P[n-1].x;
		    for (i=n-2; i>=0; i--) {
		        if (P[i].x != xmax) break;
		    	maxmin = i+1;
		    }
		    
		    // Compute the lower hull on the stack H
		    H[++top] = P[minmin];      // push minmin point onto stack
		    i = minmax;
		    while (++i <= maxmin)
		    {
		        // the lower line joins P[minmin] with P[maxmin]
		        if (isLeft( P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)
		            continue;          // ignore P[i] above or on the lower line
		
		        while (top > 0)        // there are at least 2 points on the stack
		        {
		            // test if P[i] is left of the line at the stack top
		            if (isLeft( H[top-1], H[top], P[i]) > 0)
		                break;         // P[i] is a new hull vertex
		            else
		                top--;         // pop top point off stack
		        }
		        H[++top] = P[i];       // push P[i] onto stack
		    }
		    
		    // Next, compute the upper hull on the stack H above the bottom hull
		    if (maxmax != maxmin)      // if distinct xmax points
		        H[++top] = P[maxmax];  // push maxmax point onto stack
		    
		    bot = top;                 // the bottom point of the upper hull stack
		    i = maxmin;
		    
		    while (--i >= minmax)
		    {
		        // the upper line joins P[maxmax] with P[minmax]
		        if (isLeft( P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)
		            continue;          // ignore P[i] below or on the upper line
		
		        while (top > bot)    // at least 2 points on the upper stack
		        {
		            // test if P[i] is left of the line at the stack top
		            if (isLeft( H[top-1], H[top], P[i]) > 0)
		                break;         // P[i] is a new hull vertex
		            else
		                top--;         // pop top point off stack
		        }
		        H[++top] = P[i];       // push P[i] onto stack
		    }
		    if (minmax != minmin)
		        H[++top] = P[minmin];  // push joining endpoint onto stack
		    
		    return top+1;
        }

		public function buildApproximate ( P:Array ) : int
		{
			
			var n:int = P.length, i:int, b:int,
			minmin:int=0,  minmax:int=0,
		    maxmin:int=0,  maxmax:int=0,
		    xmin:int = P[0].screen.x,  xmax:int = P[0].screen.x,
		    bot:int=0, top:int=(-1);  // indices for bottom and top of the stack
		    //var cP:Vector;                 // the current point being considered

		    if ( n < 3 ) return 0;
	
		    // Get the points with (1) min-max x-coord, and (2) min-max y-coord
		    for (i=1; i<n; i++) {
		        cP = P[i].screen;
		        if (cP.x <= xmin) {
		            if (cP.x < xmin) {        // new xmin
		                xmin = cP.x;
		                minmin = minmax = i;
		            }
		            else {                      // another xmin
		                if (cP.y < P[minmin].screen.y)
		                    minmin = i;
		                else if (cP.y > P[minmax].screen.y)
		                    minmax = i;
		            }
		        }
		        if (cP.x >= xmax) {
		            if (cP.x > xmax) {        // new xmax
		                xmax = cP.x;
		                maxmin = maxmax = i;
		            }
		            else {                      // another xmax
		                if (cP.y < P[maxmin].screen.y)
		                    maxmin = i;
		                else if (cP.y > P[maxmax].screen.y)
		                    maxmax = i;
		            }
		        }

		    }
		    
		    if (xmin == xmax) {      // degenerate case: all x-coords == xmin
		        H[++top] = P[minmin].screen;           // a point, or
		        if (minmax != minmin)           // a nontrivial segment
		            H[++top] = P[minmax].screen;
		        return top+1;                   // one or two points
		    }
		    
		    // Next, get the max and min points in the k range bins
		    var B:Array = new Array();   // first allocate the bins
		    B[0] = new Object();
		    B[0].min = minmin; B[0].max = minmax;        // set bin 0
		    B[k+1] = new Object();
		    B[k+1].min = maxmin; B[k+1].max = maxmax;      // set bin k+1
		    for (b=1; b<=k; b++) { // initially nothing is in the other bins
		    	B[b] = new Object();
		        B[b].min = B[b].max = null;
		    }
		    
		    for (b, i=0; i<n; i++) {
		        cP = P[i].screen;
		        if (cP.x == xmin || cP.x == xmax) // already have bins 0 and k+1 
		            continue;
		        // check if a lower or upper point
		        if (isLeft( P[minmin].screen, P[maxmin].screen, cP) < 0) {  // below lower line
		            b = int(( k * (cP.x - xmin) / (xmax - xmin) ) + 1);  // bin #
		            if (B[b].min == null)       // no min point in this range
		                B[b].min = i;           // first min
		            else if (cP.y < P[B[b].min].screen.y)
		                B[b].min = i;           // new min
		            continue;
		        }
		        if (isLeft( P[minmax].screen, P[maxmax].screen, cP) > 0) {  // above upper line
		            b = int((k * (cP.x - xmin) / (xmax - xmin) ) + 1);  // bin #
		            if (B[b].max == null)       // no max point in this range
		                B[b].max = i;           // first max
		            else if (cP.y > P[B[b].max].screen.y)
		                B[b].max = i;           // new max
		            continue;
		        }
		    }
		    
		    // Now, use the chain algorithm to get the lower and upper hulls
		    // the output array H[] will be used as the stack
		    // First, compute the lower hull on the stack H
		    for (i=0; i <= k+1; ++i)
		    {
		        if (B[i].min == null)  // no min point in this range
		            continue;
		        cP = P[ B[i].min ].screen;   // select the current min point
		
		        while (top > 0)        // there are at least 2 points on the stack
		        {
		            // test if current point is left of the line at the stack top
		            if (isLeft( H[top-1], H[top], cP) > 0)
		                break;         // cP is a new hull vertex
		            else
		                top--;         // pop top point off stack
		        }
		        H[++top] = cP;        // push current point onto stack
		    }
		    
		    // Next, compute the upper hull on the stack H above the bottom hull
		    if (maxmax != maxmin)      // if distinct xmax points
		        H[++top] = P[maxmax].screen;  // push maxmax point onto stack
		    
		    bot = top;                 // the bottom point of the upper hull stack
		    
		    for (i=k; i >= 0; --i)
		    {
		        if (B[i].max == null)  // no max point in this range
		            continue;
		        cP = P[ B[i].max ].screen;   // select the current max point
		
		        while (top > bot)      // at least 2 points on the upper stack
		        {
		            // test if current point is left of the line at the stack top
		            if (isLeft( H[top-1], H[top], cP) > 0)
		                break;         // current point is a new hull vertex
		            else
		                top--;         // pop top point off stack
		        }
		        H[++top] = cP;        // push current point onto stack
		    }
		    
		    if (minmax != minmin)
		        H[++top] = P[minmin].screen;  // push joining endpoint onto stack
		
		    return top+1;              // # of points on the stack

		}

		public function contains ( x:int, y:int ) : Boolean
        {   
		  	var hlen:int = H.length;
		  	if (hlen < 3) return false;
		  	var p3:Vector = new Vector(x,y,0);
		  	var i:int,t:int;
		  	for (i = 0; i < hlen; i++)
            {
            	t = isLeft( H[i],H[(i+1)%hlen],p3 );
            	if ( t < 0 ) return false;
            }
            return true;
        }
        
        public function render ( g:Graphics ) : void
        {
        	var hlen:int = H.length;
        	if (hlen < 3) return;
        	var v:Vector = H[0];
			g.lineStyle( 5, 0xFF0000, 1);
			g.moveTo( v.x,v.y );
			for (var i:int = 1; i < hlen; i++)
            {
                v = H[i];
                g.lineTo(v.x, v.y);
            }
            g.lineStyle();
        }
/*
		public function fromScreenCoords ( P:Array ) : Array
		{
			var Q:Array = [];
			var i:Vertex;
			var v:Vector,b:Vector;
			for each ( i in P )
			{
				if ( i.visible )
				{
					v = i.screen;
					Q.push( v );
				}
				
			}
			/*
			for each ( i in P )
			{
				if ( i.visible )
				{
					v = i.screen;
					Q.push( v );
					if (!b)
						b = v
					else
		                if (b.y < v.y)
	                    b = v;
		                else
		                if (b.y == v.y)
		                    if (b.x < v.x)
		                        b = v;
				}
				
			}
			
			var xx:int,yy:int;
			for each (v in Q)
			{
				xx = (v.x - b.x);
				yy = (v.y - b.y);
				if ( xx && yy ) v.num = xx / yy;
				else v.num = 0;
			}
                
            Q.sortOn("num", Array.NUMERIC);
			return Q;
		}
*/
		private function isLeft ( P0:Vector, P1:Vector, P2:Vector ) : Number
		{
		    return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
		}

    }

}