1'use strict'; 2 3// module.exports = earcut; 4 5function earcut(data, holeIndices, dim) { 6 7 dim = dim || 2; 8 9 var hasHoles = holeIndices && holeIndices.length, 10 outerLen = hasHoles ? holeIndices[0] * dim : data.length, 11 outerNode = linkedList(data, 0, outerLen, dim, true), 12 triangles = []; 13 14 if (!outerNode) return triangles; 15 16 var minX, minY, maxX, maxY, x, y, size; 17 18 if (hasHoles) outerNode = eliminateHoles(data, holeIndices, outerNode, dim); 19 20 // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox 21 if (data.length > 80 * dim) { 22 minX = maxX = data[0]; 23 minY = maxY = data[1]; 24 25 for (var i = dim; i < outerLen; i += dim) { 26 x = data[i]; 27 y = data[i + 1]; 28 if (x < minX) minX = x; 29 if (y < minY) minY = y; 30 if (x > maxX) maxX = x; 31 if (y > maxY) maxY = y; 32 } 33 34 // minX, minY and size are later used to transform coords into integers for z-order calculation 35 size = Math.max(maxX - minX, maxY - minY); 36 } 37 38 earcutLinked(outerNode, triangles, dim, minX, minY, size); 39 40 return triangles; 41} 42 43// create a circular doubly linked list from polygon points in the specified winding order 44function linkedList(data, start, end, dim, clockwise) { 45 var i, last; 46 47 if (clockwise === (signedArea(data, start, end, dim) > 0)) { 48 for (i = start; i < end; i += dim) last = insertNode(i, data[i], data[i + 1], last); 49 } else { 50 for (i = end - dim; i >= start; i -= dim) last = insertNode(i, data[i], data[i + 1], last); 51 } 52 53 if (last && equals(last, last.next)) { 54 removeNode(last); 55 last = last.next; 56 } 57 58 return last; 59} 60 61// eliminate colinear or duplicate points 62function filterPoints(start, end) { 63 if (!start) return start; 64 if (!end) end = start; 65 66 var p = start, 67 again; 68 do { 69 again = false; 70 71 if (!p.steiner && (equals(p, p.next) || area(p.prev, p, p.next) === 0)) { 72 removeNode(p); 73 p = end = p.prev; 74 if (p === p.next) return null; 75 again = true; 76 77 } else { 78 p = p.next; 79 } 80 } while (again || p !== end); 81 82 return end; 83} 84 85// main ear slicing loop which triangulates a polygon (given as a linked list) 86function earcutLinked(ear, triangles, dim, minX, minY, size, pass) { 87 if (!ear) return; 88 89 // interlink polygon nodes in z-order 90 if (!pass && size) indexCurve(ear, minX, minY, size); 91 92 var stop = ear, 93 prev, next; 94 95 // iterate through ears, slicing them one by one 96 while (ear.prev !== ear.next) { 97 prev = ear.prev; 98 next = ear.next; 99 100 if (size ? isEarHashed(ear, minX, minY, size) : isEar(ear)) { 101 // cut off the triangle 102 triangles.push(prev.i / dim); 103 triangles.push(ear.i / dim); 104 triangles.push(next.i / dim); 105 106 removeNode(ear); 107 108 // skipping the next vertice leads to less sliver triangles 109 ear = next.next; 110 stop = next.next; 111 112 continue; 113 } 114 115 ear = next; 116 117 // if we looped through the whole remaining polygon and can't find any more ears 118 if (ear === stop) { 119 // try filtering points and slicing again 120 if (!pass) { 121 earcutLinked(filterPoints(ear), triangles, dim, minX, minY, size, 1); 122 123 // if this didn't work, try curing all small self-intersections locally 124 } else if (pass === 1) { 125 ear = cureLocalIntersections(ear, triangles, dim); 126 earcutLinked(ear, triangles, dim, minX, minY, size, 2); 127 128 // as a last resort, try splitting the remaining polygon into two 129 } else if (pass === 2) { 130 splitEarcut(ear, triangles, dim, minX, minY, size); 131 } 132 133 break; 134 } 135 } 136} 137 138// check whether a polygon node forms a valid ear with adjacent nodes 139function isEar(ear) { 140 var a = ear.prev, 141 b = ear, 142 c = ear.next; 143 144 if (area(a, b, c) >= 0) return false; // reflex, can't be an ear 145 146 // now make sure we don't have other points inside the potential ear 147 var p = ear.next.next; 148 149 while (p !== ear.prev) { 150 if (pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) && 151 area(p.prev, p, p.next) >= 0) return false;
152 p = p.next; 153 } 154 155 return true; 156} 157 158function isEarHashed(ear, minX, minY, size) { 159 var a = ear.prev, 160 b = ear, 161 c = ear.next; 162 163 if (area(a, b, c) >= 0) return false; // reflex, can't be an ear 164 165 // triangle bbox; min & max are calculated like this for speed 166 var minTX = a.x < b.x ? (a.x < c.x ? a.x : c.x) : (b.x < c.x ? b.x : c.x), 167 minTY = a.y < b.y ? (a.y < c.y ? a.y : c.y) : (b.y < c.y ? b.y : c.y), 168 maxTX = a.x > b.x ? (a.x > c.x ? a.x : c.x) : (b.x > c.x ? b.x : c.x), 169 maxTY = a.y > b.y ? (a.y > c.y ? a.y : c.y) : (b.y > c.y ? b.y : c.y); 170 171 // z-order range for the current triangle bbox; 172 var minZ = zOrder(minTX, minTY, minX, minY, size), 173 maxZ = zOrder(maxTX, maxTY, minX, minY, size); 174 175 // first look for points inside the triangle in increasing z-order 176 var p = ear.nextZ; 177 178 while (p && p.z <= maxZ) { 179 if (p !== ear.prev && p !== ear.next && 180 pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) && 181 area(p.prev, p, p.next) >= 0) return false; 182 p = p.nextZ; 183 } 184 185 // then look for points in decreasing z-order 186 p = ear.prevZ; 187 188 while (p && p.z >= minZ) { 189 if (p !== ear.prev && p !== ear.next && 190 pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) && 191 area(p.prev, p, p.next) >= 0) return false; 192 p = p.prevZ; 193 } 194 195 return true; 196} 197 198// go through all polygon nodes and cure small local self-intersections 199function cureLocalIntersections(start, triangles, dim) { 200 var p = start; 201 do { 202 var a = p.prev, 203 b = p.next.next; 204 205 if (!equals(a, b) && intersects(a, p, p.next, b) && locallyInside(a, b) && locallyInside(b, a)) { 206 207 triangles.push(a.i / dim); 208 triangles.push(p.i / dim); 209 triangles.push(b.i / dim); 210 211 // remove two nodes involved 212 removeNode(p); 213 removeNode(p.next); 214 215 p = start = b; 216 } 217 p = p.next; 218 } while (p !== start); 219 220 return p; 221} 222 223// try splitting polygon into two and triangulate them independently 224function splitEarcut(start, triangles, dim, minX, minY, size) { 225 // look for a valid diagonal that divides the polygon into two 226 var a = start; 227 do { 228 var b = a.next.next; 229 while (b !== a.prev) { 230 if (a.i !== b.i && isValidDiagonal(a, b)) { 231 // split the polygon in two by the diagonal 232 var c = splitPolygon(a, b); 233 234 // filter colinear points around the cuts 235 a = filterPoints(a, a.next); 236 c = filterPoints(c, c.next); 237 238 // run earcut on each half 239 earcutLinked(a, triangles, dim, minX, minY, size); 240 earcutLinked(c, triangles, dim, minX, minY, size); 241 return; 242 } 243 b = b.next; 244 } 245 a = a.next; 246 } while (a !== start); 247} 248 249// link every hole into the outer loop, producing a single-ring polygon without holes 250function eliminateHoles(data, holeIndices, outerNode, dim) { 251 var queue = [], 252 i, len, start, end, list; 253 254 for (i = 0, len = holeIndices.length; i < len; i++) { 255 start = holeIndices[i] * dim; 256 end = i < len - 1 ? holeIndices[i + 1] * dim : data.length; 257 list = linkedList(data, start, end, dim, false); 258 if (list === list.next) list.steiner = true; 259 queue.push(getLeftmost(list)); 260 } 261 262 queue.sort(compareX); 263 264 // process holes from left to right 265 for (i = 0; i < queue.length; i++) { 266 eliminateHole(queue[i], outerNode); 267 outerNode = filterPoints(outerNode, outerNode.next); 268 } 269 270 return outerNode; 271} 272 273function compareX(a, b) { 274 return a.x - b.x; 275} 276 277// find a bridge between vertices that connects hole with an outer ring and and link it 278function eliminateHole(hole, outerNode) { 279 outerNode = findHoleBridge(hole, outerNode); 280 if (outerNode) { 281 var b = splitPolygon(outerNode, hole); 282 filterPoints(b, b.next); 283 } 284} 285 286// David Eberly's algorithm for finding a bridge between hole and outer polygon 287function findHoleBridge(hole, outerNode) { 288 var p = outerNode, 289 hx = hole.x, 290 hy = hole.y, 291 qx = -Infinity, 292 m; 293 294 // find a segment intersected by a ray from the hole's leftmost point to the left; 295 // segment's endpoint with lesser x will be potential connection point 296 do { 297 if (hy <= p.y && hy >= p.next.y && p.next.y !== p.y) { 298 var x = p.x + (hy - p.y) * (p.next.x - p.x) / (p.next.y - p.y); 299 if (x <= hx && x > qx) { 300 qx = x; 301 if (x === hx) { 302 if (hy === p.y) return p; 303 if (hy === p.next.y) return p.next; 304 } 305 m = p.x < p.next.x ? p : p.next; 306 } 307 } 308 p = p.next; 309 } while (p !== outerNode); 310 311 if (!m) return null; 312 313 if (hx === qx) return m.prev; // hole touches outer segment; pick lower endpoint 314 315 // look for points inside the triangle of hole point, segment intersection and endpoint; 316 // if there are no points found, we have a valid connection; 317 // otherwise choose the point of the minimum angle with the ray as connection point 318 319 var stop = m, 320 mx = m.x, 321 my = m.y, 322 tanMin = Infinity, 323 tan; 324 325 p = m.next; 326 327 while (p !== stop) { 328 if (hx >= p.x && p.x >= mx && hx !== p.x && 329 pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p.x, p.y)) { 330 331 tan = Math.abs(hy - p.y) / (hx - p.x); // tangential 332 333 if ((tan < tanMin || (tan === tanMin && p.x > m.x)) && locallyInside(p, hole)) { 334 m = p; 335 tanMin = tan; 336 } 337 } 338 339 p = p.next; 340 } 341 342 return m; 343} 344 345// interlink polygon nodes in z-order 346function indexCurve(start, minX, minY, size) { 347 var p = start; 348 do { 349 if (p.z === null) p.z = zOrder(p.x, p.y, minX, minY, size); 350 p.prevZ = p.prev; 351 p.nextZ = p.next; 352 p = p.next; 353 } while (p !== start); 354 355 p.prevZ.nextZ = null; 356 p.prevZ = null; 357 358 sortLinked(p); 359} 360 361// Simon Tatham's linked list merge sort algorithm 362// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html 363function sortLinked(list) { 364 var i, p, q, e, tail, numMerges, pSize, qSize, 365 inSize = 1; 366 367 do { 368 p = list; 369 list = null; 370 tail = null; 371 numMerges = 0; 372 373 while (p) { 374 numMerges++; 375 q = p; 376 pSize = 0; 377 for (i = 0; i < inSize; i++) { 378 pSize++; 379 q = q.nextZ; 380 if (!q) break; 381 } 382 383 qSize = inSize; 384 385 while (pSize > 0 || (qSize > 0 && q)) { 386 387 if (pSize === 0) { 388 e = q; 389 q = q.nextZ; 390 qSize--; 391 } else if (qSize === 0 || !q) { 392 e = p; 393 p = p.nextZ; 394 pSize--; 395 } else if (p.z <= q.z) { 396 e = p; 397 p = p.nextZ; 398 pSize--; 399 } else { 400 e = q; 401 q = q.nextZ; 402 qSize--; 403 } 404 405 if (tail) tail.nextZ = e; 406 else list = e; 407 408 e.prevZ = tail; 409 tail = e; 410 } 411 412 p = q; 413 } 414 415 tail.nextZ = null; 416 inSize *= 2; 417 418 } while (numMerges > 1); 419 420 return list; 421} 422 423// z-order of a point given coords and size of the data bounding box 424function zOrder(x, y, minX, minY, size) { 425 // coords are transformed into non-negative 15-bit integer range 426 x = 32767 * (x - minX) / size; 427 y = 32767 * (y - minY) / size; 428 429 x = (x | (x << 8)) & 0x00FF00FF; 430 x = (x | (x << 4)) & 0x0F0F0F0F; 431 x = (x | (x << 2)) & 0x33333333; 432 x = (x | (x << 1)) & 0x55555555; 433 434 y = (y | (y << 8)) & 0x00FF00FF; 435 y = (y | (y << 4)) & 0x0F0F0F0F; 436 y = (y | (y << 2)) & 0x33333333; 437 y = (y | (y << 1)) & 0x55555555; 438 439 return x | (y << 1); 440} 441 442// find the leftmost node of a polygon ring 443function getLeftmost(start) { 444 var p = start, 445 leftmost = start; 446 do { 447 if (p.x < leftmost.x) leftmost = p; 448 p = p.next; 449 } while (p !== start); 450 451 return leftmost; 452} 453 454// check if a point lies within a convex triangle 455function pointInTriangle(ax, ay, bx, by, cx, cy, px, py) { 456 return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 && 457 (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 && 458 (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0; 459} 460 461// check if a diagonal between two polygon nodes is valid (lies in polygon interior) 462function isValidDiagonal(a, b) { 463 return a.next.i !== b.i && a.prev.i !== b.i && !intersectsPolygon(a, b) && 464 locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b); 465} 466 467// signed area of a triangle 468function area(p, q, r) { 469 return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); 470} 471 472// check if two points are equal 473function equals(p1, p2) { 474 return p1.x === p2.x && p1.y === p2.y; 475} 476 477// check if two segments intersect
478function intersects(p1, q1, p2, q2) { 479 if ((equals(p1, q1) && equals(p2, q2)) || 480 (equals(p1, q2) && equals(p2, q1))) return true; 481 return area(p1, q1, p2) > 0 !== area(p1, q1, q2) > 0 && 482 area(p2, q2, p1) > 0 !== area(p2, q2, q1) > 0; 483} 484 485// check if a polygon diagonal intersects any polygon segments 486function intersectsPolygon(a, b) { 487 var p = a; 488 do { 489 if (p.i !== a.i && p.next.i !== a.i && p.i !== b.i && p.next.i !== b.i && 490 intersects(p, p.next, a, b)) return true; 491 p = p.next; 492 } while (p !== a); 493 494 return false; 495} 496 497// check if a polygon diagonal is locally inside the polygon 498function locallyInside(a, b) { 499 return area(a.prev, a, a.next) < 0 ? 500 area(a, b, a.next) >= 0 && area(a, a.prev, b) >= 0 : 501 area(a, b, a.prev) < 0 || area(a, a.next, b) < 0; 502} 503 504// check if the middle point of a polygon diagonal is inside the polygon 505function middleInside(a, b) { 506 var p = a, 507 inside = false, 508 px = (a.x + b.x) / 2, 509 py = (a.y + b.y) / 2; 510 do { 511 if (((p.y > py) !== (p.next.y > py)) && p.next.y !== p.y && 512 (px < (p.next.x - p.x) * (py - p.y) / (p.next.y - p.y) + p.x)) 513 inside = !inside; 514 p = p.next; 515 } while (p !== a); 516 517 return inside; 518} 519 520// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits polygon into two; 521// if one belongs to the outer ring and another to a hole, it merges it into a single ring 522function splitPolygon(a, b) { 523 var a2 = new EarNode(a.i, a.x, a.y), 524 b2 = new EarNode(b.i, b.x, b.y), 525 an = a.next, 526 bp = b.prev; 527 528 a.next = b; 529 b.prev = a; 530 531 a2.next = an; 532 an.prev = a2; 533 534 b2.next = a2; 535 a2.prev = b2; 536 537 bp.next = b2; 538 b2.prev = bp; 539 540 return b2; 541} 542 543// create a node and optionally link it with previous one (in a circular doubly linked list) 544function insertNode(i, x, y, last) { 545 var p = new EarNode(i, x, y); 546 547 if (!last) { 548 p.prev = p; 549 p.next = p; 550 551 } else { 552 p.next = last.next; 553 p.prev = last; 554 last.next.prev = p; 555 last.next = p; 556 } 557 return p; 558} 559 560function removeNode(p) { 561 p.next.prev = p.prev; 562 p.prev.next = p.next; 563 564 if (p.prevZ) p.prevZ.nextZ = p.nextZ; 565 if (p.nextZ) p.nextZ.prevZ = p.prevZ; 566} 567 568function EarNode(i, x, y) { 569 // vertice index in coordinates array 570 this.i = i; 571 572 // vertex coordinates 573 this.x = x; 574 this.y = y; 575 576 // previous and next vertice nodes in a polygon ring 577 this.prev = null; 578 this.next = null; 579 580 // z-order curve value 581 this.z = null; 582 583 // previous and next nodes in z-order 584 this.prevZ = null; 585 this.nextZ = null; 586 587 // indicates whether this is a steiner point 588 this.steiner = false; 589} 590 591// return a percentage difference between the polygon area and its triangulation area; 592// used to verify correctness of triangulation 593earcut.deviation = function (data, holeIndices, dim, triangles) { 594 var hasHoles = holeIndices && holeIndices.length; 595 var outerLen = hasHoles ? holeIndices[0] * dim : data.length; 596 597 var polygonArea = Math.abs(signedArea(data, 0, outerLen, dim)); 598 if (hasHoles) { 599 for (var i = 0, len = holeIndices.length; i < len; i++) { 600 var start = holeIndices[i] * dim; 601 var end = i < len - 1 ? holeIndices[i + 1] * dim : data.length; 602 polygonArea -= Math.abs(signedArea(data, start, end, dim)); 603 } 604 } 605 606 var trianglesArea = 0; 607 for (i = 0; i < triangles.length; i += 3) { 608 var a = triangles[i] * dim; 609 var b = triangles[i + 1] * dim; 610 var c = triangles[i + 2] * dim; 611 trianglesArea += Math.abs( 612 (data[a] - data[c]) * (data[b + 1] - data[a + 1]) - 613 (data[a] - data[b]) * (data[c + 1] - data[a + 1])); 614 } 615 616 return polygonArea === 0 && trianglesArea === 0 ? 0 : 617 Math.abs((trianglesArea - polygonArea) / polygonArea); 618}; 619 620function signedArea(data, start, end, dim) { 621 var sum = 0; 622 for (var i = start, j = end - dim; i < end; i += dim) { 623 sum += (data[j] - data[i]) * (data[i + 1] + data[j + 1]); 624 j = i; 625 } 626 return sum; 627} 628 629// turn a polygon in a multi-dimensional array form (e.g. as in GeoJSON) into a form Earcut accepts 630earcut.flatten = function (data) { 631 var dim = data[0][0].length, 632 result = {vertices: [], holes: [], dimensions: dim}, 633 holeIndex = 0; 634 635 for (var i = 0; i < data.length; i++) { 636 for (var j = 0; j < data[i].length; j++) { 637 for (var d = 0; d < dim; d++) result.vertices.push(data[i][j][d]); 638 } 639 if (i > 0) { 640 holeIndex += data[i - 1].length; 641 result.holes.push(holeIndex); 642 } 643 } 644 return result; 645};
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.