Mercurial > hg > extraction-interface

annotate geotemco/js/Map/Clustering.js @ 29:fc7342914cdf

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