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