Mercurial > hg > mpiwg_geobrowser

comparison lib/GeoTemCo/js/Map/Clustering.js @ 0:b57c7821382f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial
author Dirk Wintergruen <dwinter@mpiwg-berlin.mpg.de>
date Thu, 28 May 2015 10:28:12 +0200
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:b57c7821382f
1 /*
2 * Clustering.js
3 *
4 * Copyright (c) 2012, Stefan Jänicke. All rights reserved.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 3 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
19 * MA 02110-1301 USA
20 */
21
22 /**
23 * @class Vertex, Edge, Triangle, Clustering, BinaryHeap
24 * Dynamic Delaunay clustering algorithm (see GeoTemCo paper)
25 * @author Stefan Jänicke (stjaenicke@informatik.uni-leipzig.de)
26 * @release 1.0
27 * @release date: 2012-07-27
28 * @version date: 2012-07-27
29 */
30
31 function Vertex(x, y, categories, binning) {
32 this.x = x;
33 this.y = y;
34 this.radius
35 this.size = 0;
36 this.elements = [];
37 this.radii = [];
38 this.weights = [];
39 this.legal = true;
40 this.binning = binning;
41 if (categories != undefined) {
42 for (var i = 0; i < categories; i++) {
43 this.elements.push([]);
44 this.weights.push(0);
45 }
46 }
47 }
48
49 Vertex.prototype.merge = function(v0, v1) {
50 for (var i = 0; i < v0.elements.length; i++) {
51 this.elements[i] = v0.elements[i].concat(v1.elements[i]);
52 this.weights[i] = v0.weights[i] + v1.weights[i];
53 this.size += this.weights[i];
54 }
55 }
56
57 Vertex.prototype.CalculateRadius = function(resolution) {
58 this.radii = [];
59 for (i in this.elements ) {
60 this.radii.push(this.binning.getRadius(this.weights[i]));
61 }
62 if (this.radii.length == 1) {
63 this.radius = this.radii[0] * resolution;
64 } else {
65 var count = 0;
66 var max1 = 0;
67 var max2 = 0;
68 for (i in this.radii ) {
69 if (this.radii[i] != 0) {
70 count++;
71 }
72 if (this.radii[i] > max1) {
73 if (max1 > max2) {
74 max2 = max1;
75 }
76 max1 = this.radii[i];
77 } else if (this.radii[i] > max2) {
78 max2 = this.radii[i];
79 }
80 }
81 if (count == 1) {
82 this.radius = max1 * resolution;
83 } else if (count == 2) {
84 this.radius = (max1 + max2) * resolution;
85 } else if (count == 3) {
86 var d = (2 / 3 * Math.sqrt(3) - 1) * max1;
87 this.radius = (d + max1 + max2) * resolution;
88 } else if (count == 4) {
89 var d = (Math.sqrt(2) - 1) * max2;
90 this.radius = (d + max1 + max2) * resolution;
91 }
92 }
93 }
94
95 Vertex.prototype.addElement = function(e, weight, index) {
96 this.elements[index].push(e);
97 this.size += weight;
98 this.weights[index] += weight;
99 }
100 function Edge(v0, v1) {
101 this.v0 = v0;
102 this.v1 = v1;
103 this.leftFace
104 this.rightFace
105 this.legal = true;
106 this.setLength();
107 }
108
109 Edge.prototype.setLength = function() {
110 var dx = this.v0.x - this.v1.x;
111 var dy = this.v0.y - this.v1.y;
112 this.length = Math.sqrt(dx * dx + dy * dy);
113 }
114
115 Edge.prototype.contains = function(v) {
116 if (this.v0 == v || this.v1 == v) {
117 return true;
118 }
119 return false;
120 }
121
122 Edge.prototype.replaceFace = function(f_old, f_new) {
123 if (this.leftFace == f_old) {
124 this.leftFace = f_new;
125 } else if (this.rightFace == f_old) {
126 this.rightFace = f_new;
127 }
128 }
129
130 Edge.prototype.setFace = function(f) {
131 if (f.leftOf(this)) {
132 this.leftFace = f;
133 } else {
134 this.rightFace = f;
135 }
136 }
137
138 Edge.prototype.setFaces = function(f1, f2) {
139 if (f1.leftOf(this)) {
140 this.leftFace = f1;
141 this.rightFace = f2;
142 } else {
143 this.leftFace = f2;
144 this.rightFace = f1;
145 }
146 }
147
148 Edge.prototype.removeFace = function(f) {
149 if (this.leftFace == f) {
150 this.leftFace = null;
151 } else {
152 this.rightFace = null;
153 }
154 }
155
156 Edge.prototype.equals = function(e) {
157 if (this.v0 == e.v0 && this.v1 == e.v1 || this.v0 == e.v1 && this.v1 == e.v0) {
158 return true;
159 }
160 return false;
161 }
162 function Triangle(edges) {
163 this.edges = edges;
164 this.setVertices();
165 this.descendants = [];
166 }
167
168 Triangle.prototype.getTriple = function(e) {
169 var i = arrayIndex(this.edges, e);
170 return {
171 e_s : this.edges[(i + 1) % 3],
172 e_p : this.edges[(i + 2) % 3],
173 u : this.vertices[(i + 2) % 3]
174 };
175 }
176
177 Triangle.prototype.leftOf = function(e) {
178 var i = arrayIndex(this.edges, e);
179 if (this.vertices[i].y != this.vertices[(i + 1) % 3].y) {
180 return this.vertices[i].y > this.vertices[(i + 1) % 3].y;
181 }
182 return this.vertices[i].y > this.vertices[(i + 2) % 3].y;
183 }
184
185 Triangle.prototype.getNext = function(v) {
186 var i = arrayIndex(this.vertices, v);
187 return this.vertices[(i + 1) % 3];
188 }
189
190 Triangle.prototype.oppositeEdge = function(v) {
191 var i = arrayIndex(this.vertices, v);
192 return this.edges[(i + 1) % 3];
193 }
194
195 Triangle.prototype.contains = function(v) {
196 return arrayIndex(this.vertices, v) != -1;
197 }
198
199 Triangle.prototype.replace = function(e_old, e_new) {
200 this.edges[arrayIndex(this.edges, e_old)] = e_new;
201 }
202
203 Triangle.prototype.setVertices = function() {
204 if (this.edges[1].v0 == this.edges[0].v0 || this.edges[1].v1 == this.edges[0].v0) {
205 this.vertices = [this.edges[0].v1, this.edges[0].v0];
206 } else {
207 this.vertices = [this.edges[0].v0, this.edges[0].v1];
208 }
209 if (this.edges[2].v0 == this.vertices[0]) {
210 this.vertices.push(this.edges[2].v1);
211 } else {
212 this.vertices.push(this.edges[2].v0);
213 }
214 }
215
216 Triangle.prototype.replaceBy = function(triangles) {
217 this.descendants = triangles;
218 this.edges[0].replaceFace(this, triangles[0]);
219 this.edges[1].replaceFace(this, triangles[1]);
220 this.edges[2].replaceFace(this, triangles[2]);
221 }
222
223 Triangle.prototype.CalcCircumcircle = function() {
224 var v0 = this.vertices[0];
225 var v1 = this.vertices[1];
226 var v2 = this.vertices[2];
227 var A = v1.x - v0.x;
228 var B = v1.y - v0.y;
229 var C = v2.x - v0.x;
230 var D = v2.y - v0.y;
231 var E = A * (v0.x + v1.x) + B * (v0.y + v1.y);
232 var F = C * (v0.x + v2.x) + D * (v0.y + v2.y);
233 var G = 2.0 * (A * (v2.y - v1.y) - B * (v2.x - v1.x));
234 var cx = (D * E - B * F) / G;
235 var cy = (A * F - C * E) / G;
236 this.center = new Vertex(cx, cy);
237 var dx = this.center.x - v0.x;
238 var dy = this.center.y - v0.y;
239 this.radius_squared = dx * dx + dy * dy;
240 };
241
242 Triangle.prototype.inCircumcircle = function(v) {
243 if (this.radius_squared == undefined) {
244 this.CalcCircumcircle();
245 }
246 var dx = this.center.x - v.x;
247 var dy = this.center.y - v.y;
248 var dist_squared = dx * dx + dy * dy;
249 return (dist_squared <= this.radius_squared );
250 };
251
252 Triangle.prototype.interior = function(v) {
253 var v0 = this.vertices[0];
254 var v1 = this.vertices[1];
255 var v2 = this.vertices[2];
256 var dotAB = (v.x - v0.x ) * (v0.y - v1.y ) + (v.y - v0.y ) * (v1.x - v0.x );
257 var dotBC = (v.x - v1.x ) * (v1.y - v2.y ) + (v.y - v1.y ) * (v2.x - v1.x );
258 var dotCA = (v.x - v2.x ) * (v2.y - v0.y ) + (v.y - v2.y ) * (v0.x - v2.x );
259 if (dotAB > 0 || dotBC > 0 || dotCA > 0) {
260 return null;
261 } else if (dotAB < 0 && dotBC < 0 && dotCA < 0) {
262 return this;
263 } else if (dotAB == 0) {
264 if (dotBC == 0) {
265 return this.vertices[1];
266 } else if (dotCA == 0) {
267 return this.vertices[0];
268 }
269 return this.edges[0];
270 } else if (dotBC == 0) {
271 if (dotCA == 0) {
272 return this.vertices[2];
273 }
274 return this.edges[1];
275 } else if (dotCA == 0) {
276 return this.edges[2];
277 }
278 };
279
280 function Clustering(xMin, yMin, xMax, yMax) {
281 this.triangles = [];
282 this.newTriangles = [];
283 this.bbox = {
284 x1 : xMin,
285 y1 : yMin,
286 x2 : xMax,
287 y2 : yMax
288 };
289 this.CreateBoundingTriangle();
290 this.edges = [];
291 this.vertices = [];
292 this.legalizes = 0;
293 this.collapses = 0;
294 }
295
296 Clustering.prototype.locate = function(v) {
297 if (this.boundingTriangle.descendants.length == 0) {
298 return this.boundingTriangle;
299 }
300 var triangles = this.boundingTriangle.descendants;
301 while (true) {
302 for (var i = 0; i < triangles.length; i++) {
303 var simplex = triangles[i].interior(v);
304 if (simplex == null) {
305 continue;
306 }
307 if ( simplex instanceof Vertex || this.isLeaf(triangles[i])) {
308 return simplex;
309 }
310 triangles = triangles[i].descendants;
311 break;
312 }
313 }
314 }
315
316 Clustering.prototype.legalize = function(v, e, t0_old) {
317 if (!e.v0.legal && !e.v1.legal) {
318 return;
319 }
320 this.legalizes++;
321 var flip = false;
322 var t1_old, tr1;
323 if (e.leftFace == t0_old && e.rightFace.inCircumcircle(v)) {
324 flip = true;
325 t1_old = e.rightFace;
326 } else if (e.rightFace == t0_old && e.leftFace.inCircumcircle(v)) {
327 flip = true;
328 t1_old = e.leftFace;
329 }
330 if (flip) {
331 var tr0 = t0_old.getTriple(e);
332 var tr1 = t1_old.getTriple(e);
333 var e_flip = new Edge(tr0.u, tr1.u);
334 var poly = [];
335 poly.push(e.v0);
336 poly.push(e_flip.v0);
337 poly.push(e.v1);
338 poly.push(e_flip.v1);
339 if (!this.JordanTest(poly, e_flip)) {
340 return;
341 }
342 e.legal = false;
343 this.edges.push(e_flip);
344 var t0_new = new Triangle([e_flip, tr0.e_p, tr1.e_s]);
345 var t1_new = new Triangle([e_flip, tr1.e_p, tr0.e_s]);
346 e_flip.setFaces(t0_new, t1_new);
347 tr0.e_p.replaceFace(t0_old, t0_new);
348 tr1.e_s.replaceFace(t1_old, t0_new);
349 tr1.e_p.replaceFace(t1_old, t1_new);
350 tr0.e_s.replaceFace(t0_old, t1_new);
351 t0_old.descendants = [t0_new, t1_new];
352 t1_old.descendants = [t0_new, t1_new];
353 this.legalize(v, t0_new.edges[2], t0_new);
354 this.legalize(v, t1_new.edges[1], t1_new);
355 }
356 }
357
358 Clustering.prototype.add = function(v) {
359 this.addVertex(v, this.locate(v));
360 }
361
362 Clustering.prototype.addVertex = function(v, simplex) {
363 if ( simplex instanceof Vertex) {
364 simplex.merge(simplex, v);
365 } else if ( simplex instanceof Edge) {
366 this.vertices.push(v);
367 simplex.legal = false;
368 var tr0 = simplex.leftFace.getTriple(simplex);
369 var tr1 = simplex.rightFace.getTriple(simplex);
370 var e0 = new Edge(v, tr0.u);
371 var e1 = new Edge(v, simplex.leftFace.getNext(tr0.u));
372 var e2 = new Edge(v, tr1.u);
373 var e3 = new Edge(v, simplex.rightFace.getNext(tr1.u));
374 var t0 = new Triangle([e0, tr0.e_p, e1]);
375 var t1 = new Triangle([e1, tr1.e_s, e2]);
376 var t2 = new Triangle([e2, tr1.e_p, e3]);
377 var t3 = new Triangle([e3, tr0.e_s, e0]);
378 simplex.leftFace.descendants = [t0, t3];
379 simplex.rightFace.descendants = [t1, t2];
380 this.edges.push(e0);
381 this.edges.push(e1);
382 this.edges.push(e2);
383 this.edges.push(e3);
384 e0.setFaces(t0, t3);
385 e1.setFaces(t0, t1);
386 e2.setFaces(t1, t2);
387 e3.setFaces(t2, t3);
388 tr0.e_p.replaceFace(simplex.leftFace, t0);
389 tr1.e_s.replaceFace(simplex.rightFace, t1);
390 tr1.e_p.replaceFace(simplex.rightFace, t2);
391 tr0.e_s.replaceFace(simplex.leftFace, t3);
392 this.legalize(v, tr0.e_p, t0);
393 this.legalize(v, tr1.e_s, t1);
394 this.legalize(v, tr1.e_p, t2);
395 this.legalize(v, tr0.e_s, t3);
396 } else {
397 this.vertices.push(v);
398 var e_i = new Edge(simplex.vertices[0], v);
399 var e_j = new Edge(simplex.vertices[1], v);
400 var e_k = new Edge(simplex.vertices[2], v);
401 this.edges.push(e_i);
402 this.edges.push(e_j);
403 this.edges.push(e_k);
404 var t0 = new Triangle([e_i, simplex.edges[0], e_j]);
405 var t1 = new Triangle([e_j, simplex.edges[1], e_k]);
406 var t2 = new Triangle([e_k, simplex.edges[2], e_i]);
407 e_i.setFaces(t0, t2);
408 e_j.setFaces(t0, t1);
409 e_k.setFaces(t1, t2);
410 simplex.replaceBy([t0, t1, t2]);
411 this.legalize(v, simplex.edges[0], t0);
412 this.legalize(v, simplex.edges[1], t1);
413 this.legalize(v, simplex.edges[2], t2);
414 }
415 }
416
417 Clustering.prototype.isLeaf = function(t) {
418 return t.descendants.length == 0;
419 }
420
421 Clustering.prototype.CreateBoundingTriangle = function() {
422 var dx = (this.bbox.x2 - this.bbox.x1 ) * 10;
423 var dy = (this.bbox.y2 - this.bbox.y1 ) * 10;
424 var v0 = new Vertex(this.bbox.x1 - dx, this.bbox.y1 - dy * 3);
425 var v1 = new Vertex(this.bbox.x2 + dx * 3, this.bbox.y2 + dy);
426 var v2 = new Vertex(this.bbox.x1 - dx, this.bbox.y2 + dy);
427 var e0 = new Edge(v1, v0);
428 var e1 = new Edge(v0, v2);
429 var e2 = new Edge(v2, v1);
430 v0.legal = false;
431 v1.legal = false;
432 v2.legal = false;
433 this.boundingTriangle = new Triangle([e0, e1, e2]);
434 var inf = new Triangle([e0, e1, e2]);
435 e0.setFaces(this.boundingTriangle, inf);
436 e1.setFaces(this.boundingTriangle, inf);
437 e2.setFaces(this.boundingTriangle, inf);
438 }
439
440 Clustering.prototype.mergeVertices = function(e) {
441 this.collapses++;
442 var s0 = e.v0.size;
443 var s1 = e.v1.size;
444 var x = (e.v0.x * s0 + e.v1.x * s1 ) / (s0 + s1 );
445 var y = (e.v0.y * s0 + e.v1.y * s1 ) / (s0 + s1 );
446 var v = new Vertex(x, y, e.v0.elements.length, e.v0.binning);
447 v.merge(e.v0, e.v1);
448
449 e.v0.legal = false;
450 e.v1.legal = false;
451
452 var hole = [];
453 var oldFacets = [];
454 e.legal = false;
455
456 var vertices = [];
457 var traverse = function(eLeft, eRight, triangle) {
458 eLeft.legal = false;
459 do {
460 var triple;
461 if (eLeft.leftFace == triangle) {
462 triple = eLeft.rightFace.getTriple(eLeft);
463 oldFacets.push(eLeft.rightFace);
464 triple.e_s.removeFace(eLeft.rightFace);
465 triangle = eLeft.rightFace;
466 } else {
467 triple = eLeft.leftFace.getTriple(eLeft);
468 oldFacets.push(eLeft.leftFace);
469 triple.e_s.removeFace(eLeft.leftFace);
470 triangle = eLeft.leftFace;
471 }
472 if (arrayIndex(hole, triple.e_s) == -1) {
473 hole.push(triple.e_s);
474 }
475 vertices.push(triple.u);
476 eLeft = triple.e_p;
477 eLeft.legal = false;
478 } while( eLeft != eRight );
479 }
480 var tr0 = e.leftFace.getTriple(e);
481 var tr1 = e.rightFace.getTriple(e);
482 oldFacets.push(e.leftFace);
483 oldFacets.push(e.rightFace);
484 traverse(tr0.e_p, tr1.e_s, e.leftFace);
485 traverse(tr1.e_p, tr0.e_s, e.rightFace);
486
487 var hd = new Clustering(this.bbox.x1 - 10, this.bbox.y1 - 10, this.bbox.x2 + 10, this.bbox.y2 + 10);
488 var hull = [];
489 for (var i in hole ) {
490 if (!(hole[i].leftFace == null && hole[i].rightFace == null)) {
491 hull.push(hole[i].v0);
492 hull.push(hole[i].v1);
493 }
494 }
495 var hullVertices = [];
496 var distinct = [];
497 for (var i in vertices ) {
498 if (arrayIndex(distinct, vertices[i]) == -1) {
499 hd.add(vertices[i]);
500 distinct.push(vertices[i]);
501 }
502 if (arrayIndex(hull, vertices[i]) != -1) {
503 hullVertices.push(vertices[i]);
504 }
505 }
506
507 var newFacets = [];
508 var isBoundary = function(e) {
509 for (var i = 0; i < hole.length; i++) {
510 if (hole[i].equals(e)) {
511 return i;
512 }
513 }
514 return -1;
515 }
516 var holeEdges = new Array(hole.length);
517 var nonHoleEdges = [];
518
519 for (var i = 0; i < hd.edges.length; i++) {
520 var e = hd.edges[i];
521 var b = isBoundary(e);
522 if (b != -1) {
523 if (!e.legal) {
524 var t1 = e.leftFace.getTriple(e);
525 var t2 = e.rightFace.getTriple(e);
526 var edge = new Edge(t1.u, t2.u);
527 for (var j = 0; j < hd.edges.length; j++) {
528 if (hd.edges[j].equals(edge) && hd.edges[j].legal) {
529 hd.edges[j].legal = false;
530 break;
531 }
532 }
533 t1.e_p.setFace(e.leftFace);
534 t1.e_s.setFace(e.leftFace);
535 t2.e_p.setFace(e.rightFace);
536 t2.e_s.setFace(e.rightFace);
537
538 e.legal = true;
539 }
540 holeEdges[b] = e;
541 } else {
542 nonHoleEdges.push(e);
543 }
544 }
545
546 for (var i = 0; i < holeEdges.length; i++) {
547 var e = holeEdges[i];
548 if (hole[i].leftFace == null) {
549 hole[i].leftFace = e.leftFace;
550 hole[i].leftFace.replace(e, hole[i]);
551 if (arrayIndex(newFacets, hole[i].leftFace) == -1) {
552 newFacets.push(hole[i].leftFace);
553 }
554 }
555 if (hole[i].rightFace == null) {
556 hole[i].rightFace = e.rightFace;
557 hole[i].rightFace.replace(e, hole[i]);
558 if (arrayIndex(newFacets, hole[i].rightFace) == -1) {
559 newFacets.push(hole[i].rightFace);
560 }
561 }
562 }
563
564 for (var i = 0; i < nonHoleEdges.length; i++) {
565 var e = nonHoleEdges[i];
566 if (!e.legal) {
567 continue;
568 }
569 if (this.JordanTest(hullVertices, e)) {
570 this.edges.push(e);
571 if (arrayIndex(newFacets, e.rightFace) == -1) {
572 newFacets.push(e.rightFace);
573 }
574 if (arrayIndex(newFacets, e.leftFace) == -1) {
575 newFacets.push(e.leftFace);
576 }
577 }
578 }
579
580 for (var i in oldFacets ) {
581 oldFacets[i].descendants = newFacets;
582 }
583
584 for (var i = 0; i < newFacets.length; i++) {
585 var simplex = newFacets[i].interior(v);
586 if (simplex == null) {
587 continue;
588 } else {
589 this.addVertex(v, simplex);
590 break;
591 }
592 }
593
594 return v;
595
596 }
597
598 Clustering.prototype.JordanTest = function(pol, e) {
599 var p = new Vertex((e.v0.x + e.v1.x) * 0.5, (e.v0.y + e.v1.y) * 0.5);
600 var inside = false;
601 var i, j = pol.length - 1;
602 for ( i = 0; i < pol.length; j = i++) {
603 var p1 = pol[i];
604 var p2 = pol[j];
605 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))
606 inside = !inside;
607 }
608 return inside;
609 }
610
611 Clustering.prototype.mergeForResolution = function(resolution, circleGap, circleOverlap) {
612 this.deleteEdges = new BinaryHeap(function(e) {
613 return e.weight;
614 });
615 this.weightEdges(resolution, circleGap, circleOverlap);
616 var index = 0;
617 while (this.deleteEdges.size() > 0) {
618 var e = this.deleteEdges.pop();
619 if (e.legal) {
620 var l = this.edges.length;
621 var newVertex = this.mergeVertices(e);
622 newVertex.CalculateRadius(resolution);
623 for (var k = l; k < this.edges.length; k++) {
624 var eNew = this.edges[k];
625 if (eNew.legal) {
626 if( circleGap != 0 ){
627 eNew.weight = eNew.length / (eNew.v0.radius + eNew.v1.radius + circleGap * resolution );
628 }
629 else if( circleOverlap.overlap == 0 ){
630 eNew.weight = eNew.length / (eNew.v0.radius + eNew.v1.radius);
631 }
632 else {
633 var r1 = eNew.v0.radius;
634 var r2 = eNew.v1.radius;
635 var r = eNew.length;
636 if( r < r1 + r2 ){
637 if( circleOverlap.type == 'diameter' ){
638 var ol1 = (r2-(r-r1)) / r1 / 2;
639 var ol2 = (r1-(r-r2)) / r2 / 2;
640 var ol = Math.max(ol1,ol2);
641 eNew.weight = circleOverlap.overlap / ol;
642 }
643 if( circleOverlap.type == 'area' ){
644 if( !(r+r1 < r2 || r+r2 < r1) ){
645 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));
646 var ol1 = A / (Math.PI*r1*r1);
647 var ol2 = A / (Math.PI*r2*r2);
648 var ol = Math.max(ol1,ol2);
649 eNew.weight = circleOverlap.overlap / ol;
650 }
651 else {
652 eNew.weight = 0;
653 }
654 }
655 }
656 }
657 if (eNew.weight < 1) {
658 this.deleteEdges.push(eNew);
659 }
660 }
661 }
662 }
663 }
664 }
665
666 Clustering.prototype.weightEdges = function(resolution, circleGap, circleOverlap) {
667 for (var i = 0; i < this.vertices.length; i++) {
668 if (this.vertices[i].legal) {
669 this.vertices[i].CalculateRadius(resolution);
670 }
671 }
672 var newEdges = [];
673 for (var i = 0; i < this.edges.length; i++) {
674 var e = this.edges[i];
675 if (e.legal) {
676 if (!e.v0.legal || !e.v1.legal) {
677 e.weight = 1;
678 } else {
679 if( circleGap != 0 ){
680 e.weight = e.length / (e.v0.radius + e.v1.radius + circleGap * resolution );
681 }
682 else if( circleOverlap.overlap == 0 ){
683 e.weight = e.length / (e.v0.radius + e.v1.radius);
684 }
685 else {
686 var r1 = e.v0.radius;
687 var r2 = e.v1.radius;
688 var r = e.length;
689 if( r < r1 + r2 ){
690 if( circleOverlap.type == 'diameter' ){
691 var ol1 = (r2-(r-r1)) / r1 / 2;
692 var ol2 = (r1-(r-r2)) / r2 / 2;
693 var ol = Math.max(ol1,ol2);
694 e.weight = circleOverlap.overlap / ol;
695 }
696 if( circleOverlap.type == 'area' ){
697 if( !(r+r1 < r2 || r+r2 < r1) ){
698 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));
699 var ol1 = A / (Math.PI*r1*r1);
700 var ol2 = A / (Math.PI*r2*r2);
701 var ol = Math.max(ol1,ol2);
702 e.weight = circleOverlap.overlap / ol;
703 }
704 else {
705 e.weight = 0;
706 }
707 }
708 }
709 }
710 if (e.weight < 1) {
711 this.deleteEdges.push(e);
712 }
713 }
714 newEdges.push(e);
715 }
716 }
717 this.edges = newEdges;
718 }
719
720 Clustering.prototype.ValidityTest = function() {
721 console.info("Test 1: Valid Delaunay ...");
722 /*
723 var leafs = [];
724 var triangles = this.boundingTriangle.descendants;
725 var j = 0;
726 while( triangles.length > j ){
727 var t = triangles[j];
728 if( t.taken == undefined ){
729 t.taken = true;
730 if( this.isLeaf(t) ){
731 leafs.push(t);
732 }
733 else {
734 triangles = triangles.concat(t.descendants);
735 }
736 }
737 j++;
738 }
739 console.info(" Number of Triangles: "+leafs.length);
740
741 var c = 0;
742 for( i in this.edges ){
743 if( this.edges[i].legal ){
744 c++;
745 }
746 }
747 console.info(" Number of Edges: "+c);*/
748 /*
749
750 for( var i=0; i<leafs.length; i++ ){
751 for( var j=0; j<vertices.length; j++ ){
752 if( !leafs[i].contains(vertices[j]) && leafs[i].inCircumcircle(vertices[j]) ){
753 console.info(leafs[i],vertices[j]);
754
755 }
756 }
757 }
758 */
759
760 //console.info("Test 2: Edges Facets (null) ...");
761 for (i in this.edges ) {
762 var e = this.edges[i];
763 if (e.leftFace == null || e.rightFace == null) {
764 console.info(e);
765 alert();
766 }
767 }
768
769 //console.info("Test 3: Edges Facets ...");
770 var leftOf = function(v1, v2, v) {
771 var x2 = v1.x - v2.x;
772 var x3 = v1.x - v.x;
773 var y2 = v1.y - v2.y;
774 var y3 = v1.y - v.y;
775 if (x2 * y3 - y2 * x3 < 0) {
776 return true;
777 }
778 return false;
779 }
780 var c = 0;
781 for (i in this.edges ) {
782 var e = this.edges[i];
783 var t1 = e.leftFace.getTriple(e);
784 var t2 = e.rightFace.getTriple(e);
785 if (e.v0.y == e.v1.y) {
786 if (t1.u.y > t2.u.y) {
787 console.info("equal y conflict ...");
788 console.info(e);
789 alert();
790 c++;
791 }
792 } else {
793 var v1, v2;
794 if (e.v0.y > e.v1.y) {
795 v1 = e.v0;
796 v2 = e.v1;
797 } else {
798 v1 = e.v1;
799 v2 = e.v0;
800 }
801 if (!leftOf(v1, v2, t1.u)) {
802 console.info("left right conflict ... left is right");
803 console.info(e);
804 alert();
805 c++;
806 }
807 if (leftOf(v1, v2, t2.u)) {
808 console.info("left right conflict ... right is left");
809 console.info(e);
810 alert();
811 c++;
812 }
813 }
814 }
815 //console.info("Number of Edges: "+this.edges.length);
816 //console.info("Number of Conflicts: "+c);
817
818 for (i in this.edges ) {
819 if (this.edges[i].legal) {
820 var e = this.edges[i];
821 var tr0 = e.leftFace.getTriple(e);
822 var tr1 = e.rightFace.getTriple(e);
823 if (!tr0.e_p.legal || !tr0.e_s.legal || !tr1.e_p.legal || !tr1.e_s.legal) {
824 console.info(e);
825 console.info("conflict in edge continuity");
826 return;
827 }
828 }
829 }
830
831 }
832 function BinaryHeap(scoreFunction) {
833 this.content = [];
834 this.scoreFunction = scoreFunction;
835 }
836
837 BinaryHeap.prototype = {
838 push : function(element) {
839 // Add the new element to the end of the array.
840 this.content.push(element);
841 // Allow it to bubble up.
842 this.bubbleUp(this.content.length - 1);
843 },
844
845 pop : function() {
846 // Store the first element so we can return it later.
847 var result = this.content[0];
848 // Get the element at the end of the array.
849 var end = this.content.pop();
850 // If there are any elements left, put the end element at the
851 // start, and let it sink down.
852 if (this.content.length > 0) {
853 this.content[0] = end;
854 this.sinkDown(0);
855 }
856 return result;
857 },
858
859 remove : function(node) {
860 var len = this.content.length;
861 // To remove a value, we must search through the array to find
862 // it.
863 for (var i = 0; i < len; i++) {
864 if (this.content[i] == node) {
865 // When it is found, the process seen in 'pop' is repeated
866 // to fill up the hole.
867 var end = this.content.pop();
868 if (i != len - 1) {
869 this.content[i] = end;
870 if (this.scoreFunction(end) < this.scoreFunction(node))
871 this.bubbleUp(i);
872 else
873 this.sinkDown(i);
874 }
875 return;
876 }
877 }
878 throw new Error("Node not found.");
879 },
880
881 size : function() {
882 return this.content.length;
883 },
884
885 bubbleUp : function(n) {
886 // Fetch the element that has to be moved.
887 var element = this.content[n];
888 // When at 0, an element can not go up any further.
889 while (n > 0) {
890 // Compute the parent element's index, and fetch it.
891 var parentN = Math.floor((n + 1) / 2) - 1, parent = this.content[parentN];
892 // Swap the elements if the parent is greater.
893 if (this.scoreFunction(element) < this.scoreFunction(parent)) {
894 this.content[parentN] = element;
895 this.content[n] = parent;
896 // Update 'n' to continue at the new position.
897 n = parentN;
898
899 }
900 // Found a parent that is less, no need to move it further.
901 else {
902 break;
903 }
904 }
905 },
906
907 sinkDown : function(n) {
908 // Look up the target element and its score.
909 var length = this.content.length, element = this.content[n], elemScore = this.scoreFunction(element);
910
911 while (true) {
912 // Compute the indices of the child elements.
913 var child2N = (n + 1) * 2, child1N = child2N - 1;
914 // This is used to store the new position of the element,
915 // if any.
916 var swap = null;
917 // If the first child exists (is inside the array)...
918 if (child1N < length) {
919 // Look it up and compute its score.
920 var child1 = this.content[child1N], child1Score = this.scoreFunction(child1);
921 // If the score is less than our element's, we need to swap.
922 if (child1Score < elemScore)
923 swap = child1N;
924 }
925 // Do the same checks for the other child.
926 if (child2N < length) {
927 var child2 = this.content[child2N], child2Score = this.scoreFunction(child2);
928 if (child2Score < (swap == null ? elemScore : child1Score))
929 swap = child2N;
930 }
931
932 // If the element needs to be moved, swap it, and continue.
933 if (swap != null) {
934 this.content[n] = this.content[swap];
935 this.content[swap] = element;
936 n = swap;
937 }
938 // Otherwise, we are done.
939 else {
940 break;
941 }
942 }
943 }
944 };