/*
City of Saint Paul Open Source License

LICENSE

Copyright © 2006 City of Saint Paul, Minnesota. 

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following terms and conditions:

1.The above copyright notice and this permission notice shall be included in all copies of this Software or works derived from this Software.
2.Whenever a Recipient distributes or redistributes the Software, a copy of this agreement must be included with each copy of the Software
3.If Recipient distributes or redistributes the Software in any form other than source code, Recipient must also make the source code freely available, and must provide with each copy of the Software information on how to obtain the source code in a reasonable manner on or through a medium customarily used for software exchange
4.A Recipient may not make any representation in the Software or in any promotional, advertising or other material that may be construed as an endorsement by the City of Saint Paul of any product or service provided by Recipient, or that may seek to obtain commercial advantage by the fact of the City of Saint Paul’s participation in this Agreement.

DISCLAIMER OF WARRANTIES AND LIABILITIES; WAIVER AND INDEMNIFICATION

No Warranty:  The Software is provided “as is” without any warranty of any kind, either expressed, implied, or statutory, including, but not limited to, any warranty that the Software will conform to specifications, any implied warranties of merchantability, fitness for a particular purpose, or freedom from infringement, any warranty that the Software will be error free, or any warranty that documentation, if provided, will conform to the Software. This agreement does not, in any manner, constitute an endorsement by the City of Saint Paul or any prior recipient of any results, resulting designs, hardware, software products or any other applications resulting from use of the Software. Further, the City of Saint Paul disclaims all warranties and liabilities regarding third-party software, if present in the original Software, and distributes it “as is.”

Waiver and Indemnity:  Recipient agrees to waive any and all claims against the City of Saint Paul, its contractors and subcontractors, as well as any prior recipient.  If recipient's use of the Software results in any liabilities, demands, damages, expenses or losses arising from such use, including any damages from products based on, or resulting from, recipient's use of the Software, recipient shall indemnify and hold harmless the City of Saint Paul, it’s contractors and subcontractors, as well as any prior recipient, to the extent permitted by law. Recipient's sole remedy for any such matter shall be the immediate, unilateral termination of this agreement.

SUPPORT STATEMENT 

The Software is freely provided by the City of Saint Paul as a public service.  The recipient is herby notified that the provision and distribution of the Software should in no way be construed to mean that the City of Saint Paul is obligated to provide any level of support for the Software, now or in the future.  Support in this context shall be construed to mean providing coordination, technical assistance, responding to questions, releasing bug fixes, providing future releases, or otherwise obligating the City of Saint Paul to commit resources to maintain this Software or assist in its implementation by any person or entity.  The City of Saint Paul may, at it’s sole option, and without notice or obligation to the recipients, provide varying levels of support for the Software or terminate the agreement.  Provision of such support shall not alter the condition that the Software is provided without support as stated above.
*/

function Point(x, y) {
	this.x = x;
	this.y = y;

	this.type = 'point';
	
	this.fromString = function(str,delim) {
		var arr = str.split(delim);
		this.x = parseFloat(arr[0]);
		this.y = parseFloat(arr[1]);
	}

	this.toString = function(delim) {
		return this.x+delim+this.y;
	}

	this.equals = function(otherPoint) {
		return(this.x == otherPoint.x && this.y == otherPoint.y);
	}

	this.scale = function(s) {
		this.x = this.x * s;
		this.y = this.y * s;
	}

	this.clean = function() {
		this.x = parseFloat(this.x);
		this.y = parseFloat(this.y);
	}

	this.buffer = function(rad) {
		var newCirc = new Circle();
		newCirc.Center = new Point(this.x, this.y);
		newCirc.Radius = rad;
		return newCirc;
	}


	this.minX = function() {
		return x;
	}
	this.maxX = function() {
		return x;
	}

	this.minY = function() {
		return y;
	}

	this.maxY = function() {
		return y;
	}
}

