/**
   	 @author 	Andreas Weber, webweber@motiondraw.com
   	 @version 	1.0 (March 05, 2005)
   
	 This class provides 2 line gereralization functions:
	 Lang Simplification and McMaster's Slide Averaging Algorithm
	 
	 The purpose and principle of these algorithms are perfectly explained in this tutorial: 
	 http://www.sli.unimelb.edu.au/gisweb/LGmodule/LGSelect.htm (thanks to Jim Cheng for pointing this out)
	 
	
	 simplifyLang	
	 
	 	Parameters
	 	
			 lookAhead:Number
				 Integer between 2 and the number of points in the line minus 1
				 the higher this value:
				 	the better the compression (less points)
				 	the slower (this function is highly recursive)
				 
				 Examples: a lookAhead value of e.g. 5 makes that at least every fifth point of the original line will
				 also be in the resulting, simplified line (a value of 1 would just return the original line)
				 A straight line, consisting of 100 points in a row, is reduced to 2 points if the lookAhead value equals
				 the number of points in the line minus one.
			 
			 tolerance:Number
			 
			 
			 points:Array
			 
		Purpose
			Lang Simplification is a compression algorithm: it reduces the number of points that define a line
			 
			 
	smoothMcMaster
	
		Parameters
			points:Array
	
	
		Purpose
			 Makes the line less edgy  
			 By repeating the smoothing many times, any line will eventually appear as a straight line
			 Does not reduce the number of points (i.e. no compression) 
			 Changes the position of the points (except the first and the last point)   
	 

*/

class com.motiondraw.LineGeneralization{
	
	public function smoothMcMaster(points:Array):Array{
		var nL = [];
		var len = points.length;
		if(len < 5){ return points};
		var j, avX, avY;
		var i = len;
		while(i--){
			if(i==len-1 || i==len-2 || i==1 || i==0){
				nL[i] = {x:points[i].x, y:points[i].y};
			}else{
				j=5;
				avX = 0; avY = 0;
				while(j--){
					avX += points[i+2-j].x; avY += points[i+2-j].y;
				}
				avX = avX/5; avY = avY/5;
				nL[i] = nL[i] = {x:(points[i].x+avX)/2, y:(points[i].y+avY)/2};
			}
		}
		return nL;
	}
	
	public function simplifyLang(lookAhead:Number, tolerance:Number, points:Array):Array{
		if(lookAhead <= 1){return points;};
		var nP:Array = [];
		var offset:Number, len:Number, count:Number;
		len= points.length;
		if(lookAhead > len-1){lookAhead = len-1;};
		nP[0] = {x: points[0].x , y: points[0].y};
		count = 1;
		for(var i=0; i<len; i++){
			if(i+lookAhead > len){lookAhead = len - i -1};
			offset = recursiveToleranceBar(points, i, lookAhead, tolerance);
			if(offset>0){
					nP[count] = {x: points[i+offset].x , y: points[i+offset].y};
					i += offset-1;// don't loop through the skipped points
					count++;
			}
		}
		//nP[count] = {x: points[len-1].x , y: points[len-1].y};
		return nP;
	}
	
	// this function is called by simplifyLang
	private function recursiveToleranceBar(points, i, lookAhead, tolerance):Number{
		
		var n = lookAhead;
		var cP, cLP, v1, v2, angle, dx, dy;
		cP = points[i];// current point
		// the vector through the current point and the max look ahead point
		v1 = {x:points[i+n].x - cP.x, y:points[i+n].y - cP.y};
		// loop through the intermediate points
		for(var j=1; j<=n; j++){
			  // the vector	through the current point and the current intermediate point
			  cLP = points[i+j]; // current look ahead point
			  v2 = {x: cLP.x - cP.x, y:cLP.y - cP.y};
			  angle = Math.acos((v1.x * v2.x + v1.y * v2.y)/(Math.sqrt(v1.y * v1.y + v1.x * v1.x)*Math.sqrt(v2.y * v2.y + v2.x * v2.x)));
			  if(isNaN(angle)){angle = 0;}
			// the hypothenuse is the line between the current point and the current intermediate point
			dx = cP.x - cLP.x; dy = cP.y - cLP.y;
			var lH = Math.sqrt(dx*dx+dy*dy);// lenght of hypothenuse

			// length of opposite leg / perpendicular offset 	
			if( Math.sin(angle) * lH >= tolerance){// too long, exceeds tolerance
				n--;
				if(n>0){// back the vector up one point
					//trace('== recursion, new lookAhead '+n);
					return recursiveToleranceBar(points, i, n, tolerance);
				}else{
					//trace('== return 0, all exceed tolerance');
					return 0;// all intermediate points exceed tolerance
				}
				
			}
		}
		return n;
	}
	
	
	
	// Just a utility, not a Line Gereralization function
	// Adapted from Robert Penner's drawCurve3Pts() method
	
