🚀 Socket Launch Week Day 5:Introducing Repository Access Permissions and Custom Roles.Learn more →
Sign In

earcut

Package Overview
Dependencies
Maintainers
29
Versions
45
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

earcut - npm Package Compare versions

Comparing version
3.1.0
 to
3.1.1
+104
-117
dist/earcut.dev.js

@@ -28,2 +28,6 @@ (function (global, factory) {

// set by filterPoints whenever it removes at least one node; read by earcutLinked's stall
// handler to decide whether another clip pass is worth attempting before the costlier stages
let filteredOut = false;
/**

@@ -52,7 +56,3 @@ * Triangulate a polygon given as a flat array of vertex coordinates.

if (hasHoles) {
outerNode = eliminateHoles(data, holeIndices, outerNode, dim);
// collapse collinear/coincident points across the whole merged ring once before clipping
outerNode = filterPoints(outerNode);
}
if (hasHoles) outerNode = eliminateHoles(data, holeIndices, outerNode, dim);

@@ -80,3 +80,3 @@ // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox

earcutLinked(outerNode, triangles, dim, minX, minY, invSize, 0);
earcutLinked(outerNode, triangles, minX, minY, invSize);

@@ -121,2 +121,3 @@ return triangles;

if (full || p === end) end = p.prev; // pull the stop bound back past the removal
filteredOut = true;
removeNode(p);

@@ -135,10 +136,8 @@ p = p.prev; // re-check the predecessor

// main ear slicing loop which triangulates a polygon (given as a linked list)
/** @param {Node | null} ear @param {number[]} triangles @param {number} dim @param {number} minX @param {number} minY @param {number} invSize @param {number} pass */
function earcutLinked(ear, triangles, dim, minX, minY, invSize, pass) {
if (!ear) return;
/** @param {Node} ear @param {number[]} triangles @param {number} minX @param {number} minY @param {number} invSize */
function earcutLinked(ear, triangles, minX, minY, invSize) {
// interlink polygon nodes in z-order
if (!pass && invSize) indexCurve(ear, minX, minY, invSize);
if (invSize) indexCurve(ear, minX, minY, invSize);
let stop = ear;
let stop = ear, cured = false;

@@ -155,6 +154,4 @@ // iterate through ears, slicing them one by one

removeNode(ear);
ear = next;
stop = next;
continue;

@@ -167,16 +164,18 @@ }

if (ear === stop) {
// try filtering points and slicing again
if (!pass) {
earcutLinked(filterPoints(ear), triangles, dim, minX, minY, invSize, 1);
// try filtering collinear/coincident points and slicing again — repeat as long as
// filtering actually removes nodes, since each removal can expose new ears
filteredOut = false;
ear = filterPoints(ear);
if (filteredOut) { stop = ear; continue; }
// if this didn't work, try curing all small self-intersections locally
} else if (pass === 1) {
ear = cureLocalIntersections(filterPoints(ear), triangles);
earcutLinked(ear, triangles, dim, minX, minY, invSize, 2);
// filtering is exhausted: cure small local self-intersections once, then retry
if (!cured) {
ear = cureLocalIntersections(ear, triangles);
stop = ear;
cured = true;
continue;
}
// as a last resort, try splitting the remaining polygon into two
} else if (pass === 2) {
splitEarcut(ear, triangles, dim, minX, minY, invSize);
}
splitEarcut(ear, triangles, minX, minY, invSize);
break;

@@ -190,15 +189,6 @@ }

function isEar(ear) {
const a = ear.prev,
b = ear,
c = ear.next;
// reflex check (area(a, b, c) >= 0) is hoisted into the earcutLinked caller to avoid non-inlined call here
// make sure we don't have other points inside the potential ear; the point-in-triangle
// test (false when the point coincides with the first vertex a) is inlined here and in
// isEarHashed rather than called — V8 doesn't inline it and the call sits in the hot loop
const ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y;
// triangle bbox
const x0 = Math.min(ax, bx, cx),
const a = ear.prev, b = ear, c = ear.next,
ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y,
x0 = Math.min(ax, bx, cx), // triangle bbox
y0 = Math.min(ay, by, cy),

@@ -208,10 +198,9 @@ x1 = Math.max(ax, bx, cx),

// make sure we don't have other points inside the potential ear
let p = c.next;
while (p !== a) {
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 &&
!(ax === p.x && ay === p.y) && (cx - p.x) * (ay - p.y) >= (ax - p.x) * (cy - p.y) && (ax - p.x) * (by - p.y) >= (bx - p.x) * (ay - p.y) && (bx - p.x) * (cy - p.y) >= (cx - p.x) * (by - p.y) &&
area(p.prev, p, p.next) >= 0) return false;
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && !(ax === p.x && ay === p.y) &&
pointInTriangle(ax, ay, bx, by, cx, cy, p.x, p.y) && area(p.prev, p, p.next) >= 0) return false;
p = p.next;
}
return true;

@@ -222,48 +211,24 @@ }

function isEarHashed(ear, minX, minY, invSize) {
const a = ear.prev,
b = ear,
c = ear.next;
// reflex check is hoisted into the earcutLinked caller (see isEar)
const ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y;
// triangle bbox
const x0 = Math.min(ax, bx, cx),
const a = ear.prev, b = ear, c = ear.next,
ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y,
x0 = Math.min(ax, bx, cx), // triangle bbox
y0 = Math.min(ay, by, cy),
x1 = Math.max(ax, bx, cx),
y1 = Math.max(ay, by, cy);
// z-order range for the current triangle bbox;
const minZ = zOrder(x0, y0, minX, minY, invSize),
y1 = Math.max(ay, by, cy),
minZ = zOrder(x0, y0, minX, minY, invSize), // z-order range for the current triangle bbox;
maxZ = zOrder(x1, y1, minX, minY, invSize);
let p = ear.prevZ,
n = ear.nextZ;
// look for points inside the triangle in both directions
while (p && p.z >= minZ && n && n.z <= maxZ) {
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== c &&
!(ax === p.x && ay === p.y) && (cx - p.x) * (ay - p.y) >= (ax - p.x) * (cy - p.y) && (ax - p.x) * (by - p.y) >= (bx - p.x) * (ay - p.y) && (bx - p.x) * (cy - p.y) >= (cx - p.x) * (by - p.y) && area(p.prev, p, p.next) >= 0) return false;
let p = ear.prevZ;
while (p && p.z >= minZ) { // look for points inside the triangle in decreasing z-order
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== c && !(ax === p.x && ay === p.y) &&
pointInTriangle(ax, ay, bx, by, cx, cy, p.x, p.y) && area(p.prev, p, p.next) >= 0) return false;
p = p.prevZ;
if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== c &&
!(ax === n.x && ay === n.y) && (cx - n.x) * (ay - n.y) >= (ax - n.x) * (cy - n.y) && (ax - n.x) * (by - n.y) >= (bx - n.x) * (ay - n.y) && (bx - n.x) * (cy - n.y) >= (cx - n.x) * (by - n.y) && area(n.prev, n, n.next) >= 0) return false;
n = n.nextZ;
}
// look for remaining points in decreasing z-order
while (p && p.z >= minZ) {
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== c &&
!(ax === p.x && ay === p.y) && (cx - p.x) * (ay - p.y) >= (ax - p.x) * (cy - p.y) && (ax - p.x) * (by - p.y) >= (bx - p.x) * (ay - p.y) && (bx - p.x) * (cy - p.y) >= (cx - p.x) * (by - p.y) && area(p.prev, p, p.next) >= 0) return false;
p = p.prevZ;
}
// look for remaining points in increasing z-order
while (n && n.z <= maxZ) {
if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== c &&
!(ax === n.x && ay === n.y) && (cx - n.x) * (ay - n.y) >= (ax - n.x) * (cy - n.y) && (ax - n.x) * (by - n.y) >= (bx - n.x) * (ay - n.y) && (bx - n.x) * (cy - n.y) >= (cx - n.x) * (by - n.y) && area(n.prev, n, n.next) >= 0) return false;
let n = ear.nextZ;
while (n && n.z <= maxZ) { // look for points in increasing z-order
if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== c && !(ax === n.x && ay === n.y) &&
pointInTriangle(ax, ay, bx, by, cx, cy, n.x, n.y) && area(n.prev, n, n.next) >= 0) return false;
n = n.nextZ;
}
return true;

