1// from https://github.com/mapbox/delaunator 2 3module.exports = Delaunator; 4 5function Delaunator(points, getX, getY) { 6 7 if (!getX) getX = defaultGetX; 8 if (!getY) getY = defaultGetY; 9 10 var minX = Infinity; 11 var minY = Infinity; 12 var maxX = -Infinity; 13 var maxY = -Infinity; 14 15 var coords = this.coords = []; 16 var ids = this.ids = new Uint32Array(points.length); 17 18 for (var i = 0; i < points.length; i++) { 19 var p = points[i]; 20 var x = getX(p); 21 var y = getY(p); 22 ids[i] = i; 23 coords[2 * i] = x; 24 coords[2 * i + 1] = y; 25 if (x < minX) minX = x; 26 if (y < minY) minY = y; 27 if (x > maxX) maxX = x; 28 if (y > maxY) maxY = y; 29 } 30 31 var cx = (minX + maxX) / 2; 32 var cy = (minY + maxY) / 2; 33 34 var minDist = Infinity; 35 var i0, i1, i2; 36 37 // pick a seed point close to the centroid 38 for (i = 0; i < points.length; i++) { 39 var d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]); 40 if (d < minDist) { 41 i0 = i; 42 minDist = d; 43 } 44 } 45 46 minDist = Infinity; 47 48 // find the point closest to the seed 49 for (i = 0; i < points.length; i++) { 50 if (i === i0) continue; 51 d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]); 52 if (d < minDist && d > 0) { 53 i1 = i; 54 minDist = d; 55 } 56 } 57 58 var minRadius = Infinity; 59 60 // find the third point which forms the smallest circumcircle with the first two 61 for (i = 0; i < points.length; i++) { 62 if (i === i0 || i === i1) continue; 63 64 var r = circumradius( 65 coords[2 * i0], coords[2 * i0 + 1], 66 coords[2 * i1], coords[2 * i1 + 1], 67 coords[2 * i], coords[2 * i + 1]); 68 69 if (r < minRadius) { 70 i2 = i; 71 minRadius = r; 72 } 73 } 74 75 if (minRadius === Infinity) { 76 throw new Error('No Delaunay triangulation exists for this input.'); 77 } 78 79 // swap the order of the seed points for counter-clockwise orientation 80 if (area(coords[2 * i0], coords[2 * i0 + 1], 81 coords[2 * i1], coords[2 * i1 + 1], 82 coords[2 * i2], coords[2 * i2 + 1]) < 0) { 83 84 var tmp = i1; 85 i1 = i2; 86 i2 = tmp; 87 } 88 89 var i0x = coords[2 * i0]; 90 var i0y = coords[2 * i0 + 1]; 91 var i1x = coords[2 * i1]; 92 var i1y = coords[2 * i1 + 1]; 93 var i2x = coords[2 * i2]; 94 var i2y = coords[2 * i2 + 1]; 95 96 var center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y); 97 98 // sort the points by distance from the seed triangle circumcenter 99 quicksort(ids, coords, 0, ids.length - 1, center.x, center.y); 100 101 // initialize a circular doubly-linked list that will hold an advancing convex hull 102 this.hull = insertNode(coords, i0); 103 this.hull.t = 0; 104 this.hull = insertNode(coords, i1, this.hull); 105 this.hull.t = 1; 106 this.hull = insertNode(coords, i2, this.hull); 107 this.hull.t = 2; 108 109 var maxTriangles = 2 * points.length - 5; 110 var triangles = this.triangles = new Uint32Array(maxTriangles * 3); 111 triangles[0] = i0; 112 triangles[1] = i1; 113 triangles[2] = i2; 114 this.trianglesLen = 3; 115 116 var adjacent = this.adjacent = new Int32Array(maxTriangles * 3); 117 adjacent[0] = -1; 118 adjacent[1] = -1; 119 adjacent[2] = -1; 120 121 var xp, yp; 122 for (var k = 0; k < ids.length; k++) { 123 i = ids[k]; 124 x = coords[2 * i]; 125 y = coords[2 * i + 1]; 126 127 // skip duplicate points 128 if (x === xp && y === yp) continue; 129 xp = x; 130 yp = y; 131 132 // skip seed triangle points 133 if ((x === i0x && y === i0y) || 134 (x === i1x && y === i1y) || 135 (x === i2x && y === i2y)) continue; 136 137 // find a visible edge on the convex hull 138 var e = this.hull; 139 while (area(x, y, e.x, e.y, e.next.x, e.next.y) >= 0) { 140 e = e.next; 141 if (e === this.hull) { 142 throw new Error('Something is wrong with the input points.'); 143 } 144 } 145 var walkBack = e === this.hull; 146 147 // add the first triangle from the point 148 var t = this._addTriangle(i, e); 149 adjacent[t] = -1; 150 adjacent[t + 1] = -1; 151 this._link(t + 2, e.t); 152 153 e.t = t; // keep track of boundary triangles on the hull
154 e = insertNode(coords, i, e); 155 156 // recursively flip triangles from the point until they satisfy the Delaunay condition 157 e.t = this._legalize(t + 2); 158 159 // walk forward through the hull, adding more triangles and flipping recursively 160 var q = e.next; 161 while (area(x, y, q.x, q.y, q.next.x, q.next.y) < 0) { 162 163 t = this._addTriangle(i, q); 164 this._link(t, q.prev.t); 165 adjacent[t + 1] = -1; 166 this._link(t + 2, q.t); 167 168 q.prev.t = this._legalize(t + 2); 169 170 this.hull = removeNode(q); 171 q = q.next; 172 } 173 174 if (!walkBack) continue; 175 176 // walk backward from the other side, adding more triangles and flipping 177 q = e.prev; 178 while (area(x, y, q.prev.x, q.prev.y, q.x, q.y) < 0) { 179 180 t = this._addTriangle(i, q.prev); 181 adjacent[t] = -1; 182 this._link(t + 1, q.t); 183 this._link(t + 2, q.prev.t); 184 185 this._legalize(t + 2); 186 187 q.prev.t = t; 188 this.hull = removeNode(q); 189 q = q.prev; 190 } 191 } 192 193 // trim typed triangle mesh arrays 194 this.triangles = triangles.subarray(0, this.trianglesLen); 195 this.adjacent = adjacent.subarray(0, this.trianglesLen); 196} 197 198Delaunator.prototype = { 199 200 _legalize: function (a) { 201 var triangles = this.triangles; 202 var coords = this.coords; 203 var adjacent = this.adjacent; 204 205 var b = adjacent[a]; 206 207 var a0 = a - a % 3; 208 var b0 = b - b % 3; 209 210 var al = a0 + (a + 1) % 3; 211 var ar = a0 + (a + 2) % 3; 212 var br = b0 + (b + 1) % 3; 213 var bl = b0 + (b + 2) % 3; 214 215 var p0 = triangles[ar]; 216 var pr = triangles[a]; 217 var pl = triangles[al]; 218 var p1 = triangles[bl]; 219 220 var illegal = inCircle( 221 coords[2 * p0], coords[2 * p0 + 1], 222 coords[2 * pr], coords[2 * pr + 1], 223 coords[2 * pl], coords[2 * pl + 1], 224 coords[2 * p1], coords[2 * p1 + 1]); 225 226 if (illegal) { 227 triangles[a] = p1; 228 triangles[b] = p0; 229 230 this._link(a, adjacent[bl]); 231 this._link(b, adjacent[ar]); 232 this._link(ar, bl); 233 234 this._legalize(a); 235 return this._legalize(br); 236 } 237 238 return ar; 239 }, 240 241 _link: function (a, b) { 242 this.adjacent[a] = b; 243 if (b !== -1) this.adjacent[b] = a; 244 }, 245 246 _addTriangle(i, e) { 247 var t = this.trianglesLen; 248 this.triangles[t] = e.i; 249 this.triangles[t + 1] = i; 250 this.triangles[t + 2] = e.next.i; 251 this.trianglesLen += 3; 252 return t; 253 } 254}; 255 256function dist(ax, ay, bx, by) { 257 var dx = ax - bx; 258 var dy = ay - by; 259 return dx * dx + dy * dy; 260} 261 262function area(px, py, qx, qy, rx, ry) { 263 return (qy - py) * (rx - qx) - (qx - px) * (ry - qy); 264} 265 266function inCircle(ax, ay, bx, by, cx, cy, px, py) { 267 ax -= px; 268 ay -= py; 269 bx -= px; 270 by -= py; 271 cx -= px; 272 cy -= py; 273 274 var ap = ax * ax + ay * ay; 275 var bp = bx * bx + by * by; 276 var cp = cx * cx + cy * cy; 277 278 var det = ax * (by * cp - bp * cy) - 279 ay * (bx * cp - bp * cx) + 280 ap * (bx * cy - by * cx); 281 282 return det < 0; 283} 284 285function circumradius(ax, ay, bx, by, cx, cy) { 286 bx -= ax; 287 by -= ay; 288 cx -= ax; 289 cy -= ay; 290 291 var bl = bx * bx + by * by; 292 var cl = cx * cx + cy * cy; 293 294 if (bl === 0 || cl === 0) return Infinity; 295 296 var d = bx * cy - by * cx; 297 if (d === 0) return Infinity; 298 299 var x = (cy * bl - by * cl) * 0.5 / d; 300 var y = (bx * cl - cx * bl) * 0.5 / d; 301 302 return x * x + y * y; 303} 304 305function circumcenter(ax, ay, bx, by, cx, cy) { 306 bx -= ax; 307 by -= ay; 308 cx -= ax; 309 cy -= ay; 310 311 var bl = bx * bx + by * by; 312 var cl = cx * cx + cy * cy; 313 314 var d = bx * cy - by * cx; 315 316 var x = (cy * bl - by * cl) * 0.5 / d; 317 var y = (bx * cl - cx * bl) * 0.5 / d; 318 319 return { 320 x: ax + x, 321 y: ay + y 322 }; 323} 324 325// create a new node in a doubly linked list 326function insertNode(coords, i, prev) { 327 var node = { 328 i: i, 329 x: coords[2 * i], 330 y: coords[2 * i + 1], 331 t: 0, 332 prev: null, 333 next: null 334 }; 335 336 if (!prev) { 337 node.prev = node; 338 node.next = node; 339 340 } else { 341 node.next = prev.next; 342 node.prev = prev; 343 prev.next.prev = node; 344 prev.next = node; 345 } 346 return node; 347} 348 349function removeNode(node) { 350 node.prev.next = node.next; 351 node.next.prev = node.prev; 352 return node.prev; 353} 354 355function quicksort(ids, coords, left, right, cx, cy) { 356 var i, j, temp; 357 358 if (right - left <= 20) { 359 for (i = left + 1; i <= right; i++) { 360 temp = ids[i];
361 j = i - 1; 362 while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) ids[j + 1] = ids[j--]; 363 ids[j + 1] = temp; 364 } 365 } else { 366 var median = (left + right) >> 1; 367 i = left + 1; 368 j = right; 369 swap(ids, median, i); 370 if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right); 371 if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right); 372 if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i); 373 374 temp = ids[i]; 375 while (true) { 376 do i++; while (compare(coords, ids[i], temp, cx, cy) < 0); 377 do j--; while (compare(coords, ids[j], temp, cx, cy) > 0); 378 if (j < i) break; 379 swap(ids, i, j); 380 } 381 ids[left + 1] = ids[j]; 382 ids[j] = temp; 383 384 if (right - i + 1 >= j - left) { 385 quicksort(ids, coords, i, right, cx, cy); 386 quicksort(ids, coords, left, j - 1, cx, cy); 387 } else { 388 quicksort(ids, coords, left, j - 1, cx, cy); 389 quicksort(ids, coords, i, right, cx, cy); 390 } 391 } 392} 393 394function compare(coords, i, j, cx, cy) { 395 var d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy); 396 var d2 = dist(coords[2 * j], coords[2 * j + 1], cx, cy); 397 return (d1 - d2) || (coords[2 * i] - coords[2 * j]) || (coords[2 * i + 1] - coords[2 * j + 1]); 398} 399 400function swap(arr, i, j) { 401 var tmp = arr[i]; 402 arr[i] = arr[j]; 403 arr[j] = tmp; 404} 405 406function defaultGetX(p) { 407 return p[0]; 408} 409function defaultGetY(p) { 410 return p[1]; 411}
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.