function LineSegment(PointA, PointB) {
	this.pointA = PointA;
	this.pointB = PointB;

	this.type = 'line';
	
	this.slope = function() {
		return ((this.pointA.y - this.pointB.y) / (this.pointA.x - this.pointB.x));
	}

	this.eval = function(x) {
		if((x - this.pointA.x) == 0) { return this.pointA.y; }
		if((x - this.pointB.x) == 0) { return this.pointB.y; }
		return (this.slope() * (x - this.pointA.x) + this.pointA.y);
	}

	this.evalA = function () {
		return this.eval(this.pointA.x);
	}

	this.evalB = function () {
		return this.eval(this.pointB.x);
	}

	function returnGreater(A, B) {
		if(A > B) return A;
		return B;
	}

	function returnLesser(A, B) {
		if(A < B) return A;
		return B;
	}

	this.normalize = function() {
		if(this.pointA.x > this.pointB.x) {
			var t = this.pointA.x;
			this.pointA.x = this.pointB.x;
			this.pointB.x = t;
		}
		if(this.pointA.y > this.pointB.y) {
			var t = this.pointA.y;
			this.pointA.y = this.pointB.y;
			this.pointB.y = t;
		}

	}

	this.getLength = function() {
		if((this.pointA.x - this.pointB.x) == 0) { return this.maxY() - this.minY(); }
		if((this.pointA.y - this.pointB.y) == 0) { return this.maxX() - this.minX(); }
		return (Math.sqrt(Math.pow(this.getWidth(),2) + Math.pow(this.getHeight(),2)));
	}

	this.minX = function () {
		return returnLesser(this.pointA.x, this.pointB.x);
	}

	this.maxX = function () {
		return returnGreater(this.pointA.x, this.pointB.x);		
	}

	this.minY = function () {
		return returnLesser(this.pointA.y, this.pointB.y);
	}

	this.maxY = function () {
		return returnGreater(this.pointA.y, this.pointB.y);		
	}


	this.getWidth = function() {
		return this.maxX() - this.minX();
	}

	this.getHeight = function() {
		return this.maxY() - this.minY();
	}

	this.shift = function(x,y) {
		this.pointA.x = parseInt(this.pointA.x);
		this.pointA.y = parseInt(this.pointA.y);
		this.pointB.x = parseInt(this.pointB.x);
		this.pointB.y = parseInt(this.pointB.y);
		this.pointA.x += x;
		this.pointB.x += x;
		this.pointA.y += y;
		this.pointB.y += y;
	}

	this.scale = function(x, y) {
		this.pointA.x = this.pointA.x * x;
		this.pointA.y = this.pointA.y * y;
		this.pointB.x = this.pointB.x * x;
		this.pointB.y = this.pointB.y * y;
	}

	this.getMidPoint = function() {
		var oldMidX = (this.pointA.x + this.pointB.x) / 2;
		var oldMidY = this.eval(oldMidX);
		return new Point(oldMidX, oldMidY);
	}

	this.shiftMidPoint = function(newMidPoint) {
		var oldMidPoint = this.getMidPoint();
		this.shift(oldMidPoint.x-newMidPoint.x, oldMidPoint.y-newMidPoint.y);
	}

	this.getScaledPoint = function(fromLine, fromPoint) {
		var scaledPoint = new Point();
		scaledPoint.x = fromLine.getWidth() / (fromPoint.x - fromLine.minX());
		scaledPoint.x = (this.getWidth() / scaledPoint.x) + this.minX();
		scaledPoint.y = fromLine.getHeight() / (fromPoint.y - fromLine.minY());
		scaledPoint.y = (this.getHeight() / scaledPoint.y) + this.minY();
		return scaledPoint;
	}

	this.scaleAboutMidPoint = function(scale) {
		var oldMidPoint = this.getMidPoint();	
		this.scale(scale,scale);
		var newMidPoint = this.getMidPoint();
		this.shift((oldMidPoint.x-newMidPoint.x), oldMidPoint.y-newMidPoint.y);
	}

	this.toString = function(delim) {
		var retString = this.pointA.x+delim+this.pointA.y+delim+this.pointB.x+delim+this.pointB.y;
		return retString;
	}


	this.fromString = function(str, delim) {
		var coords = str.split(delim);
		for(var i = 0; i < coords.length; i++) {
			coords[i] = parseFloat(coords[i]);
		}
		this.pointA = new Point(coords[0], coords[1]);
		this.pointB = new Point(coords[2], coords[3]);
	}

	this.intersectEndPoint = function() {
	}
	
/*
this.intersects = function(testLine) {
		var minX = this.minX();
		var maxX = this.maxX();

		var testMinX = testLine.minX();
		var testMaxX = testLine.maxX();

		var minY = this.minY();
		var maxY = this.maxY();
		var testMinY = testLine.minY();
		var testMaxY = testLine.maxY();

		// This saves some time if the lines don't share a domain
		if(testMinX > maxX || testMaxX < minX) {
			return false;
		}

		// If the line is striaght up and down, it needs to be handled
		// In a special fashion, checking both the X and Y domain
		// using the end points.
		if((this.pointA.x - this.pointB.x) == 0) {
			var testLineY = testLine.eval(this.pointA.x);
			return (testLineY >= minY && testLineY <= maxY);
		}
		if(testMinX - testMaxX == 0) {
			return(testMinX >= minX && testMinX <= maxX);
		}

		// Do some domain normalization, narrows the test domain
		// to the smaller line segment.
		minX = returnGreater(testMinX, minX);
		maxX = returnLesser(testMaxX, maxX);


		return (
			(this.eval(minX) < testLine.eval(minX)) && (testLine.eval(maxX) <= this.eval(maxX))
			||
			(this.eval(minX) > testLine.eval(minX)) && (testLine.eval(maxX) >= this.eval(maxX))
		);

	}
*/

	this.intersects = function(testLine) {
		var X1 =  this.pointA.x;
		var Y1 =  this.pointA.y;
		var X2 =  this.pointB.x;
		var Y2 =  this.pointB.y;

		var X3 = testLine.pointA.x;
		var Y3 = testLine.pointA.y;
		var X4 = testLine.pointB.x;
		var Y4 = testLine.pointB.y;

		var dDenom = (((X2 - X1) * (Y4 - Y3)) - ((Y2 - Y1) * (X4 - X3)));

		if(dDenom == 0) {
			return false; // Line Segments are Parallel
		}
		var dSnum = (((Y1 - Y3) * (X4 - X3)) - ((X1 - X3) * (Y4 - Y3)));
		var dTnum = (((Y1 - Y3) * (X2 - X1)) - ((X1 - X3) * (Y2 - Y1)));

		var S = dSnum / dDenom;
		var T = dTnum / dDenom;
		var testS = (0 <= S && S <= 1);
		var testT = (0 <= T && T <= 1);

		return(testS && testT)
	}

	this.buffer = function(rad) {
		var slope = this.slope();
		var inverse_slope = -1 / slope;
		var x_shift = 0, y_shift = 0;

		if(!isFinite(slope)) {
			x_shift = rad;
		} else if(slope == 0) {
			y_shift = rad;
		} else {
			var theta = Math.atan(inverse_slope);
			x_shift = Math.round(Math.cos(theta) * rad);
			y_shift = Math.round(Math.sin(theta) * rad);
		}

		var newPoints = new Array();
		newPoints[0] = new Point(this.pointA.x + x_shift, this.pointA.y + y_shift);
		newPoints[1] = new Point(this.pointB.x + x_shift, this.pointB.y + y_shift);
		newPoints[2] = new Point(this.pointB.x - x_shift, this.pointB.y - y_shift);
		newPoints[3] = new Point(this.pointA.x - x_shift, this.pointA.y - y_shift);
		var pointsString = '';
		for(var i = 0; i < newPoints.length; i++) {
			pointsString += newPoints[i].toString(',')+' ';
		}

		var newLines = new Array();
		newLines[0] = new LineSegment(newPoints[0], newPoints[1]);
		newLines[1] = new LineSegment(newPoints[1], newPoints[2]);
		newLines[2] = new LineSegment(newPoints[2], newPoints[3]);
		newLines[3] = new LineSegment(newPoints[3], newPoints[0]);
		
		//logDebugMessage('Buffered Segment', true, pointsString);
		var newPoly = new Polygon();
		for(var i = 0; i < newLines.length; i++) {
			newPoly.addLine(newLines[i]);
		}
		//logDebugMessage('Buffered Segment', true, 'Lines: '+newPoly.toString(','));
		return newPoly;
	}
}