@@ -299,4 +264,4 @@ }

// try splitting polygon into two and triangulate them independently
/** @param {Node} start @param {number[]} triangles @param {number} dim @param {number} minX @param {number} minY @param {number} invSize */
function splitEarcut(start, triangles, dim, minX, minY, invSize) {
/** @param {Node} start @param {number[]} triangles @param {number} minX @param {number} minY @param {number} invSize */
function splitEarcut(start, triangles, minX, minY, invSize) {
// look for a valid diagonal that divides the polygon into two

@@ -316,4 +281,4 @@ let a = start;

// run earcut on each half
earcutLinked(a, triangles, dim, minX, minY, invSize, 0);
earcutLinked(c, triangles, dim, minX, minY, invSize, 0);
earcutLinked(a, triangles, minX, minY, invSize);
earcutLinked(c, triangles, minX, minY, invSize);
return;

@@ -358,3 +323,4 @@ }

return outerNode;
// collapse collinear/coincident points across the whole merged ring once before clipping
return filterPoints(outerNode);
}

@@ -566,7 +532,15 @@

// scratch array of node refs, reused across calls and grown on demand
// scratch buffers reused across calls and grown on demand: two node-ref arrays that
// ping-pong during the radix passes, plus parallel z-value arrays so the passes read
// z from contiguous memory instead of dereferencing each node. 256-entry histogram for
// 8-bit digits; the small histogram keeps per-call setup cheap (most rings are short)
/** @type {Node[]} */
const sortArr = [];
/** @type {Node[]} */
let sortBuf = [];
let zArr = new Uint32Array(0);
let zBuf = new Uint32Array(0);
const counts = new Uint32Array(256);
// interlink polygon nodes in z-order: collect into an array, quicksort by z, relink
// interlink polygon nodes in z-order: collect into an array, sort by z, relink
/** @param {Node} start @param {number} minX @param {number} minY @param {number} invSize */

