--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lib/GeoTemCo/js/Map/Clustering.js	Thu May 28 10:28:12 2015 +0200
@@ -0,0 +1,944 @@
+/*
+* Clustering.js
+*
+* Copyright (c) 2012, Stefan Jänicke. All rights reserved.
+*
+* This library is free software; you can redistribute it and/or
+* modify it under the terms of the GNU Lesser General Public
+* License as published by the Free Software Foundation; either
+* version 3 of the License, or (at your option) any later version.
+*
+* This library is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+* Lesser General Public License for more details.
+*
+* You should have received a copy of the GNU Lesser General Public
+* License along with this library; if not, write to the Free Software
+* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+* MA 02110-1301  USA
+*/
+
+/**
+ * @class Vertex, Edge, Triangle, Clustering, BinaryHeap
+ * Dynamic Delaunay clustering algorithm (see GeoTemCo paper)
+ * @author Stefan Jänicke (stjaenicke@informatik.uni-leipzig.de)
+ * @release 1.0
+ * @release date: 2012-07-27
+ * @version date: 2012-07-27
+ */
+
+function Vertex(x, y, categories, binning) {
+	this.x = x;
+	this.y = y;
+	this.radius
+	this.size = 0;
+	this.elements = [];
+	this.radii = [];
+	this.weights = [];
+	this.legal = true;
+	this.binning = binning;
+	if (categories != undefined) {
+		for (var i = 0; i < categories; i++) {
+			this.elements.push([]);
+			this.weights.push(0);
+		}
+	}
+}
+
+Vertex.prototype.merge = function(v0, v1) {
+	for (var i = 0; i < v0.elements.length; i++) {
+		this.elements[i] = v0.elements[i].concat(v1.elements[i]);
+		this.weights[i] = v0.weights[i] + v1.weights[i];
+		this.size += this.weights[i];
+	}
+}
+
+Vertex.prototype.CalculateRadius = function(resolution) {
+	this.radii = [];
+	for (i in this.elements ) {
+		this.radii.push(this.binning.getRadius(this.weights[i]));
+	}
+	if (this.radii.length == 1) {
+		this.radius = this.radii[0] * resolution;
+	} else {
+		var count = 0;
+		var max1 = 0;
+		var max2 = 0;
+		for (i in this.radii ) {
+			if (this.radii[i] != 0) {
+				count++;
+			}
+			if (this.radii[i] > max1) {
+				if (max1 > max2) {
+					max2 = max1;
+				}
+				max1 = this.radii[i];
+			} else if (this.radii[i] > max2) {
+				max2 = this.radii[i];
+			}
+		}
+		if (count == 1) {
+			this.radius = max1 * resolution;
+		} else if (count == 2) {
+			this.radius = (max1 + max2) * resolution;
+		} else if (count == 3) {
+			var d = (2 / 3 * Math.sqrt(3) - 1) * max1;
+			this.radius = (d + max1 + max2) * resolution;
+		} else if (count == 4) {
+			var d = (Math.sqrt(2) - 1) * max2;
+			this.radius = (d + max1 + max2) * resolution;
+		}
+	}
+}
+
+Vertex.prototype.addElement = function(e, weight, index) {
+	this.elements[index].push(e);
+	this.size += weight;
+	this.weights[index] += weight;
+}
+function Edge(v0, v1) {
+	this.v0 = v0;
+	this.v1 = v1;
+	this.leftFace
+	this.rightFace
+	this.legal = true;
+	this.setLength();
+}
+
+Edge.prototype.setLength = function() {
+	var dx = this.v0.x - this.v1.x;
+	var dy = this.v0.y - this.v1.y;
+	this.length = Math.sqrt(dx * dx + dy * dy);
+}
+
+Edge.prototype.contains = function(v) {
+	if (this.v0 == v || this.v1 == v) {
+		return true;
+	}
+	return false;
+}
+
+Edge.prototype.replaceFace = function(f_old, f_new) {
+	if (this.leftFace == f_old) {
+		this.leftFace = f_new;
+	} else if (this.rightFace == f_old) {
+		this.rightFace = f_new;
+	}
+}
+
+Edge.prototype.setFace = function(f) {
+	if (f.leftOf(this)) {
+		this.leftFace = f;
+	} else {
+		this.rightFace = f;
+	}
+}
+
+Edge.prototype.setFaces = function(f1, f2) {
+	if (f1.leftOf(this)) {
+		this.leftFace = f1;
+		this.rightFace = f2;
+	} else {
+		this.leftFace = f2;
+		this.rightFace = f1;
+	}
+}
+
+Edge.prototype.removeFace = function(f) {
+	if (this.leftFace == f) {
+		this.leftFace = null;
+	} else {
+		this.rightFace = null;
+	}
+}
+
+Edge.prototype.equals = function(e) {
+	if (this.v0 == e.v0 && this.v1 == e.v1 || this.v0 == e.v1 && this.v1 == e.v0) {
+		return true;
+	}
+	return false;
+}
+function Triangle(edges) {
+	this.edges = edges;
+	this.setVertices();
+	this.descendants = [];
+}
+
+Triangle.prototype.getTriple = function(e) {
+	var i = arrayIndex(this.edges, e);
+	return {
+		e_s : this.edges[(i + 1) % 3],
+		e_p : this.edges[(i + 2) % 3],
+		u : this.vertices[(i + 2) % 3]
+	};
+}
+
+Triangle.prototype.leftOf = function(e) {
+	var i = arrayIndex(this.edges, e);
+	if (this.vertices[i].y != this.vertices[(i + 1) % 3].y) {
+		return this.vertices[i].y > this.vertices[(i + 1) % 3].y;
+	}
+	return this.vertices[i].y > this.vertices[(i + 2) % 3].y;
+}
+
+Triangle.prototype.getNext = function(v) {
+	var i = arrayIndex(this.vertices, v);
+	return this.vertices[(i + 1) % 3];
+}
+
+Triangle.prototype.oppositeEdge = function(v) {
+	var i = arrayIndex(this.vertices, v);
+	return this.edges[(i + 1) % 3];
+}
+
+Triangle.prototype.contains = function(v) {
+	return arrayIndex(this.vertices, v) != -1;
+}
+
+Triangle.prototype.replace = function(e_old, e_new) {
+	this.edges[arrayIndex(this.edges, e_old)] = e_new;
+}
+
+Triangle.prototype.setVertices = function() {
+	if (this.edges[1].v0 == this.edges[0].v0 || this.edges[1].v1 == this.edges[0].v0) {
+		this.vertices = [this.edges[0].v1, this.edges[0].v0];
+	} else {
+		this.vertices = [this.edges[0].v0, this.edges[0].v1];
+	}
+	if (this.edges[2].v0 == this.vertices[0]) {
+		this.vertices.push(this.edges[2].v1);
+	} else {
+		this.vertices.push(this.edges[2].v0);
+	}
+}
+
+Triangle.prototype.replaceBy = function(triangles) {
+	this.descendants = triangles;
+	this.edges[0].replaceFace(this, triangles[0]);
+	this.edges[1].replaceFace(this, triangles[1]);
+	this.edges[2].replaceFace(this, triangles[2]);
+}
+
+Triangle.prototype.CalcCircumcircle = function() {
+	var v0 = this.vertices[0];
+	var v1 = this.vertices[1];
+	var v2 = this.vertices[2];
+	var A = v1.x - v0.x;
+	var B = v1.y - v0.y;
+	var C = v2.x - v0.x;
+	var D = v2.y - v0.y;
+	var E = A * (v0.x + v1.x) + B * (v0.y + v1.y);
+	var F = C * (v0.x + v2.x) + D * (v0.y + v2.y);
+	var G = 2.0 * (A * (v2.y - v1.y) - B * (v2.x - v1.x));
+	var cx = (D * E - B * F) / G;
+	var cy = (A * F - C * E) / G;
+	this.center = new Vertex(cx, cy);
+	var dx = this.center.x - v0.x;
+	var dy = this.center.y - v0.y;
+	this.radius_squared = dx * dx + dy * dy;
+};
+
+Triangle.prototype.inCircumcircle = function(v) {
+	if (this.radius_squared == undefined) {
+		this.CalcCircumcircle();
+	}
+	var dx = this.center.x - v.x;
+	var dy = this.center.y - v.y;
+	var dist_squared = dx * dx + dy * dy;
+	return (dist_squared <= this.radius_squared );
+};
+
+Triangle.prototype.interior = function(v) {
+	var v0 = this.vertices[0];
+	var v1 = this.vertices[1];
+	var v2 = this.vertices[2];
+	var dotAB = (v.x - v0.x ) * (v0.y - v1.y ) + (v.y - v0.y ) * (v1.x - v0.x );
+	var dotBC = (v.x - v1.x ) * (v1.y - v2.y ) + (v.y - v1.y ) * (v2.x - v1.x );
+	var dotCA = (v.x - v2.x ) * (v2.y - v0.y ) + (v.y - v2.y ) * (v0.x - v2.x );
+	if (dotAB > 0 || dotBC > 0 || dotCA > 0) {
+		return null;
+	} else if (dotAB < 0 && dotBC < 0 && dotCA < 0) {
+		return this;
+	} else if (dotAB == 0) {
+		if (dotBC == 0) {
+			return this.vertices[1];
+		} else if (dotCA == 0) {
+			return this.vertices[0];
+		}
+		return this.edges[0];
+	} else if (dotBC == 0) {
+		if (dotCA == 0) {
+			return this.vertices[2];
+		}
+		return this.edges[1];
+	} else if (dotCA == 0) {
+		return this.edges[2];
+	}
+};
+
+function Clustering(xMin, yMin, xMax, yMax) {
+	this.triangles = [];
+	this.newTriangles = [];
+	this.bbox = {
+		x1 : xMin,
+		y1 : yMin,
+		x2 : xMax,
+		y2 : yMax
+	};
+	this.CreateBoundingTriangle();
+	this.edges = [];
+	this.vertices = [];
+	this.legalizes = 0;
+	this.collapses = 0;
+}
+
+Clustering.prototype.locate = function(v) {
+	if (this.boundingTriangle.descendants.length == 0) {
+		return this.boundingTriangle;
+	}
+	var triangles = this.boundingTriangle.descendants;
+	while (true) {
+		for (var i = 0; i < triangles.length; i++) {
+			var simplex = triangles[i].interior(v);
+			if (simplex == null) {
+				continue;
+			}
+			if ( simplex instanceof Vertex || this.isLeaf(triangles[i])) {
+				return simplex;
+			}
+			triangles = triangles[i].descendants;
+			break;
+		}
+	}
+}
+
+Clustering.prototype.legalize = function(v, e, t0_old) {
+	if (!e.v0.legal && !e.v1.legal) {
+		return;
+	}
+	this.legalizes++;
+	var flip = false;
+	var t1_old, tr1;
+	if (e.leftFace == t0_old && e.rightFace.inCircumcircle(v)) {
+		flip = true;
+		t1_old = e.rightFace;
+	} else if (e.rightFace == t0_old && e.leftFace.inCircumcircle(v)) {
+		flip = true;
+		t1_old = e.leftFace;
+	}
+	if (flip) {
+		var tr0 = t0_old.getTriple(e);
+		var tr1 = t1_old.getTriple(e);
+		var e_flip = new Edge(tr0.u, tr1.u);
+		var poly = [];
+		poly.push(e.v0);
+		poly.push(e_flip.v0);
+		poly.push(e.v1);
+		poly.push(e_flip.v1);
+		if (!this.JordanTest(poly, e_flip)) {
+			return;
+		}
+		e.legal = false;
+		this.edges.push(e_flip);
+		var t0_new = new Triangle([e_flip, tr0.e_p, tr1.e_s]);
+		var t1_new = new Triangle([e_flip, tr1.e_p, tr0.e_s]);
+		e_flip.setFaces(t0_new, t1_new);
+		tr0.e_p.replaceFace(t0_old, t0_new);
+		tr1.e_s.replaceFace(t1_old, t0_new);
+		tr1.e_p.replaceFace(t1_old, t1_new);
+		tr0.e_s.replaceFace(t0_old, t1_new);
+		t0_old.descendants = [t0_new, t1_new];
+		t1_old.descendants = [t0_new, t1_new];
+		this.legalize(v, t0_new.edges[2], t0_new);
+		this.legalize(v, t1_new.edges[1], t1_new);
+	}
+}
+
+Clustering.prototype.add = function(v) {
+	this.addVertex(v, this.locate(v));
+}
+
+Clustering.prototype.addVertex = function(v, simplex) {
+	if ( simplex instanceof Vertex) {
+		simplex.merge(simplex, v);
+	} else if ( simplex instanceof Edge) {
+		this.vertices.push(v);
+		simplex.legal = false;
+		var tr0 = simplex.leftFace.getTriple(simplex);
+		var tr1 = simplex.rightFace.getTriple(simplex);
+		var e0 = new Edge(v, tr0.u);
+		var e1 = new Edge(v, simplex.leftFace.getNext(tr0.u));
+		var e2 = new Edge(v, tr1.u);
+		var e3 = new Edge(v, simplex.rightFace.getNext(tr1.u));
+		var t0 = new Triangle([e0, tr0.e_p, e1]);
+		var t1 = new Triangle([e1, tr1.e_s, e2]);
+		var t2 = new Triangle([e2, tr1.e_p, e3]);
+		var t3 = new Triangle([e3, tr0.e_s, e0]);
+		simplex.leftFace.descendants = [t0, t3];
+		simplex.rightFace.descendants = [t1, t2];
+		this.edges.push(e0);
+		this.edges.push(e1);
+		this.edges.push(e2);
+		this.edges.push(e3);
+		e0.setFaces(t0, t3);
+		e1.setFaces(t0, t1);
+		e2.setFaces(t1, t2);
+		e3.setFaces(t2, t3);
+		tr0.e_p.replaceFace(simplex.leftFace, t0);
+		tr1.e_s.replaceFace(simplex.rightFace, t1);
+		tr1.e_p.replaceFace(simplex.rightFace, t2);
+		tr0.e_s.replaceFace(simplex.leftFace, t3);
+		this.legalize(v, tr0.e_p, t0);
+		this.legalize(v, tr1.e_s, t1);
+		this.legalize(v, tr1.e_p, t2);
+		this.legalize(v, tr0.e_s, t3);
+	} else {
+		this.vertices.push(v);
+		var e_i = new Edge(simplex.vertices[0], v);
+		var e_j = new Edge(simplex.vertices[1], v);
+		var e_k = new Edge(simplex.vertices[2], v);
+		this.edges.push(e_i);
+		this.edges.push(e_j);
+		this.edges.push(e_k);
+		var t0 = new Triangle([e_i, simplex.edges[0], e_j]);
+		var t1 = new Triangle([e_j, simplex.edges[1], e_k]);
+		var t2 = new Triangle([e_k, simplex.edges[2], e_i]);
+		e_i.setFaces(t0, t2);
+		e_j.setFaces(t0, t1);
+		e_k.setFaces(t1, t2);
+		simplex.replaceBy([t0, t1, t2]);
+		this.legalize(v, simplex.edges[0], t0);
+		this.legalize(v, simplex.edges[1], t1);
+		this.legalize(v, simplex.edges[2], t2);
+	}
+}
+
+Clustering.prototype.isLeaf = function(t) {
+	return t.descendants.length == 0;
+}
+
+Clustering.prototype.CreateBoundingTriangle = function() {
+	var dx = (this.bbox.x2 - this.bbox.x1 ) * 10;
+	var dy = (this.bbox.y2 - this.bbox.y1 ) * 10;
+	var v0 = new Vertex(this.bbox.x1 - dx, this.bbox.y1 - dy * 3);
+	var v1 = new Vertex(this.bbox.x2 + dx * 3, this.bbox.y2 + dy);
+	var v2 = new Vertex(this.bbox.x1 - dx, this.bbox.y2 + dy);
+	var e0 = new Edge(v1, v0);
+	var e1 = new Edge(v0, v2);
+	var e2 = new Edge(v2, v1);
+	v0.legal = false;
+	v1.legal = false;
+	v2.legal = false;
+	this.boundingTriangle = new Triangle([e0, e1, e2]);
+	var inf = new Triangle([e0, e1, e2]);
+	e0.setFaces(this.boundingTriangle, inf);
+	e1.setFaces(this.boundingTriangle, inf);
+	e2.setFaces(this.boundingTriangle, inf);
+}
+
+Clustering.prototype.mergeVertices = function(e) {
+	this.collapses++;
+	var s0 = e.v0.size;
+	var s1 = e.v1.size;
+	var x = (e.v0.x * s0 + e.v1.x * s1 ) / (s0 + s1 );
+	var y = (e.v0.y * s0 + e.v1.y * s1 ) / (s0 + s1 );
+	var v = new Vertex(x, y, e.v0.elements.length, e.v0.binning);
+	v.merge(e.v0, e.v1);
+
+	e.v0.legal = false;
+	e.v1.legal = false;
+
+	var hole = [];
+	var oldFacets = [];
+	e.legal = false;
+
+	var vertices = [];
+	var traverse = function(eLeft, eRight, triangle) {
+		eLeft.legal = false;
+		do {
+			var triple;
+			if (eLeft.leftFace == triangle) {
+				triple = eLeft.rightFace.getTriple(eLeft);
+				oldFacets.push(eLeft.rightFace);
+				triple.e_s.removeFace(eLeft.rightFace);
+				triangle = eLeft.rightFace;
+			} else {
+				triple = eLeft.leftFace.getTriple(eLeft);
+				oldFacets.push(eLeft.leftFace);
+				triple.e_s.removeFace(eLeft.leftFace);
+				triangle = eLeft.leftFace;
+			}
+			if (arrayIndex(hole, triple.e_s) == -1) {
+				hole.push(triple.e_s);
+			}
+			vertices.push(triple.u);
+			eLeft = triple.e_p;
+			eLeft.legal = false;
+		} while( eLeft != eRight );
+	}
+	var tr0 = e.leftFace.getTriple(e);
+	var tr1 = e.rightFace.getTriple(e);
+	oldFacets.push(e.leftFace);
+	oldFacets.push(e.rightFace);
+	traverse(tr0.e_p, tr1.e_s, e.leftFace);
+	traverse(tr1.e_p, tr0.e_s, e.rightFace);
+
+	var hd = new Clustering(this.bbox.x1 - 10, this.bbox.y1 - 10, this.bbox.x2 + 10, this.bbox.y2 + 10);
+	var hull = [];
+	for (var i in hole ) {
+		if (!(hole[i].leftFace == null && hole[i].rightFace == null)) {
+			hull.push(hole[i].v0);
+			hull.push(hole[i].v1);
+		}
+	}
+	var hullVertices = [];
+	var distinct = [];
+	for (var i in vertices ) {
+		if (arrayIndex(distinct, vertices[i]) == -1) {
+			hd.add(vertices[i]);
+			distinct.push(vertices[i]);
+		}
+		if (arrayIndex(hull, vertices[i]) != -1) {
+			hullVertices.push(vertices[i]);
+		}
+	}
+
+	var newFacets = [];
+	var isBoundary = function(e) {
+		for (var i = 0; i < hole.length; i++) {
+			if (hole[i].equals(e)) {
+				return i;
+			}
+		}
+		return -1;
+	}
+	var holeEdges = new Array(hole.length);
+	var nonHoleEdges = [];
+
+	for (var i = 0; i < hd.edges.length; i++) {
+		var e = hd.edges[i];
+		var b = isBoundary(e);
+		if (b != -1) {
+			if (!e.legal) {
+				var t1 = e.leftFace.getTriple(e);
+				var t2 = e.rightFace.getTriple(e);
+				var edge = new Edge(t1.u, t2.u);
+				for (var j = 0; j < hd.edges.length; j++) {
+					if (hd.edges[j].equals(edge) && hd.edges[j].legal) {
+						hd.edges[j].legal = false;
+						break;
+					}
+				}
+				t1.e_p.setFace(e.leftFace);
+				t1.e_s.setFace(e.leftFace);
+				t2.e_p.setFace(e.rightFace);
+				t2.e_s.setFace(e.rightFace);
+
+				e.legal = true;
+			}
+			holeEdges[b] = e;
+		} else {
+			nonHoleEdges.push(e);
+		}
+	}
+
+	for (var i = 0; i < holeEdges.length; i++) {
+		var e = holeEdges[i];
+		if (hole[i].leftFace == null) {
+			hole[i].leftFace = e.leftFace;
+			hole[i].leftFace.replace(e, hole[i]);
+			if (arrayIndex(newFacets, hole[i].leftFace) == -1) {
+				newFacets.push(hole[i].leftFace);
+			}
+		}
+		if (hole[i].rightFace == null) {
+			hole[i].rightFace = e.rightFace;
+			hole[i].rightFace.replace(e, hole[i]);
+			if (arrayIndex(newFacets, hole[i].rightFace) == -1) {
+				newFacets.push(hole[i].rightFace);
+			}
+		}
+	}
+
+	for (var i = 0; i < nonHoleEdges.length; i++) {
+		var e = nonHoleEdges[i];
+		if (!e.legal) {
+			continue;
+		}
+		if (this.JordanTest(hullVertices, e)) {
+			this.edges.push(e);
+			if (arrayIndex(newFacets, e.rightFace) == -1) {
+				newFacets.push(e.rightFace);
+			}
+			if (arrayIndex(newFacets, e.leftFace) == -1) {
+				newFacets.push(e.leftFace);
+			}
+		}
+	}
+
+	for (var i in oldFacets ) {
+		oldFacets[i].descendants = newFacets;
+	}
+
+	for (var i = 0; i < newFacets.length; i++) {
+		var simplex = newFacets[i].interior(v);
+		if (simplex == null) {
+			continue;
+		} else {
+			this.addVertex(v, simplex);
+			break;
+		}
+	}
+
+	return v;
+
+}
+
+Clustering.prototype.JordanTest = function(pol, e) {
+	var p = new Vertex((e.v0.x + e.v1.x) * 0.5, (e.v0.y + e.v1.y) * 0.5);
+	var inside = false;
+	var i, j = pol.length - 1;
+	for ( i = 0; i < pol.length; j = i++) {
+		var p1 = pol[i];
+		var p2 = pol[j];
+		if ((((p1.y <= p.y) && (p.y < p2.y)) || ((p2.y <= p.y) && (p.y < p1.y))) && (p.x < (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y) + p1.x))
+			inside = !inside;
+	}
+	return inside;
+}
+
+Clustering.prototype.mergeForResolution = function(resolution, circleGap, circleOverlap) {
+	this.deleteEdges = new BinaryHeap(function(e) {
+		return e.weight;
+	});
+	this.weightEdges(resolution, circleGap, circleOverlap);
+	var index = 0;
+	while (this.deleteEdges.size() > 0) {
+		var e = this.deleteEdges.pop();
+		if (e.legal) {
+			var l = this.edges.length;
+			var newVertex = this.mergeVertices(e);
+			newVertex.CalculateRadius(resolution);
+			for (var k = l; k < this.edges.length; k++) {
+				var eNew = this.edges[k];
+				if (eNew.legal) {
+					if( circleGap != 0 ){
+						eNew.weight = eNew.length / (eNew.v0.radius + eNew.v1.radius + circleGap * resolution );
+					}
+					else if( circleOverlap.overlap == 0 ){
+						eNew.weight = eNew.length / (eNew.v0.radius + eNew.v1.radius);
+					}
+					else {
+						var r1 = eNew.v0.radius;
+						var r2 = eNew.v1.radius;
+						var r = eNew.length;
+						if( r < r1 + r2 ){
+							if( circleOverlap.type == 'diameter' ){
+								var ol1 = (r2-(r-r1)) / r1 / 2;
+								var ol2 = (r1-(r-r2)) / r2 / 2;
+								var ol = Math.max(ol1,ol2);
+								eNew.weight = circleOverlap.overlap / ol;
+							}
+							if( circleOverlap.type == 'area' ){								
+								if( !(r+r1 < r2 || r+r2 < r1) ){
+									var A = r2*r2*Math.acos((r*r+r2*r2-r1*r1)/(2*r*r2))+r1*r1*Math.acos((r*r+r1*r1-r2*r2)/(2*r*r1))-1/2*Math.sqrt((-r+r1+r2)*(r-r1+r2)*(r+r1-r2)*(r+r1+r2));
+									var ol1 = A / (Math.PI*r1*r1);
+									var ol2 = A / (Math.PI*r2*r2);
+									var ol = Math.max(ol1,ol2);
+									eNew.weight = circleOverlap.overlap / ol;
+								}
+								else {
+									eNew.weight = 0;
+								}
+							}
+						}
+					}
+					if (eNew.weight < 1) {
+						this.deleteEdges.push(eNew);
+					}
+				}
+			}
+		}
+	}
+}
+
+Clustering.prototype.weightEdges = function(resolution, circleGap, circleOverlap) {
+	for (var i = 0; i < this.vertices.length; i++) {
+		if (this.vertices[i].legal) {
+			this.vertices[i].CalculateRadius(resolution);
+		}
+	}
+	var newEdges = [];
+	for (var i = 0; i < this.edges.length; i++) {
+		var e = this.edges[i];
+		if (e.legal) {
+			if (!e.v0.legal || !e.v1.legal) {
+				e.weight = 1;
+			} else {
+				if( circleGap != 0 ){
+					e.weight = e.length / (e.v0.radius + e.v1.radius + circleGap * resolution );
+				}
+				else if( circleOverlap.overlap == 0 ){
+					e.weight = e.length / (e.v0.radius + e.v1.radius);
+				}
+				else {
+					var r1 = e.v0.radius;
+					var r2 = e.v1.radius;
+					var r = e.length;
+					if( r < r1 + r2 ){
+						if( circleOverlap.type == 'diameter' ){
+							var ol1 = (r2-(r-r1)) / r1 / 2;
+							var ol2 = (r1-(r-r2)) / r2 / 2;
+							var ol = Math.max(ol1,ol2);
+							e.weight = circleOverlap.overlap / ol;
+						}
+						if( circleOverlap.type == 'area' ){
+							if( !(r+r1 < r2 || r+r2 < r1) ){
+								var A = r2*r2*Math.acos((r*r+r2*r2-r1*r1)/(2*r*r2))+r1*r1*Math.acos((r*r+r1*r1-r2*r2)/(2*r*r1))-1/2*Math.sqrt((-r+r1+r2)*(r-r1+r2)*(r+r1-r2)*(r+r1+r2));
+								var ol1 = A / (Math.PI*r1*r1);
+								var ol2 = A / (Math.PI*r2*r2);
+								var ol = Math.max(ol1,ol2);
+								e.weight = circleOverlap.overlap / ol;
+							}
+							else {
+								e.weight = 0;
+							}
+						}
+					}
+				}
+				if (e.weight < 1) {
+					this.deleteEdges.push(e);
+				}
+			}
+			newEdges.push(e);
+		}
+	}
+	this.edges = newEdges;
+}
+
+Clustering.prototype.ValidityTest = function() {
+	console.info("Test 1: Valid Delaunay ...");
+	/*
+	var leafs = [];
+	var triangles = this.boundingTriangle.descendants;
+	var j = 0;
+	while( triangles.length > j ){
+	var t = triangles[j];
+	if( t.taken == undefined ){
+	t.taken = true;
+	if( this.isLeaf(t) ){
+	leafs.push(t);
+	}
+	else {
+	triangles = triangles.concat(t.descendants);
+	}
+	}
+	j++;
+	}
+	console.info("  Number of Triangles: "+leafs.length);
+
+	var c = 0;
+	for( i in this.edges ){
+	if( this.edges[i].legal ){
+	c++;
+	}
+	}
+	console.info("  Number of Edges: "+c);*/
+	/*
+
+	for( var i=0; i<leafs.length; i++ ){
+	for( var j=0; j<vertices.length; j++ ){
+	if( !leafs[i].contains(vertices[j]) && leafs[i].inCircumcircle(vertices[j]) ){
+	console.info(leafs[i],vertices[j]);
+
+	}
+	}
+	}
+	*/
+
+	//console.info("Test 2: Edges Facets (null) ...");
+	for (i in this.edges ) {
+		var e = this.edges[i];
+		if (e.leftFace == null || e.rightFace == null) {
+			console.info(e);
+			alert();
+		}
+	}
+
+	//console.info("Test 3: Edges Facets ...");
+	var leftOf = function(v1, v2, v) {
+		var x2 = v1.x - v2.x;
+		var x3 = v1.x - v.x;
+		var y2 = v1.y - v2.y;
+		var y3 = v1.y - v.y;
+		if (x2 * y3 - y2 * x3 < 0) {
+			return true;
+		}
+		return false;
+	}
+	var c = 0;
+	for (i in this.edges ) {
+		var e = this.edges[i];
+		var t1 = e.leftFace.getTriple(e);
+		var t2 = e.rightFace.getTriple(e);
+		if (e.v0.y == e.v1.y) {
+			if (t1.u.y > t2.u.y) {
+				console.info("equal y conflict ...");
+				console.info(e);
+				alert();
+				c++;
+			}
+		} else {
+			var v1, v2;
+			if (e.v0.y > e.v1.y) {
+				v1 = e.v0;
+				v2 = e.v1;
+			} else {
+				v1 = e.v1;
+				v2 = e.v0;
+			}
+			if (!leftOf(v1, v2, t1.u)) {
+				console.info("left right conflict ... left is right");
+				console.info(e);
+				alert();
+				c++;
+			}
+			if (leftOf(v1, v2, t2.u)) {
+				console.info("left right conflict ... right is left");
+				console.info(e);
+				alert();
+				c++;
+			}
+		}
+	}
+	//console.info("Number of Edges: "+this.edges.length);
+	//console.info("Number of Conflicts: "+c);
+
+	for (i in this.edges ) {
+		if (this.edges[i].legal) {
+			var e = this.edges[i];
+			var tr0 = e.leftFace.getTriple(e);
+			var tr1 = e.rightFace.getTriple(e);
+			if (!tr0.e_p.legal || !tr0.e_s.legal || !tr1.e_p.legal || !tr1.e_s.legal) {
+				console.info(e);
+				console.info("conflict in edge continuity");
+				return;
+			}
+		}
+	}
+
+}
+function BinaryHeap(scoreFunction) {
+	this.content = [];
+	this.scoreFunction = scoreFunction;
+}
+
+BinaryHeap.prototype = {
+	push : function(element) {
+		// Add the new element to the end of the array.
+		this.content.push(element);
+		// Allow it to bubble up.
+		this.bubbleUp(this.content.length - 1);
+	},
+
+	pop : function() {
+		// Store the first element so we can return it later.
+		var result = this.content[0];
+		// Get the element at the end of the array.
+		var end = this.content.pop();
+		// If there are any elements left, put the end element at the
+		// start, and let it sink down.
+		if (this.content.length > 0) {
+			this.content[0] = end;
+			this.sinkDown(0);
+		}
+		return result;
+	},
+
+	remove : function(node) {
+		var len = this.content.length;
+		// To remove a value, we must search through the array to find
+		// it.
+		for (var i = 0; i < len; i++) {
+			if (this.content[i] == node) {
+				// When it is found, the process seen in 'pop' is repeated
+				// to fill up the hole.
+				var end = this.content.pop();
+				if (i != len - 1) {
+					this.content[i] = end;
+					if (this.scoreFunction(end) < this.scoreFunction(node))
+						this.bubbleUp(i);
+					else
+						this.sinkDown(i);
+				}
+				return;
+			}
+		}
+		throw new Error("Node not found.");
+	},
+
+	size : function() {
+		return this.content.length;
+	},
+
+	bubbleUp : function(n) {
+		// Fetch the element that has to be moved.
+		var element = this.content[n];
+		// When at 0, an element can not go up any further.
+		while (n > 0) {
+			// Compute the parent element's index, and fetch it.
+			var parentN = Math.floor((n + 1) / 2) - 1, parent = this.content[parentN];
+			// Swap the elements if the parent is greater.
+			if (this.scoreFunction(element) < this.scoreFunction(parent)) {
+				this.content[parentN] = element;
+				this.content[n] = parent;
+				// Update 'n' to continue at the new position.
+				n = parentN;
+
+			}
+			// Found a parent that is less, no need to move it further.
+			else {
+				break;
+			}
+		}
+	},
+
+	sinkDown : function(n) {
+		// Look up the target element and its score.
+		var length = this.content.length, element = this.content[n], elemScore = this.scoreFunction(element);
+
+		while (true) {
+			// Compute the indices of the child elements.
+			var child2N = (n + 1) * 2, child1N = child2N - 1;
+			// This is used to store the new position of the element,
+			// if any.
+			var swap = null;
+			// If the first child exists (is inside the array)...
+			if (child1N < length) {
+				// Look it up and compute its score.
+				var child1 = this.content[child1N], child1Score = this.scoreFunction(child1);
+				// If the score is less than our element's, we need to swap.
+				if (child1Score < elemScore)
+					swap = child1N;
+			}
+			// Do the same checks for the other child.
+			if (child2N < length) {
+				var child2 = this.content[child2N], child2Score = this.scoreFunction(child2);
+				if (child2Score < (swap == null ? elemScore : child1Score))
+					swap = child2N;
+			}
+
+			// If the element needs to be moved, swap it, and continue.
+			if (swap != null) {
+				this.content[n] = this.content[swap];
+				this.content[swap] = element;
+				n = swap;
+			}
+			// Otherwise, we are done.
+			else {
+				break;
+			}
+		}
+	}
+};