function Polygon() {
	this.Lines = new Array();

	this.origin = new Point(0,0);

	this.type = 'polygon';
	
	var MinX = 1000000, MaxX = -1, MinY = 1000000, MaxY = -1;

	this.addLine = function(line) {
		if(line.minX() < MinX) { MinX = line.minX(); }
		if(line.maxX() > MaxX) { MaxX = line.maxX(); }
		if(line.minY() < MinY) { MinY = line.minY(); }
		if(line.maxY() > MaxY) { MaxY = line.maxY(); }

		this.Lines[this.Lines.length] = line;
	}

	this.minX = function() {
		return MinX;
	}

	this.maxX = function() {
		return MaxX;
	}

	this.minY = function() {
		return MinY;
	}

	this.maxY = function() {
		return MaxY;
	}

	this.clearLines = function () {
		this.Lines = new Array();
	}

	this.countLines = function() {
		return this.Lines.length;
	}

	this.countIntersections = function(testLine) {
		var c = 0;
		for(var i = 0; i < this.Lines.length; i++) {
			if(this.Lines[i].intersects(testLine)) {
				c++;
			}
		}
		return c;
	}

	this.isMemberPoint = function(pointA) {
		if(pointA.x < MinX || pointA.x > MaxX) { return false; }
		if(pointA.y < MinY || pointA.y > MaxY) { return false; }
		var intersections = this.countIntersections(new LineSegment(new Point(0,pointA.y), pointA));
		var intersections2 = this.countIntersections(new LineSegment(new Point(0,0), pointA));
//		return((intersections % 2) == 1 || (intersections2 % 2) == 1);
//		return (intersections % 2 == 1);

		return((intersections % 2) == 1 && (intersections2 % 2) == 1);
	}

	this.intersectsPoly = function(poly) {
		var nIntersections = 0;
		var allLines = poly.Lines;
		for(var i = 0; i < allLines.length; i++) {
			nIntersections+=this.countIntersections(allLines[i]);
		}
		return nIntersections;
	}
	
	this.isMember = function(shape) {
		if(shape.type.match(/point/i)) {
			return this.isMemberPoint(shape);
		} else if(shape.type.match(/polygon/i)) {
			var points = shape.getPoints();
			for(var p = 0; p < points.length; p++) {
				if(this.isMemberPoint(points[p])) {
					return true;
				}
			}
			if(this.intersectsPoly(shape) > 0) {
				return true;
			} else {
				//logDebugMessage('Poly Test', true, 'Not Intersect');
			}
			return false;
		} else if(shape.type.match(/line/i)) {
			return(this.countIntersections(shape) > 0);
		}
	}

	
	this.buildFromPoints = function(pointsArray) {
		this.Lines = new Array();
		var lenLimit = (pointsArray.length % 2) + 1;
		for(var i = 0; i < pointsArray.length - 1; i++) {
			var newLineSeg = new LineSegment(pointsArray[i], pointsArray[i+1]);
			this.addLine(newLineSeg);
		}
		// Now Close the polygon
		var newLineSeg = new LineSegment(pointsArray[pointsArray.length-1], pointsArray[0]);
		this.addLine(newLineSeg);
	}

	this.toString = function(delim) {
		var myStr = '';
		for(var i = 0; i < this.Lines.length; i++) {
			myStr += this.Lines[i].pointA.toString(delim) + delim;
		}
		myStr += this.Lines[this.Lines.length-1].pointB.toString(delim);
		return myStr;
	}

	this.area = function() {
		var myPoints = this.getPoints();
		myPoints[myPoints.length ] = myPoints[0];
		var sum = 0;
		for(var i = 0; i < myPoints.length - 1; i++) {
			myPoints[i].clean(); myPoints[i+1].clean();
			sum += (myPoints[i].x*myPoints[i+1].y - myPoints[i+1].x*myPoints[i].y);
			//sum += ((myPoints[i].x - myPoints[i+1].x) * (myPoints[i].y + myPoints[i+1].y)) / 2;
		}
		sum *= .5;
		return sum;
	}

	this.centroid = function() {
		var myPoints = this.getPoints();
		myPoints[myPoints.length ] = myPoints[0];
		var area = 1 / (6 * this.area());
		var x = 0;
		var y = 0;
		for(var i = 0; i < myPoints.length -1; i++) {
			myPoints[i].clean(); myPoints[i+1].clean();
			var f = (myPoints[i].x*myPoints[i+1].y - myPoints[i+1].x*myPoints[i].y);
			x += ((myPoints[i].x + myPoints[i+1].x)*f);
			y += ((myPoints[i].y + myPoints[i+1].y)*f);
		}
		return new Point(x*area,y*area);
	}

	this.getPoints = function() {
		var retArr = new Array();
		for(var i = 0; i < this.Lines.length; i++) {
			retArr[retArr.length] = this.Lines[i].pointA;
		}
		return retArr;
	}

	this.buffer = function(rad) {
		var center = this.centroid();
		var bufferedPoints = new Array();
		var myPoints = this.getPoints();
		myPoints[myPoints.length] = myPoints[0];

		var elimBuffers = new Array();

		elimBuffers[0] = this;

		for(var i = 0; i < myPoints.length -1; i++) {
			var line = new LineSegment(myPoints[i], myPoints[i+1]);
			elimBuffers[elimBuffers.length] = line.buffer(rad);
			var circ = new Circle();
			circ.Center = myPoints[i];
			circ.Radius = rad;
			elimBuffers[elimBuffers.length] = circ;
		}
		return elimBuffers;
	}
}