@@ -583,3 +557,3 @@ function indexCurve(start, minX, minY, invSize) {

quicksortNodes(sortArr, 0, n - 1);
sortNodes(n);

@@ -597,34 +571,47 @@ /** @type {Node | null} */

// quicksort an array of nodes by z; middle-element pivot + insertion sort for small ranges
/** @param {Node[]} arr @param {number} left @param {number} right */
function quicksortNodes(arr, left, right) {
while (right - left > 20) {
// middle pivot splits already-sorted/reversed runs evenly; real ring-order-by-z data
// is non-adversarial, so the median-of-three guard isn't needed
const pivot = arr[(left + right) >> 1].z;
let i = left, j = right, t;
while (i <= j) {
while (arr[i].z < pivot) i++;
while (arr[j].z > pivot) j--;
if (i <= j) { t = arr[i]; arr[i] = arr[j]; arr[j] = t; i++; j--; }
// sort the first n nodes of sortArr by z, in place: insertion sort for small n (cheaper
// than histogram setup), else LSD radix in four 8-bit passes (covering z's 30 bits)
/** @param {number} n */
function sortNodes(n) {
if (n <= 32) {
for (let i = 1; i < n; i++) {
const node = sortArr[i], z = node.z;
let j = i - 1;
while (j >= 0 && sortArr[j].z > z) { sortArr[j + 1] = sortArr[j]; j--; }
sortArr[j + 1] = node;
}
// recurse into the smaller half, loop on the larger to bound stack depth
if (j - left < right - i) {
quicksortNodes(arr, left, j);
left = i;
} else {
quicksortNodes(arr, i, right);
right = j;
}
return;
}
// insertion sort the small remaining range
for (let i = left + 1; i <= right; i++) {
const node = arr[i], z = node.z;
let j = i - 1;
while (j >= left && arr[j].z > z) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = node;
if (zArr.length < n) {
zArr = new Uint32Array(n);
zBuf = new Uint32Array(n);
sortBuf = new Array(n);
}
for (let i = 0; i < n; i++) zArr[i] = sortArr[i].z;
// even pass count lands the sorted result back in sortArr
radixPass(n, sortArr, zArr, sortBuf, zBuf, 0);
radixPass(n, sortBuf, zBuf, sortArr, zArr, 8);
radixPass(n, sortArr, zArr, sortBuf, zBuf, 16);
radixPass(n, sortBuf, zBuf, sortArr, zArr, 24);
}
// one LSD radix pass: stably scatter the first n nodes (and their z) from src to dst,
// bucketed by the 8-bit digit of z at the given bit shift
/** @param {number} n @param {Node[]} src @param {Uint32Array} srcZ @param {Node[]} dst @param {Uint32Array} dstZ @param {number} shift */
function radixPass(n, src, srcZ, dst, dstZ, shift) {
counts.fill(0);
for (let i = 0; i < n; i++) counts[(srcZ[i] >>> shift) & 0xff]++;
// turn per-bucket counts into start offsets (prefix sum)
let sum = 0;
for (let b = 0; b < 256; b++) { const c = counts[b]; counts[b] = sum; sum += c; }
for (let i = 0; i < n; i++) {
const z = srcZ[i];
const pos = counts[(z >>> shift) & 0xff]++;
dst[pos] = src[i];
dstZ[pos] = z;
}
}
// z-order of a point given coords and inverse of the longer side of data bbox

@@ -674,6 +661,6 @@ /** @param {number} x @param {number} y @param {number} minX @param {number} minY @param {number} invSize @returns {number} */

function isValidDiagonal(a, b) {
return a.next.i !== b.i && !intersectsPolygon(a, b) && // doesn't intersect other edges
(locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b) && // locally visible
(area(a.prev, a, b.prev) !== 0 || area(a, b.prev, b) !== 0) || // does not create opposite-facing sectors
equals(a, b) && area(a.prev, a, a.next) > 0 && area(b.prev, b, b.next) > 0); // special zero-length case
const zeroLength = equals(a, b) && area(a.prev, a, a.next) > 0 && area(b.prev, b, b.next) > 0; // degenerate case
return a.next.i !== b.i && (zeroLength || locallyInside(a, b) && locallyInside(b, a) && // // locally visible
(area(a.prev, a, b.prev) !== 0 || area(a, b.prev, b) !== 0)) && // no opposite-facing sectors
!intersectsPolygon(a, b) && (zeroLength || middleInside(a, b)); // doesn't intersect other edges, diagonal inside polygon
}

@@ -680,0 +667,0 @@ 

+1
-1
dist/earcut.min.js

@@ -1,1 +0,1 @@

!function(t,n){"object"==typeof exports&&"undefined"!=typeof module?n(exports):"function"==typeof define&&define.amd?define(["exports"],n):n((t="undefined"!=typeof globalThis?globalThis:t||self).earcut={})}(this,function(t){"use strict";const n=new Set;function e(t,n,e,x,r){let o=null;if(r===C(t,n,e,x)>0)for(let r=n;r<e;r+=x)o=S(r/x|0,t[r],t[r+1],o);else for(let r=e-x;r>=n;r-=x)o=S(r/x|0,t[r],t[r+1],o);return o&&T(o,o.next)&&(q(o),o=o.next),o}function x(t,e=t){const x=e===t;let r,o=t;do{r=!1,o===o.next||0!==n.size&&n.has(o)||!T(o,o.next)&&0!==F(o.prev,o,o.next)?(x||o!==e)&&(o=o.next,r=!x):((x||o===e)&&(e=o.prev),q(o),o=o.prev,r=!0)}while(r||o!==e);return e}function r(t,n,e,u,l,c,s){if(!t)return;!s&&c&&function(t,n,e,x){let r=t,o=0;do{r.z=w(r.x,r.y,n,e,x),g[o++]=r,r=r.next}while(r!==t);z(g,0,o-1);let i=null;for(let t=0;t<o;t++){const n=g[t];n.prevZ=i,i&&(i.nextZ=n),i=n}i.nextZ=null}(t,u,l,c);let p=t;for(;t.prev!==t.next;){const h=t.prev,a=t.next;if(F(h,t,a)<0&&(c?i(t,u,l,c):o(t)))n.push(h.i,t.i,a.i),q(t),t=a,p=a;else if((t=a)===p){s?1===s?r(t=y(x(t),n),n,e,u,l,c,2):2===s&&f(t,n,e,u,l,c):r(x(t),n,e,u,l,c,1);break}}}function o(t){const n=t.prev,e=t,x=t.next,r=n.x,o=e.x,i=x.x,y=n.y,f=e.y,u=x.y,l=Math.min(r,o,i),c=Math.min(y,f,u),s=Math.max(r,o,i),p=Math.max(y,f,u);let h=x.next;for(;h!==n;){if(h.x>=l&&h.x<=s&&h.y>=c&&h.y<=p&&(r!==h.x||y!==h.y)&&(i-h.x)*(y-h.y)>=(r-h.x)*(u-h.y)&&(r-h.x)*(f-h.y)>=(o-h.x)*(y-h.y)&&(o-h.x)*(u-h.y)>=(i-h.x)*(f-h.y)&&F(h.prev,h,h.next)>=0)return!1;h=h.next}return!0}function i(t,n,e,x){const r=t.prev,o=t,i=t.next,y=r.x,f=o.x,u=i.x,l=r.y,c=o.y,s=i.y,p=Math.min(y,f,u),h=Math.min(l,c,s),a=Math.max(y,f,u),v=Math.max(l,c,s),d=w(p,h,n,e,x),M=w(a,v,n,e,x);let m=t.prevZ,Z=t.nextZ;for(;m&&m.z>=d&&Z&&Z.z<=M;){if(m.x>=p&&m.x<=a&&m.y>=h&&m.y<=v&&m!==i&&(y!==m.x||l!==m.y)&&(u-m.x)*(l-m.y)>=(y-m.x)*(s-m.y)&&(y-m.x)*(c-m.y)>=(f-m.x)*(l-m.y)&&(f-m.x)*(s-m.y)>=(u-m.x)*(c-m.y)&&F(m.prev,m,m.next)>=0)return!1;if(m=m.prevZ,Z.x>=p&&Z.x<=a&&Z.y>=h&&Z.y<=v&&Z!==i&&(y!==Z.x||l!==Z.y)&&(u-Z.x)*(l-Z.y)>=(y-Z.x)*(s-Z.y)&&(y-Z.x)*(c-Z.y)>=(f-Z.x)*(l-Z.y)&&(f-Z.x)*(s-Z.y)>=(u-Z.x)*(c-Z.y)&&F(Z.prev,Z,Z.next)>=0)return!1;Z=Z.nextZ}for(;m&&m.z>=d;){if(m.x>=p&&m.x<=a&&m.y>=h&&m.y<=v&&m!==i&&(y!==m.x||l!==m.y)&&(u-m.x)*(l-m.y)>=(y-m.x)*(s-m.y)&&(y-m.x)*(c-m.y)>=(f-m.x)*(l-m.y)&&(f-m.x)*(s-m.y)>=(u-m.x)*(c-m.y)&&F(m.prev,m,m.next)>=0)return!1;m=m.prevZ}for(;Z&&Z.z<=M;){if(Z.x>=p&&Z.x<=a&&Z.y>=h&&Z.y<=v&&Z!==i&&(y!==Z.x||l!==Z.y)&&(u-Z.x)*(l-Z.y)>=(y-Z.x)*(s-Z.y)&&(y-Z.x)*(c-Z.y)>=(f-Z.x)*(l-Z.y)&&(f-Z.x)*(s-Z.y)>=(u-Z.x)*(c-Z.y)&&F(Z.prev,Z,Z.next)>=0)return!1;Z=Z.nextZ}return!0}function y(t,n){let e=t,r=!1;do{const x=e.prev,o=e.next.next;_(x,e,e.next,o,!1)&&O(x,o)&&O(o,x)&&(n.push(x.i,e.i,o.i),q(e),q(e.next),e=t=o,r=!0),e=e.next}while(e!==t);return r?x(e):e}function f(t,n,e,o,i,y){let f=t;do{let t=f.next.next;for(;t!==f.prev;){if(f.i!==t.i&&A(f,t)){let u=P(f,t);return f=x(f,f.next),u=x(u,u.next),r(f,n,e,o,i,y,0),void r(u,n,e,o,i,y,0)}t=t.next}f=f.next}while(f!==t)}let u=!1;function l(t,n){return t.x-n.x||t.y-n.y||(t.next.y-t.y)/(t.next.x-t.x)-(n.next.y-n.y)/(n.next.x-n.x)}function c(t,n){const e=function(t,n){let e=n;const x=t.x,r=t.y;let o,i=-1/0;if(T(t,e))return e;for(let n=0,y=0;n<h;n++,y+=4){if(r<p[y+1]||r>p[y+3]||p[y]>x||p[y+2]<=i)continue;const f=M(n);e=m(n);do{if(e.prev.next===e){if(T(t,e.next))return e.next;if(r<=e.y&&r>=e.next.y&&e.next.y!==e.y){const t=e.x+(r-e.y)*(e.next.x-e.x)/(e.next.y-e.y);if(t<=x&&t>i&&(i=t,o=e.x<e.next.x?e:e.next,t===x))return o}}e=e.next}while(e!==f)}if(!o)return null;const y=o.x,f=o.y,u=Math.min(r,f),l=Math.max(r,f);let c=1/0;for(let n=0,s=0;n<h;n++,s+=4){if(p[s+2]<y||p[s]>x||p[s+3]<u||p[s+1]>l)continue;const h=M(n);e=m(n);do{if(e.prev.next===e&&x>=e.x&&e.x>=y&&x!==e.x&&j(r<f?x:i,r,y,f,r<f?i:x,r,e.x,e.y)){const n=Math.abs(r-e.y)/(x-e.x);(O(e,t)||e.y===r&&e.next.y===r&&e.next.x>x)&&(n<c||n===c&&(e.x>o.x||e.x===o.x&&Z(o,e)))&&(o=e,c=n)}e=e.next}while(e!==h)}return o}(t,n);if(!e)return n;const r=P(e,t);return d(e,r.next.next),x(r,r.next),x(e,e.next)}const s=16;let p=new Float64Array(0),h=0;const a=[],v=[];function d(t,n){let e=t;do{const t=h++;a[t]=e;let x=1/0,r=1/0,o=-1/0,i=-1/0,y=0;do{const n=e.next;e.z=t,e.x<x&&(x=e.x),e.x>o&&(o=e.x),e.y<r&&(r=e.y),e.y>i&&(i=e.y),n.x<x&&(x=n.x),n.x>o&&(o=n.x),n.y<r&&(r=n.y),n.y>i&&(i=n.y),e=n}while(++y<s&&e!==n);v[t]=e;const f=4*t;p[f]=x,p[f+1]=r,p[f+2]=o,p[f+3]=i}while(e!==n)}function M(t){let n=v[t];for(;n.prev.next!==n;)n=n.next;return v[t]=n,n}function m(t){let n=a[t];for(;n.prev.next!==n;)n=n.next;return a[t]=n,n}function Z(t,n){return F(t.prev,t,n.prev)<0&&F(n.next,t,t.next)<0}const g=[];function z(t,n,e){for(;e-n>20;){const x=t[n+e>>1].z;let r,o=n,i=e;for(;o<=i;){for(;t[o].z<x;)o++;for(;t[i].z>x;)i--;o<=i&&(r=t[o],t[o]=t[i],t[i]=r,o++,i--)}i-n<e-o?(z(t,n,i),n=o):(z(t,o,e),e=i)}for(let x=n+1;x<=e;x++){const e=t[x],r=e.z;let o=x-1;for(;o>=n&&t[o].z>r;)t[o+1]=t[o],o--;t[o+1]=e}}function w(t,n,e,x,r){return(t=1431655765&((t=858993459&((t=252645135&((t=16711935&((t=(t-e)*r|0)|t<<8))|t<<4))|t<<2))|t<<1))|(n=1431655765&((n=858993459&((n=252645135&((n=16711935&((n=(n-x)*r|0)|n<<8))|n<<4))|n<<2))|n<<1))<<1}function b(t){let n=t,e=t;do{(n.x<e.x||n.x===e.x&&n.y<e.y)&&(e=n),n=n.next}while(n!==t);return e}function j(t,n,e,x,r,o,i,y){return(r-i)*(n-y)>=(t-i)*(o-y)&&(t-i)*(x-y)>=(e-i)*(n-y)&&(e-i)*(o-y)>=(r-i)*(x-y)}function A(t,n){return t.next.i!==n.i&&!function(t,n){const e=Math.min(t.x,n.x),x=Math.max(t.x,n.x),r=Math.min(t.y,n.y),o=Math.max(t.y,n.y);let i=t;do{const y=i.next;if(i.x>x&&y.x>x||i.x<e&&y.x<e||i.y>o&&y.y>o||i.y<r&&y.y<r)i=y;else{if(i.i!==t.i&&y.i!==t.i&&i.i!==n.i&&y.i!==n.i&&_(i,y,t,n))return!0;i=y}}while(i!==t);return!1}(t,n)&&(O(t,n)&&O(n,t)&&function(t,n){let e=t,x=!1;const r=(t.x+n.x)/2,o=(t.y+n.y)/2;do{const t=e.next;e.y>o!=t.y>o&&r<(t.x-e.x)*(o-e.y)/(t.y-e.y)+e.x&&(x=!x),e=t}while(e!==t);return x}(t,n)&&(0!==F(t.prev,t,n.prev)||0!==F(t,n.prev,n))||T(t,n)&&F(t.prev,t,t.next)>0&&F(n.prev,n,n.next)>0)}function F(t,n,e){return(n.y-t.y)*(e.x-n.x)-(n.x-t.x)*(e.y-n.y)}function T(t,n){return t.x===n.x&&t.y===n.y}function _(t,n,e,x,r=!0){const o=F(t,n,e),i=F(t,n,x),y=F(e,x,t),f=F(e,x,n);return(o>0&&i<0||o<0&&i>0)&&(y>0&&f<0||y<0&&f>0)||!!r&&(!(0!==o||!k(t,e,n))||(!(0!==i||!k(t,x,n))||(!(0!==y||!k(e,t,x))||!(0!==f||!k(e,n,x)))))}function k(t,n,e){return n.x<=Math.max(t.x,e.x)&&n.x>=Math.min(t.x,e.x)&&n.y<=Math.max(t.y,e.y)&&n.y>=Math.min(t.y,e.y)}function O(t,n){return F(t.prev,t,t.next)<0?F(t,n,t.next)>=0&&F(t,t.prev,n)>=0:F(t,n,t.prev)<0||F(t,t.next,n)<0}function P(t,n){const e=B(t.i,t.x,t.y),x=B(n.i,n.x,n.y),r=t.next,o=n.prev;return t.next=n,n.prev=t,e.next=r,r.prev=e,x.next=e,e.prev=x,o.next=x,x.prev=o,x}function S(t,n,e,x){const r=B(t,n,e);return x?(r.next=x.next,r.prev=x,x.next.prev=r,x.next=r):(r.prev=r,r.next=r),r}function q(t){t.next.prev=t.prev,t.prev.next=t.next,t.prevZ&&(t.prevZ.nextZ=t.nextZ),t.nextZ&&(t.nextZ.prevZ=t.prevZ),u&&function(t,n){const e=4*t.z;n.x<p[e]&&(p[e]=n.x),n.y<p[e+1]&&(p[e+1]=n.y),n.x>p[e+2]&&(p[e+2]=n.x),n.y>p[e+3]&&(p[e+3]=n.y)}(t.prev,t.next)}function B(t,n,e){return{i:t,x:n,y:e,prev:null,next:null,z:0,prevZ:null,nextZ:null}}function C(t,n,e,x){let r=0;for(let o=n,i=e-x;o<e;o+=x)r+=(t[i]-t[o])*(t[o+1]+t[i+1]),i=o;return r}t.default=function(t,o,i=2){const y=o&&o.length,f=y?o[0]*i:t.length;n.size&&n.clear();let a=e(t,0,f,i,!0);const v=[];if(!a||a.next===a.prev)return v;let M=0,m=0,Z=0;if(y&&(a=function(t,x,r,o){const i=[];for(let r=0,y=x.length;r<y;r++){const f=e(t,x[r]*o,r<y-1?x[r+1]*o:t.length,o,!1);f===f.next&&n.add(f),i.push(b(f))}i.sort(l),function(t,n){const e=Math.ceil((t+2*n)/s)+n+2;p.length<4*e&&(p=new Float64Array(4*e));h=0}(t.length/o,x.length),d(r,r),u=!0;for(let t=0;t<i.length;t++)r=c(i[t],r);return u=!1,r}(t,o,a,i),a=x(a)),t.length>80*i){M=t[0],m=t[1];let n=M,e=m;for(let x=i;x<f;x+=i){const r=t[x],o=t[x+1];r<M&&(M=r),o<m&&(m=o),r>n&&(n=r),o>e&&(e=o)}Z=Math.max(n-M,e-m),Z=0!==Z?32767/Z:0}return r(a,v,i,M,m,Z,0),v},t.deviation=function(t,n,e,x){const r=n&&n.length,o=r?n[0]*e:t.length;let i=Math.abs(C(t,0,o,e));if(r)for(let x=0,r=n.length;x<r;x++){const o=n[x]*e,y=x<r-1?n[x+1]*e:t.length;i-=Math.abs(C(t,o,y,e))}let y=0;for(let n=0;n<x.length;n+=3){const r=x[n]*e,o=x[n+1]*e,i=x[n+2]*e;y+=Math.abs((t[r]-t[i])*(t[o+1]-t[r+1])-(t[r]-t[o])*(t[i+1]-t[r+1]))}return 0===i&&0===y?0:Math.abs((y-i)/i)},t.flatten=function(t){const n=[],e=[],x=t[0][0].length;let r=0,o=0;for(const i of t){for(const t of i)for(let e=0;e<x;e++)n.push(t[e]);o&&(r+=o,e.push(r)),o=i.length}return{vertices:n,holes:e,dimensions:x}},Object.defineProperty(t,"__esModule",{value:!0})});
!function(t,n){"object"==typeof exports&&"undefined"!=typeof module?n(exports):"function"==typeof define&&define.amd?define(["exports"],n):n((t="undefined"!=typeof globalThis?globalThis:t||self).earcut={})}(this,function(t){"use strict";const n=new Set;let e=!1;function x(t,n,e,x,r){let o=null;if(r===H(t,n,e,x)>0)for(let r=n;r<e;r+=x)o=D(r/x|0,t[r],t[r+1],o);else for(let r=e-x;r>=n;r-=x)o=D(r/x|0,t[r],t[r+1],o);return o&&P(o,o.next)&&(E(o),o=o.next),o}function r(t,x=t){const r=x===t;let o,i=t;do{o=!1,i===i.next||0!==n.size&&n.has(i)||!P(i,i.next)&&0!==O(i.prev,i,i.next)?(r||i!==x)&&(i=i.next,o=!r):((r||i===x)&&(x=i.prev),e=!0,E(i),i=i.prev,o=!0)}while(o||i!==x);return x}function o(t,n,x,o,c){c&&function(t,n,e,x){let r=t,o=0;do{r.z=F(r.x,r.y,n,e,x),Z[o++]=r,r=r.next}while(r!==t);!function(t){if(t<=32){for(let n=1;n<t;n++){const t=Z[n],e=t.z;let x=n-1;for(;x>=0&&Z[x].z>e;)Z[x+1]=Z[x],x--;Z[x+1]=t}return}b.length<t&&(b=new Uint32Array(t),A=new Uint32Array(t),z=new Array(t));for(let n=0;n<t;n++)b[n]=Z[n].z;j(t,Z,b,z,A,0),j(t,z,A,Z,b,8),j(t,Z,b,z,A,16),j(t,z,A,Z,b,24)}(o);let i=null;for(let t=0;t<o;t++){const n=Z[t];n.prevZ=i,i&&(i.nextZ=n),i=n}i.nextZ=null}(t,x,o,c);let y=t,s=!1;for(;t.prev!==t.next;){const h=t.prev,a=t.next;if(O(h,t,a)<0&&(c?l(t,x,o,c):i(t)))n.push(h.i,t.i,a.i),E(t),t=a,y=a;else if((t=a)===y){if(e=!1,t=r(t),e){y=t;continue}if(!s){y=t=f(t,n),s=!0;continue}u(t,n,x,o,c);break}}}function i(t){const n=t.prev,e=t,x=t.next,r=n.x,o=e.x,i=x.x,l=n.y,f=e.y,u=x.y,c=Math.min(r,o,i),y=Math.min(l,f,u),s=Math.max(r,o,i),h=Math.max(l,f,u);let a=x.next;for(;a!==n;){if(a.x>=c&&a.x<=s&&a.y>=y&&a.y<=h&&(r!==a.x||l!==a.y)&&_(r,l,o,f,i,u,a.x,a.y)&&O(a.prev,a,a.next)>=0)return!1;a=a.next}return!0}function l(t,n,e,x){const r=t.prev,o=t,i=t.next,l=r.x,f=o.x,u=i.x,c=r.y,y=o.y,s=i.y,h=Math.min(l,f,u),a=Math.min(c,y,s),p=Math.max(l,f,u),v=Math.max(c,y,s),d=F(h,a,n,e,x),M=F(p,v,n,e,x);let m=t.prevZ;for(;m&&m.z>=d;){if(m.x>=h&&m.x<=p&&m.y>=a&&m.y<=v&&m!==i&&(l!==m.x||c!==m.y)&&_(l,c,f,y,u,s,m.x,m.y)&&O(m.prev,m,m.next)>=0)return!1;m=m.prevZ}let w=t.nextZ;for(;w&&w.z<=M;){if(w.x>=h&&w.x<=p&&w.y>=a&&w.y<=v&&w!==i&&(l!==w.x||c!==w.y)&&_(l,c,f,y,u,s,w.x,w.y)&&O(w.prev,w,w.next)>=0)return!1;w=w.nextZ}return!0}function f(t,n){let e=t,x=!1;do{const r=e.prev,o=e.next.next;S(r,e,e.next,o,!1)&&B(r,o)&&B(o,r)&&(n.push(r.i,e.i,o.i),E(e),E(e.next),e=t=o,x=!0),e=e.next}while(e!==t);return x?r(e):e}function u(t,n,e,x,i){let l=t;do{let t=l.next.next;for(;t!==l.prev;){if(l.i!==t.i&&k(l,t)){let f=C(l,t);return l=r(l,l.next),f=r(f,f.next),o(l,n,e,x,i),void o(f,n,e,x,i)}t=t.next}l=l.next}while(l!==t)}let c=!1;function y(t,n){return t.x-n.x||t.y-n.y||(t.next.y-t.y)/(t.next.x-t.x)-(n.next.y-n.y)/(n.next.x-n.x)}function s(t,n){const e=function(t,n){let e=n;const x=t.x,r=t.y;let o,i=-1/0;if(P(t,e))return e;for(let n=0,l=0;n<p;n++,l+=4){if(r<a[l+1]||r>a[l+3]||a[l]>x||a[l+2]<=i)continue;const f=m(n);e=w(n);do{if(e.prev.next===e){if(P(t,e.next))return e.next;if(r<=e.y&&r>=e.next.y&&e.next.y!==e.y){const t=e.x+(r-e.y)*(e.next.x-e.x)/(e.next.y-e.y);if(t<=x&&t>i&&(i=t,o=e.x<e.next.x?e:e.next,t===x))return o}}e=e.next}while(e!==f)}if(!o)return null;const l=o.x,f=o.y,u=Math.min(r,f),c=Math.max(r,f);let y=1/0;for(let n=0,s=0;n<p;n++,s+=4){if(a[s+2]<l||a[s]>x||a[s+3]<u||a[s+1]>c)continue;const h=m(n);e=w(n);do{if(e.prev.next===e&&x>=e.x&&e.x>=l&&x!==e.x&&_(r<f?x:i,r,l,f,r<f?i:x,r,e.x,e.y)){const n=Math.abs(r-e.y)/(x-e.x);(B(e,t)||e.y===r&&e.next.y===r&&e.next.x>x)&&(n<y||n===y&&(e.x>o.x||e.x===o.x&&g(o,e)))&&(o=e,y=n)}e=e.next}while(e!==h)}return o}(t,n);if(!e)return n;const x=C(e,t);return M(e,x.next.next),r(x,x.next),r(e,e.next)}const h=16;let a=new Float64Array(0),p=0;const v=[],d=[];function M(t,n){let e=t;do{const t=p++;v[t]=e;let x=1/0,r=1/0,o=-1/0,i=-1/0,l=0;do{const n=e.next;e.z=t,e.x<x&&(x=e.x),e.x>o&&(o=e.x),e.y<r&&(r=e.y),e.y>i&&(i=e.y),n.x<x&&(x=n.x),n.x>o&&(o=n.x),n.y<r&&(r=n.y),n.y>i&&(i=n.y),e=n}while(++l<h&&e!==n);d[t]=e;const f=4*t;a[f]=x,a[f+1]=r,a[f+2]=o,a[f+3]=i}while(e!==n)}function m(t){let n=d[t];for(;n.prev.next!==n;)n=n.next;return d[t]=n,n}function w(t){let n=v[t];for(;n.prev.next!==n;)n=n.next;return v[t]=n,n}function g(t,n){return O(t.prev,t,n.prev)<0&&O(n.next,t,t.next)<0}const Z=[];let z=[],b=new Uint32Array(0),A=new Uint32Array(0);const U=new Uint32Array(256);function j(t,n,e,x,r,o){U.fill(0);for(let n=0;n<t;n++)U[e[n]>>>o&255]++;let i=0;for(let t=0;t<256;t++){const n=U[t];U[t]=i,i+=n}for(let i=0;i<t;i++){const t=e[i],l=U[t>>>o&255]++;x[l]=n[i],r[l]=t}}function F(t,n,e,x,r){return(t=1431655765&((t=858993459&((t=252645135&((t=16711935&((t=(t-e)*r|0)|t<<8))|t<<4))|t<<2))|t<<1))|(n=1431655765&((n=858993459&((n=252645135&((n=16711935&((n=(n-x)*r|0)|n<<8))|n<<4))|n<<2))|n<<1))<<1}function T(t){let n=t,e=t;do{(n.x<e.x||n.x===e.x&&n.y<e.y)&&(e=n),n=n.next}while(n!==t);return e}function _(t,n,e,x,r,o,i,l){return(r-i)*(n-l)>=(t-i)*(o-l)&&(t-i)*(x-l)>=(e-i)*(n-l)&&(e-i)*(o-l)>=(r-i)*(x-l)}function k(t,n){const e=P(t,n)&&O(t.prev,t,t.next)>0&&O(n.prev,n,n.next)>0;return t.next.i!==n.i&&(e||B(t,n)&&B(n,t)&&(0!==O(t.prev,t,n.prev)||0!==O(t,n.prev,n)))&&!function(t,n){const e=Math.min(t.x,n.x),x=Math.max(t.x,n.x),r=Math.min(t.y,n.y),o=Math.max(t.y,n.y);let i=t;do{const l=i.next;if(i.x>x&&l.x>x||i.x<e&&l.x<e||i.y>o&&l.y>o||i.y<r&&l.y<r)i=l;else{if(i.i!==t.i&&l.i!==t.i&&i.i!==n.i&&l.i!==n.i&&S(i,l,t,n))return!0;i=l}}while(i!==t);return!1}(t,n)&&(e||function(t,n){let e=t,x=!1;const r=(t.x+n.x)/2,o=(t.y+n.y)/2;do{const t=e.next;e.y>o!=t.y>o&&r<(t.x-e.x)*(o-e.y)/(t.y-e.y)+e.x&&(x=!x),e=t}while(e!==t);return x}(t,n))}function O(t,n,e){return(n.y-t.y)*(e.x-n.x)-(n.x-t.x)*(e.y-n.y)}function P(t,n){return t.x===n.x&&t.y===n.y}function S(t,n,e,x,r=!0){const o=O(t,n,e),i=O(t,n,x),l=O(e,x,t),f=O(e,x,n);return(o>0&&i<0||o<0&&i>0)&&(l>0&&f<0||l<0&&f>0)||!!r&&(!(0!==o||!q(t,e,n))||(!(0!==i||!q(t,x,n))||(!(0!==l||!q(e,t,x))||!(0!==f||!q(e,n,x)))))}function q(t,n,e){return n.x<=Math.max(t.x,e.x)&&n.x>=Math.min(t.x,e.x)&&n.y<=Math.max(t.y,e.y)&&n.y>=Math.min(t.y,e.y)}function B(t,n){return O(t.prev,t,t.next)<0?O(t,n,t.next)>=0&&O(t,t.prev,n)>=0:O(t,n,t.prev)<0||O(t,t.next,n)<0}function C(t,n){const e=G(t.i,t.x,t.y),x=G(n.i,n.x,n.y),r=t.next,o=n.prev;return t.next=n,n.prev=t,e.next=r,r.prev=e,x.next=e,e.prev=x,o.next=x,x.prev=o,x}function D(t,n,e,x){const r=G(t,n,e);return x?(r.next=x.next,r.prev=x,x.next.prev=r,x.next=r):(r.prev=r,r.next=r),r}function E(t){t.next.prev=t.prev,t.prev.next=t.next,t.prevZ&&(t.prevZ.nextZ=t.nextZ),t.nextZ&&(t.nextZ.prevZ=t.prevZ),c&&function(t,n){const e=4*t.z;n.x<a[e]&&(a[e]=n.x),n.y<a[e+1]&&(a[e+1]=n.y),n.x>a[e+2]&&(a[e+2]=n.x),n.y>a[e+3]&&(a[e+3]=n.y)}(t.prev,t.next)}function G(t,n,e){return{i:t,x:n,y:e,prev:null,next:null,z:0,prevZ:null,nextZ:null}}function H(t,n,e,x){let r=0;for(let o=n,i=e-x;o<e;o+=x)r+=(t[i]-t[o])*(t[o+1]+t[i+1]),i=o;return r}t.default=function(t,e,i=2){const l=e&&e.length,f=l?e[0]*i:t.length;n.size&&n.clear();let u=x(t,0,f,i,!0);const v=[];if(!u||u.next===u.prev)return v;let d=0,m=0,w=0;if(l&&(u=function(t,e,o,i){const l=[];for(let r=0,o=e.length;r<o;r++){const f=x(t,e[r]*i,r<o-1?e[r+1]*i:t.length,i,!1);f===f.next&&n.add(f),l.push(T(f))}l.sort(y),function(t,n){const e=Math.ceil((t+2*n)/h)+n+2;a.length<4*e&&(a=new Float64Array(4*e));p=0}(t.length/i,e.length),M(o,o),c=!0;for(let t=0;t<l.length;t++)o=s(l[t],o);return c=!1,r(o)}(t,e,u,i)),t.length>80*i){d=t[0],m=t[1];let n=d,e=m;for(let x=i;x<f;x+=i){const r=t[x],o=t[x+1];r<d&&(d=r),o<m&&(m=o),r>n&&(n=r),o>e&&(e=o)}w=Math.max(n-d,e-m),w=0!==w?32767/w:0}return o(u,v,d,m,w),v},t.deviation=function(t,n,e,x){const r=n&&n.length,o=r?n[0]*e:t.length;let i=Math.abs(H(t,0,o,e));if(r)for(let x=0,r=n.length;x<r;x++){const o=n[x]*e,l=x<r-1?n[x+1]*e:t.length;i-=Math.abs(H(t,o,l,e))}let l=0;for(let n=0;n<x.length;n+=3){const r=x[n]*e,o=x[n+1]*e,i=x[n+2]*e;l+=Math.abs((t[r]-t[i])*(t[o+1]-t[r+1])-(t[r]-t[o])*(t[i+1]-t[r+1]))}return 0===i&&0===l?0:Math.abs((l-i)/i)},t.flatten=function(t){const n=[],e=[],x=t[0][0].length;let r=0,o=0;for(const i of t){for(const t of i)for(let e=0;e<x;e++)n.push(t[e]);o&&(r+=o,e.push(r)),o=i.length}return{vertices:n,holes:e,dimensions:x}},Object.defineProperty(t,"__esModule",{value:!0})});
+1
-1
package.json
{
"name": "earcut",
"version": "3.1.0",
"version": "3.1.1",
"description": "The fastest and smallest JavaScript polygon triangulation library for your WebGL apps",

@@ -5,0 +5,0 @@ "main": "src/earcut.js",

+104
-118
src/earcut.js

@@ -1,2 +0,1 @@

/**

@@ -23,2 +22,6 @@ * A vertex in a circular doubly linked list representing a polygon ring.

// set by filterPoints whenever it removes at least one node; read by earcutLinked's stall
// handler to decide whether another clip pass is worth attempting before the costlier stages
let filteredOut = false;
/**

@@ -47,7 +50,3 @@ * Triangulate a polygon given as a flat array of vertex coordinates.

if (hasHoles) {
outerNode = eliminateHoles(data, holeIndices, outerNode, dim);
// collapse collinear/coincident points across the whole merged ring once before clipping
outerNode = filterPoints(outerNode);
}
if (hasHoles) outerNode = eliminateHoles(data, holeIndices, outerNode, dim);

@@ -75,3 +74,3 @@ // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox

earcutLinked(outerNode, triangles, dim, minX, minY, invSize, 0);
earcutLinked(outerNode, triangles, minX, minY, invSize);

@@ -116,2 +115,3 @@ return triangles;

if (full || p === end) end = p.prev; // pull the stop bound back past the removal
filteredOut = true;
removeNode(p);

@@ -130,10 +130,8 @@ p = p.prev; // re-check the predecessor

// main ear slicing loop which triangulates a polygon (given as a linked list)
/** @param {Node | null} ear @param {number[]} triangles @param {number} dim @param {number} minX @param {number} minY @param {number} invSize @param {number} pass */
function earcutLinked(ear, triangles, dim, minX, minY, invSize, pass) {
if (!ear) return;
/** @param {Node} ear @param {number[]} triangles @param {number} minX @param {number} minY @param {number} invSize */
function earcutLinked(ear, triangles, minX, minY, invSize) {
// interlink polygon nodes in z-order
if (!pass && invSize) indexCurve(ear, minX, minY, invSize);
if (invSize) indexCurve(ear, minX, minY, invSize);
let stop = ear;
let stop = ear, cured = false;

@@ -150,6 +148,4 @@ // iterate through ears, slicing them one by one

removeNode(ear);
ear = next;
stop = next;
continue;

@@ -162,16 +158,18 @@ }

if (ear === stop) {
// try filtering points and slicing again
if (!pass) {
earcutLinked(filterPoints(ear), triangles, dim, minX, minY, invSize, 1);
// try filtering collinear/coincident points and slicing again — repeat as long as
// filtering actually removes nodes, since each removal can expose new ears
filteredOut = false;
ear = filterPoints(ear);
if (filteredOut) { stop = ear; continue; }
// if this didn't work, try curing all small self-intersections locally
} else if (pass === 1) {
ear = cureLocalIntersections(filterPoints(ear), triangles);
earcutLinked(ear, triangles, dim, minX, minY, invSize, 2);
// filtering is exhausted: cure small local self-intersections once, then retry
if (!cured) {
ear = cureLocalIntersections(ear, triangles);
stop = ear;
cured = true;
continue;
}
// as a last resort, try splitting the remaining polygon into two
} else if (pass === 2) {
splitEarcut(ear, triangles, dim, minX, minY, invSize);
}
splitEarcut(ear, triangles, minX, minY, invSize);
break;

@@ -185,15 +183,6 @@ }

function isEar(ear) {
const a = ear.prev,
b = ear,
c = ear.next;
// reflex check (area(a, b, c) >= 0) is hoisted into the earcutLinked caller to avoid non-inlined call here
// make sure we don't have other points inside the potential ear; the point-in-triangle
// test (false when the point coincides with the first vertex a) is inlined here and in
// isEarHashed rather than called — V8 doesn't inline it and the call sits in the hot loop
const ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y;
// triangle bbox
const x0 = Math.min(ax, bx, cx),
const a = ear.prev, b = ear, c = ear.next,
ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y,
x0 = Math.min(ax, bx, cx), // triangle bbox
y0 = Math.min(ay, by, cy),

@@ -203,10 +192,9 @@ x1 = Math.max(ax, bx, cx),

// make sure we don't have other points inside the potential ear
let p = c.next;
while (p !== a) {
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 &&
!(ax === p.x && ay === p.y) && (cx - p.x) * (ay - p.y) >= (ax - p.x) * (cy - p.y) && (ax - p.x) * (by - p.y) >= (bx - p.x) * (ay - p.y) && (bx - p.x) * (cy - p.y) >= (cx - p.x) * (by - p.y) &&
area(p.prev, p, p.next) >= 0) return false;
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && !(ax === p.x && ay === p.y) &&
pointInTriangle(ax, ay, bx, by, cx, cy, p.x, p.y) && area(p.prev, p, p.next) >= 0) return false;
p = p.next;
}
return true;

@@ -217,48 +205,24 @@ }

function isEarHashed(ear, minX, minY, invSize) {
const a = ear.prev,
b = ear,
c = ear.next;
// reflex check is hoisted into the earcutLinked caller (see isEar)
const ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y;
// triangle bbox
const x0 = Math.min(ax, bx, cx),
const a = ear.prev, b = ear, c = ear.next,
ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y,
x0 = Math.min(ax, bx, cx), // triangle bbox
y0 = Math.min(ay, by, cy),
x1 = Math.max(ax, bx, cx),
y1 = Math.max(ay, by, cy);
// z-order range for the current triangle bbox;
const minZ = zOrder(x0, y0, minX, minY, invSize),
y1 = Math.max(ay, by, cy),
minZ = zOrder(x0, y0, minX, minY, invSize), // z-order range for the current triangle bbox;
maxZ = zOrder(x1, y1, minX, minY, invSize);
let p = ear.prevZ,
n = ear.nextZ;
// look for points inside the triangle in both directions
while (p && p.z >= minZ && n && n.z <= maxZ) {
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== c &&
!(ax === p.x && ay === p.y) && (cx - p.x) * (ay - p.y) >= (ax - p.x) * (cy - p.y) && (ax - p.x) * (by - p.y) >= (bx - p.x) * (ay - p.y) && (bx - p.x) * (cy - p.y) >= (cx - p.x) * (by - p.y) && area(p.prev, p, p.next) >= 0) return false;
let p = ear.prevZ;
while (p && p.z >= minZ) { // look for points inside the triangle in decreasing z-order
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== c && !(ax === p.x && ay === p.y) &&
pointInTriangle(ax, ay, bx, by, cx, cy, p.x, p.y) && area(p.prev, p, p.next) >= 0) return false;
p = p.prevZ;
if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== c &&
!(ax === n.x && ay === n.y) && (cx - n.x) * (ay - n.y) >= (ax - n.x) * (cy - n.y) && (ax - n.x) * (by - n.y) >= (bx - n.x) * (ay - n.y) && (bx - n.x) * (cy - n.y) >= (cx - n.x) * (by - n.y) && area(n.prev, n, n.next) >= 0) return false;
n = n.nextZ;
}
// look for remaining points in decreasing z-order
while (p && p.z >= minZ) {
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== c &&
!(ax === p.x && ay === p.y) && (cx - p.x) * (ay - p.y) >= (ax - p.x) * (cy - p.y) && (ax - p.x) * (by - p.y) >= (bx - p.x) * (ay - p.y) && (bx - p.x) * (cy - p.y) >= (cx - p.x) * (by - p.y) && area(p.prev, p, p.next) >= 0) return false;
p = p.prevZ;
}
// look for remaining points in increasing z-order
while (n && n.z <= maxZ) {
if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== c &&
!(ax === n.x && ay === n.y) && (cx - n.x) * (ay - n.y) >= (ax - n.x) * (cy - n.y) && (ax - n.x) * (by - n.y) >= (bx - n.x) * (ay - n.y) && (bx - n.x) * (cy - n.y) >= (cx - n.x) * (by - n.y) && area(n.prev, n, n.next) >= 0) return false;
let n = ear.nextZ;
while (n && n.z <= maxZ) { // look for points in increasing z-order
if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== c && !(ax === n.x && ay === n.y) &&
pointInTriangle(ax, ay, bx, by, cx, cy, n.x, n.y) && area(n.prev, n, n.next) >= 0) return false;
n = n.nextZ;
}
return true;

@@ -294,4 +258,4 @@ }