	// Far from perfect for this purpose - we would need a drawCurveNPts()...
	// As Alex Uhlmann says in a comment in his Animation Package:
	/*
	* if anybody finds a generic method to compute control points for bezier curves with n control points, 
	* if only the points on the curve are given, please let me know!
	*/
	public function drawCurveNPts(canvas:MovieClip, points:Array){
			var o1 = curveNPts(points);

			drawCurveArray(canvas, o1);
	}
	
	function getPointsOnQuadCurve(targ:Number, p1:Object, p2:Object, p3:Object):Object {
		var a:Number,b:Number,c:Number;	
		var v:Number = targ / 100;	
		c = v * v;
		a = 1 - v;
		b = a * a;
		var p:Object = {};
		p.x = p1.x * b + 2 * p2.x * a * v + p3.x * c;
		p.y = p1.y * b + 2 * p2.y * a * v + p3.y * c;	
		return p;	
	}
	
	function curveNPts(points:Array){
		var p = points;
		var p0, p1, p2, l1, l2, a, b, c, i, j, k, v;
		var sq = Math.sqrt, po = Math.pow;
		var pp = new Array();
		var pA = new Array();
		var cA = new Array();
		var len = p.length;
		
		if(len < 4){ 
			if(len == 3){
				p0 = p[0]; p1 = p[1]; p2 = p[2];
				return [{x: p0.x, y: p0.y}, {cX: (2 * p1.x) - .5 * (p0.x + p2.x), cY:(2 * p1.y) - .5 * (p0.y + p2.y), aX:p2.x, aY:p2.y}];
			}else if(len == 2){
				p0 = p[0]; p2 = p[1]; p1 = {x: (p0.x + p2.x) / 2 ,y: (p0.y + p2.y) / 2}
				return [{x: p0.x, y: p0.y}, {cX: (2 * p1.x) - .5 * (p0.x + p2.x), cY:(2 * p1.y) - .5 * (p0.y + p2.y), aX:p2.x, aY:p2.y}];
			}else{
				return p;
			}
		}
		
		pp.splice(0, 0, {x: p[0].x, y: p[0].y}, {x: p[1].x, y: p[1].y});
		k = 2;
		for(i = 0; i < len - 3; i++){
			j = 2;
			while(j--){
				p0 = p[i + j]; p1 = p[i + j + 1]; p2 = p[i + j + 2];
				l1 = l2 ? l2 : sq(po(p1.x - p0.x, 2) +  po(p1.y - p0.y, 2));
				l2 = sq(po(p2.x - p1.x, 2) +  po(p2.y - p1.y, 2));
				v = j==0 ?  1 - ((l2 / 2) / ((l1 + l2) / 100) / 100) : ((l1 / 2) / ((l1 + l2) / 100) / 100);
				a = 1 - v; b = a * a; c = v * v;
				pA[j] = {x: p0.x * b + 2 * ((2 * p1.x) - .5 * (p0.x + p2.x)) * a * v + p2.x * c , 
						 y: p0.y * b + 2 * ((2 * p1.y) - .5 * (p0.y + p2.y)) * a * v + p2.y * c}
			}
			pp[k++] = {x: (pA[0].x + pA[1].x) / 2, y: (pA[0].y + pA[1].y) / 2};
			if(i < len - 4){
				pp[k++] = {x: p[i + 2].x, y: p[i + 2].y};
			}
		}	
		pp.splice(k,0,{x: p[len - 2].x, y: p[len - 2].y},{x: p[len - 1].x, y: p[len - 1].y});
		len = k+2;
		k=0;
		for(i = 1; i < len - 1; i += 2){
			p0 = pp[i - 1]; p1 = pp[i]; p2 =  pp[i + 1];
			cA[k++] = {cX: (2 * p1.x) - .5 * (p0.x + p2.x), cY:(2 * p1.y) - .5 * (p0.y + p2.y), aX:p2.x, aY:p2.y};
		}
		cA.unshift(p[0]);
		return cA;
	}
	
	function drawCurveArray(canvas:MovieClip, curves:Array){
		var c;
		canvas.moveTo(curves[0].x, curves[0].y);
		for(var i=1, len=curves.length; i<len; i++){
			c = curves[i];
			canvas.curveTo(c.cX, c.cY, c.aX, c.aY);
		}
	}
	
	
	
	
	
	
	
	
	
	
	function draw3Points(canvas, points){
		var cP, startP, middleP, endP;
		canvas.moveTo(points[0].x, points[0].y);
		for(var i=1, len=points.length-1; i<len; i+=2){
			
			endP =  points[i+1];
			startP = points[i-1];
			middleP = points[i];
			
			cP =  getQuadControlPoints(startP.x, startP.y, middleP.x, middleP.y, endP.x, endP.y);
			canvas.curveTo(cP.x, cP.y, endP.x, endP.y);
		}
		

	}
	
	function getQuadControlPoints(startX:Number, startY:Number, 
						        x2:Number, y2:Number, 
						        endX:Number, endY:Number):Object {
							        
		var c:Object = new Object();
		c.x = (2 * x2) - .5 * (startX + endX);
		c.y = (2 * y2) - .5 * (startY + endY);        
		return c;
	}	
}