Source: math/Delaunay.js

/**
 *  
 *	@class Delaunay
 *  @memberof SQR
 *
 *  @description based on:<br> 
 *  
 *  {@link http://paulbourke.net/papers/triangulate/}<br>
 *  {@link http://www.travellermap.com/tmp/delaunay.htm} (original code)<br> 
 *  {@link https://github.com/ironwallaby/delaunay/blob/master/delaunay.js}<br> 
 *  {@link http://www.amazon.com/Computational-Geometry-Applications-Mark-Berg/dp/3642096816}
*/
SQR.Delaunay = (function() {

	var delaunay = {};

	var Edge = function(v0, v1) {
		this.v0 = v0;
		this.v1 = v1;
	}

	Edge.prototype.equals = function(other) {
		return (this.v0 === other.v0 && this.v1 === other.v1);
	};

	Edge.prototype.inverse = function() {
		return new Edge(this.v1, this.v0);
	};

	var createSuperTriangle = function(vertices) {
		// NOTE: There's a bit of a heuristic here. If the bounding triangle 
		// is too large and you see overflow/underflow errors. If it is too small 
		// you end up with a non-convex hull.

		var minx, miny, maxx, maxy;
		vertices.forEach(function(vertex) {
			if (minx === undefined || vertex.x < minx) { minx = vertex.x; }
			if (miny === undefined || vertex.y < miny) { miny = vertex.y; }
			if (maxx === undefined || vertex.x > maxx) { maxx = vertex.x; }
			if (maxy === undefined || vertex.y > maxy) { maxy = vertex.y; }
		});

		var dx = (maxx - minx) * 10;
		var dy = (maxy - miny) * 10;

		var stv0 = vertices[0].clone().set(minx - dx, miny - dy * 3);
		var stv1 = vertices[0].clone().set(minx - dx, maxy + dy);
		var stv2 = vertices[0].clone().set(maxx + dx * 3, maxy + dy);

		return new SQR.Triangle(stv0, stv1, stv2);
	}

	function addVertex(vertex, triangles) {
		var edges = [];

		triangles = triangles.filter(function(triangle) {
			if (triangle.vertexInCircumcircle(vertex)) {
				edges.push(new Edge(triangle.v0, triangle.v1));
				edges.push(new Edge(triangle.v1, triangle.v2));
				edges.push(new Edge(triangle.v2, triangle.v0));
				return false;
			}

			return true;
		});

		edges = uniqueEdges(edges);

		edges.forEach(function(edge) {
			triangles.push(new SQR.Triangle(edge.v0, edge.v1, vertex));
		});

		return triangles;
	}

	var uniqueEdges = function(edges) {
		var uniqueEdges = [];

		for (var i = 0; i < edges.length; ++i) {
			var edge1 = edges[i];
			var unique = true;

			for (var j = 0; j < edges.length; ++j) {
				if (i === j) continue;
				var edge2 = edges[j];
				if (edge1.equals(edge2) || edge1.inverse().equals(edge2)) {
					unique = false;
					break;
				}
			}

			if (unique) uniqueEdges.push(edge1);
		}

		return uniqueEdges;
	}

	/**
	 *	@method triangulate
	 *	@memberof SQR.Delaunay
	 *
	 *	@description Performs Delaunay triangulation.
	 *
	 *	@param vertices - a list of 2d vertices. 
	 *	Can be {@link SQR.V2}, {@link SQR.V3} or any object that has `x` and `y` properties. 
	 *	In case of a 3d vector, the `z` component is ignored.
	 *	@returns a list of {@link SQR.Triangles}
	 */
	delaunay.triangulate = function(vertices) {
		var triangles = [];

		var st = createSuperTriangle(vertices);

		triangles.push(st);

		vertices.forEach(function(vertex) {
			// NOTE: This is O(n^2) - can be optimized by sorting vertices
			// along the x-axis and only considering triangles that have 
			// potentially overlapping circumcircles
			triangles = addVertex(vertex, triangles);
		});

		// Remove triangles that shared edges with "supertriangle"
		triangles = triangles.filter(function(triangle) {
			return !(triangle.v0 == st.v0 || triangle.v0 == st.v1 || triangle.v0 == st.v2 ||
			triangle.v1 == st.v0 || triangle.v1 == st.v1 || triangle.v1 == st.v2 ||
			triangle.v2 == st.v0 || triangle.v2 == st.v1 || triangle.v2 == st.v2);
		});

		return triangles;
	}

	return delaunay;

})();