// try splitting polygon into two and triangulate them independently
/** @param {Node} start @param {number[]} triangles @param {number} dim @param {number} minX @param {number} minY @param {number} invSize */
function splitEarcut(start, triangles, dim, minX, minY, invSize) {
/** @param {Node} start @param {number[]} triangles @param {number} minX @param {number} minY @param {number} invSize */
function splitEarcut(start, triangles, minX, minY, invSize) {
// look for a valid diagonal that divides the polygon into two

@@ -311,4 +275,4 @@ let a = start;

// run earcut on each half
earcutLinked(a, triangles, dim, minX, minY, invSize, 0);
earcutLinked(c, triangles, dim, minX, minY, invSize, 0);
earcutLinked(a, triangles, minX, minY, invSize);
earcutLinked(c, triangles, minX, minY, invSize);
return;

@@ -353,3 +317,4 @@ }

return outerNode;
// collapse collinear/coincident points across the whole merged ring once before clipping
return filterPoints(outerNode);
}

@@ -561,7 +526,15 @@

// scratch array of node refs, reused across calls and grown on demand
// scratch buffers reused across calls and grown on demand: two node-ref arrays that
// ping-pong during the radix passes, plus parallel z-value arrays so the passes read
// z from contiguous memory instead of dereferencing each node. 256-entry histogram for
// 8-bit digits; the small histogram keeps per-call setup cheap (most rings are short)
/** @type {Node[]} */
const sortArr = [];
/** @type {Node[]} */
let sortBuf = [];
let zArr = new Uint32Array(0);
let zBuf = new Uint32Array(0);
const counts = new Uint32Array(256);
// interlink polygon nodes in z-order: collect into an array, quicksort by z, relink
// interlink polygon nodes in z-order: collect into an array, sort by z, relink
/** @param {Node} start @param {number} minX @param {number} minY @param {number} invSize */