function Circle(cCenter, cRadius) {
	this.Center = cCenter;
	this.Radius = cRadius;

	this.type = 'circle';

	this.isMemberPoint = function(P) {
		var line = new LineSegment(this.Center, P);
		var len = line.getLength();
		return(len < this.Radius);
	}

	function square(x) {
		return (x*x);
	}


	this.minX = function() {
		return (this.Center.x - this.Radius);
	}

	this.maxX = function() {
		return(this.Center.x + this.Radius);
	}

	this.minY = function() {
		return (this.Center.y - this.Radius);
	}

	this.maxY = function() {
		return (this.Center.y + this.Radius);
	}

	this.isMember = function(Poly) {
		if(Poly.type.match(/point/i)) {
			return this.isMemberPoint(Poly);
		} else if(Poly.type.match(/circle/i)) {
			var testLine = new LineSegment(this.Center, Poly.Center);
			var totalLength = this.Radius + Poly.Radius;
			return(testLine.getLength() <= totalLength);
		} else if(Poly.type.match(/line/i)) {
			var x1 = Poly.pointA.x;
			var y1 = Poly.pointA.y;
			var x2 = Poly.pointB.x;
			var y2 = Poly.pointB.y;

			var x3 = this.Center.x;
			var y3 = this.Center.y;

			var r = parseFloat(this.Radius);
			var diffX = x2-x1;
			var diffY = y2-y1;
			var diffXSquared = square(diffX);
			var diffYSquared = square(diffY);
			var a = diffXSquared + diffYSquared;
			var b = 2* (diffX*(x1 - x3) + diffY*(y1 - y3));
			var c = square(x3) + square(y3) +  square(x1) + square(y1)  - 2* ( x3*x1 + y3*y1 ) - square(r);

			var det = b * b - 4 * a * c;


			if(det <= 0) { return false; }

			b = (x3 - x1)*(x2 - x1) + (y3 - y1)*(y2 - y1);
			//b = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
			var u= b/a;

			//logDebugMessage('Determinate', false, u);
			return(0 <= u && u <= 1);
		} else if(Poly.type.match(/poly/i)) {
			var points = Poly.getPoints();
			var member = false;
			for(var i = 0; i < points.length && !member; i++) {
				if(this.isMemberPoint(points[i])) {
					return true;
				}
			}

			var theLines = Poly.Lines;
			for(var i = 0; i < theLines.length && !member; i++) {
				if(this.isMember(theLines[i])) {
					return true;
				}
			}
			return false;
		}
		return false;
	}

	this.toString = function(delim) {
		var PointA = new Point(this.Center.x - this.Radius, this.Center.y - this.Radius);
		var PointB = new Point(this.Center.x + this.Radius, this.Center.y + this.Radius);
		return(PointA.toString(delim)+delim+PointB.toString(delim));
	}

	this.buffer = function(rad) {
		var newCirc = new Circle();
		newCirc.Center = this.Center;
		newCirc.Radius = this.Radius + rad;
		return newCirc;
	}
}
