/**
 * Geometry tools.
 */

Geometry = {};

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

Geometry.Circle = function(x, y, radius2) {
	this.center = new Geometry.Point(x, y);
	this.radius2 = radius2;
}

Geometry.Segment = function(start, end) {
	this.start = start;
	this.end = end;
}

Geometry.Segment.prototype.length2 = function() {
	var dx = this.end.x - this.start.x;
	var dy = this.end.y - this.start.y;
	return dx.squared() + dy.squared();
}

Geometry.Point.prototype.equals = function(other) {
	return this.x.equals(other.x) && this.y.equals(other.y);
}

Geometry.Circle.prototype.radius = function() {
	return Math.sqrt(this.radius2);
}

Geometry.Circle.prototype.containsPoint = function(point) {
	return ((point.x - this.center.x).squared() + (point.y - this.center.y).squared()).isLessThanOrEqual(this.radius2);
}

Geometry.Point.prototype.distanceToSegment2 = function(segment) {
	var tx = (segment.end.x - segment.start.x) * (this.x - segment.start.x);
	var ty = (segment.end.y - segment.start.y) * (this.y - segment.start.y);
	var t = (tx + ty) / segment.length2();

	t = Math.max(t, 0.0);
	t = Math.min(t, 1.0);

	var dx = segment.start.x + t * (segment.end.x - segment.start.x) - this.x;
	var dy = segment.start.y + t * (segment.end.y - segment.start.y) - this.y;

	return dx*dx + dy*dy;
}

Geometry.Segment.prototype.containsPoint = function(point) {
	var a = this.start;
	var b = this.end;

	if (a.x.equals(b.x))
		return a.x.equals(point.x) && Math.abs(b.y - a.y).equals(Math.abs(point.y - a.y) + Math.abs(point.y - b.y));

	if (a.y.equals(b.y))
		return a.y.equals(point.y) && Math.abs(b.x - a.x).equals(Math.abs(point.x - a.x) + Math.abs(point.x - b.x));

	var t = (point.x - a.x) / (b.x - a.x);

	if (t.isLessThan(0) || t.isGreaterThan(1))
		return 0;

	return t.equals((point.y - a.y) / (b.y - a.y));
}

Geometry.Segment.prototype.intersectsSegment = function(other) {
	var a = this.start;
	var b = this.end;
	var p = other.start;
	var q = other.end;

	var qpx = q.x - p.x;
	var qpy = q.y - p.y;
	var bax = b.x - a.x;
	var bay = b.y - a.y;

	if ((qpx.equals(bax) && qpy.equals(bay)) || (qpx.equals(-bax) && qpy.equals(-bay)))
		return this.containsPoint(p) || this.containsPoint(q) || other.containsPoint(a) || other.containsPoint(b);

	var pax = p.x - a.x;
	var pay = p.y - a.y;
	var d = bax * qpy - bay * qpx;
	var tx = (pax * qpy - pay * qpx) / d;
	var ty = (pax * bay - pay * bax) / d;

	return !tx.isLessThan(0) && !tx.isGreaterThan(1) && !ty.isLessThan(0) && !ty.isGreaterThan(1);
}

Geometry.Segment.prototype.distanceToSegment2 = function(other) {
	if (this.intersectsSegment(other))
		return 0.0;

	var a = this.start.distanceToSegment2(other);
	var b = this.end.distanceToSegment2(other);
	var c = other.start.distanceToSegment2(this);
	var d = other.end.distanceToSegment2(this);

	return Math.min(Math.min(a,b), Math.min(c,d));
}

/*
 * Calculate the smallest enclosing circle for an array P of points.
 *
 * Based on: Emo Welzl, Smallest enclosing disks (balls and ellipsoids), New Results and New Trends
 * in Computer Science, Lecture Notes in Computer Science 555 (1991), 359-370
 */
Geometry.Circle.minidisk = function(P, R) {
	if (R == undefined)
		R = [];

	if (P.length == 0 || R.length == 3)
		switch (R.length) {
		case 0:
			return new this(0, 0, 0);
		case 1:
			return new this(R[0].x, R[0].y, 0);
		case 2:
			return this.containingTwoPoints(R[0], R[1]);
		default:
			return this.containingThreePoints(R[0], R[1], R[2]);
		}

	var i = Math.floor(P.length * Math.random());
	var Q = P.slice(0, i).concat(P.slice(i + 1));
	var D = this.minidisk(Q, R);

	if (!D.containsPoint(P[i]))
		D = this.minidisk(Q, R.concat( [ P[i] ]));

	return D;
}

Geometry.Circle.containingTwoPoints = function(p, q) {
	var x = 0.5 * (p.x + q.x);
	var y = 0.5 * (p.y + q.y);
	return new this(x, y, (x - p.x).squared() + (y - p.y).squared());
}

Geometry.Circle.containingThreePoints = function(p, q, r) {
	var c;

	c = this.containingTwoPoints(p, q);
	if (c.containsPoint(r))
		return c;

	c = this.containingTwoPoints(p, r);
	if (c.containsPoint(q))
		return c;

	c = this.containingTwoPoints(q, r);
	if (c.containsPoint(p))
		return c;

	// see http://en.wikipedia.org/wiki/Circumscribed_circle

	var Ax = p.x, Ay = p.y;
	var Bx = q.x, By = q.y;
	var Cx = r.x, Cy = r.y;

	var D = 2 * (Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By));

	var A2 = Ax * Ax + Ay * Ay;
	var B2 = Bx * Bx + By * By;
	var C2 = Cx * Cx + Cy * Cy;

	var x = (A2 * (By - Cy) + B2 * (Cy - Ay) + C2 * (Ay - By)) / D;
	var y = (A2 * (Cx - Bx) + B2 * (Ax - Cx) + C2 * (Bx - Ax)) / D;

	var a2 = (Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By);
	var b2 = (Ax - Cx) * (Ax - Cx) + (Ay - Cy) * (Ay - Cy);
	var c2 = (Bx - Cx) * (Bx - Cx) + (By - Cy) * (By - Cy);

	var a = Math.sqrt(a2);
	var b = Math.sqrt(b2);
	var c = Math.sqrt(c2);

	var r2 = a2 * b2 * c2 / ((a + b + c) * (-a + b + c) * (a - b + c) * (a + b - c));

	return new this(x, y, r2);
}