@@ -578,3 +551,3 @@ function indexCurve(start, minX, minY, invSize) {

quicksortNodes(sortArr, 0, n - 1);
sortNodes(n);

@@ -592,34 +565,47 @@ /** @type {Node | null} */

// quicksort an array of nodes by z; middle-element pivot + insertion sort for small ranges
/** @param {Node[]} arr @param {number} left @param {number} right */
function quicksortNodes(arr, left, right) {
while (right - left > 20) {
// middle pivot splits already-sorted/reversed runs evenly; real ring-order-by-z data
// is non-adversarial, so the median-of-three guard isn't needed
const pivot = arr[(left + right) >> 1].z;
let i = left, j = right, t;
while (i <= j) {
while (arr[i].z < pivot) i++;
while (arr[j].z > pivot) j--;
if (i <= j) { t = arr[i]; arr[i] = arr[j]; arr[j] = t; i++; j--; }
// sort the first n nodes of sortArr by z, in place: insertion sort for small n (cheaper
// than histogram setup), else LSD radix in four 8-bit passes (covering z's 30 bits)
/** @param {number} n */
function sortNodes(n) {
if (n <= 32) {
for (let i = 1; i < n; i++) {
const node = sortArr[i], z = node.z;
let j = i - 1;
while (j >= 0 && sortArr[j].z > z) { sortArr[j + 1] = sortArr[j]; j--; }
sortArr[j + 1] = node;
}
// recurse into the smaller half, loop on the larger to bound stack depth
if (j - left < right - i) {
quicksortNodes(arr, left, j);
left = i;
} else {
quicksortNodes(arr, i, right);
right = j;
}
return;
}
// insertion sort the small remaining range
for (let i = left + 1; i <= right; i++) {
const node = arr[i], z = node.z;
let j = i - 1;
while (j >= left && arr[j].z > z) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = node;
if (zArr.length < n) {
zArr = new Uint32Array(n);
zBuf = new Uint32Array(n);
sortBuf = new Array(n);
}
for (let i = 0; i < n; i++) zArr[i] = sortArr[i].z;
// even pass count lands the sorted result back in sortArr
radixPass(n, sortArr, zArr, sortBuf, zBuf, 0);
radixPass(n, sortBuf, zBuf, sortArr, zArr, 8);
radixPass(n, sortArr, zArr, sortBuf, zBuf, 16);
radixPass(n, sortBuf, zBuf, sortArr, zArr, 24);
}
// one LSD radix pass: stably scatter the first n nodes (and their z) from src to dst,
// bucketed by the 8-bit digit of z at the given bit shift
/** @param {number} n @param {Node[]} src @param {Uint32Array} srcZ @param {Node[]} dst @param {Uint32Array} dstZ @param {number} shift */
function radixPass(n, src, srcZ, dst, dstZ, shift) {
counts.fill(0);
for (let i = 0; i < n; i++) counts[(srcZ[i] >>> shift) & 0xff]++;
// turn per-bucket counts into start offsets (prefix sum)
let sum = 0;
for (let b = 0; b < 256; b++) { const c = counts[b]; counts[b] = sum; sum += c; }
for (let i = 0; i < n; i++) {
const z = srcZ[i];
const pos = counts[(z >>> shift) & 0xff]++;
dst[pos] = src[i];
dstZ[pos] = z;
}
}
// z-order of a point given coords and inverse of the longer side of data bbox

@@ -669,6 +655,6 @@ /** @param {number} x @param {number} y @param {number} minX @param {number} minY @param {number} invSize @returns {number} */

function isValidDiagonal(a, b) {
return a.next.i !== b.i && !intersectsPolygon(a, b) && // doesn't intersect other edges
(locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b) && // locally visible
(area(a.prev, a, b.prev) !== 0 || area(a, b.prev, b) !== 0) || // does not create opposite-facing sectors
equals(a, b) && area(a.prev, a, a.next) > 0 && area(b.prev, b, b.next) > 0); // special zero-length case
const zeroLength = equals(a, b) && area(a.prev, a, a.next) > 0 && area(b.prev, b, b.next) > 0; // degenerate case
return a.next.i !== b.i && (zeroLength || locallyInside(a, b) && locallyInside(b, a) && // // locally visible
(area(a.prev, a, b.prev) !== 0 || area(a, b.prev, b) !== 0)) && // no opposite-facing sectors
!intersectsPolygon(a, b) && (zeroLength || middleInside(a, b)); // doesn't intersect other edges, diagonal inside polygon
}

@@ -675,0 +661,0 @@