earcut - npm Package Compare versions

Comparing version 3.1.1 to 3.2.0

dist/earcut.dev.js

@@ -883,5 +883,127 @@ (function (global, factory) {
 
+// Reusable module-level scratch for refine():
+//   he      = twin half-edge of each edge, or -1 on the polygon boundary
+//   hTable  = open-addressing hash, slot -> half-edge index, valid iff hStamp[slot] === gen
+/** @type {Int32Array} */ let edgeStack;
+/** @type {Int32Array} */ let he;
+/** @type {Int32Array} */ let hTable;
+/** @type {Uint32Array} */ let hStamp;
+let hMask = 0, gen = 0;
+
+/**
+ * Refine a triangulation toward the constrained Delaunay triangulation by legalizing every
+ * interior edge in place with Lawson flips — maximizing the minimum angle and removing most
+ * slivers. An optional post-pass for {@link earcut} output, or any manifold triangle-index array
+ * indexing into `coords`. Adapted from delaunator's edge legalization.
+ *
+ * Uses non-robust predicates: float input is fine, and the worst case is a not-quite-Delaunay
+ * edge, never an invalid mesh.
+ *
+ * @param {number[]} triangles triangle indices, as returned by {@link earcut}; mutated in place
+ * @param {ArrayLike<number>} coords the flat vertex coordinates passed to {@link earcut}
+ * @param {number} [dim=2] number of coordinates per vertex in `coords`
+ * @example refine(earcut(data), data);
+ */
+function refine(triangles, coords, dim = 2) {
+    const t = triangles;
+    const n = t.length;
+    const V = coords.length / dim;
+    ensureScratch(n);
+    gen++;              // bumping the generation logically empties the hash (no clearing)
+    he.fill(-1, 0, n);
+
+    // Build half-edge twins with an undirected-edge hash; consumed slots mark linked pairs.
+    for (let e = 0; e < n; e++) {
+        const a = t[e], b = t[nextHE(e)];
+        const lo = a < b ? a : b, hi = a < b ? b : a;
+        let h = ((hi * V + lo) * 0x9e3779b1 >>> 0) & hMask;
+        while (hStamp[h] === gen) {
+            const s = hTable[h];
+            // s === -1 marks a consumed slot (a pair already linked) — skip past it
+            if (s !== -1) {
+                const sa = t[s], sb = t[nextHE(s)];
+                if ((sa === lo && sb === hi) || (sa === hi && sb === lo)) {
+                    he[e] = s; he[s] = e; hTable[h] = -1; // link, then consume the slot
+                    break;
+                }
+            }
+            h = (h + 1) & hMask;
+        }
+        if (hStamp[h] !== gen) { hTable[h] = e; hStamp[h] = gen; } // first occurrence: insert
+    }
+
+    for (let e0 = 0; e0 < n; e0++) {
+        if (he[e0] === -1) continue;
+        let i = 0, a = e0;
+        while (true) {
+            const b = he[a];
+            const a0 = a - a % 3;
+            const ar = a0 + (a + 2) % 3;
+            if (b === -1) { if (i === 0) break; a = edgeStack[--i]; continue; }
+
+            const b0 = b - b % 3;
+            const al = a0 + (a + 1) % 3;
+            const bl = b0 + (b + 2) % 3;
+            const p0 = t[ar], pr = t[a], pl = t[al], p1 = t[bl];
+
+            const x0 = coords[p0 * dim], y0 = coords[p0 * dim + 1];
+            const xr = coords[pr * dim], yr = coords[pr * dim + 1];
+            const xl = coords[pl * dim], yl = coords[pl * dim + 1];
+            const x1 = coords[p1 * dim], y1 = coords[p1 * dim + 1];
+
+            // Both triangles of the flipped diagonal p0-p1 must be CCW (i.e. the quad is convex).
+            // Flipping a reflex quad would push a triangle outside the polygon; this guards against
+            // it. Boundary/hole edges need no guard — they self-protect via he === -1.
+            const convex = orient(x0, y0, xr, yr, x1, y1) > 0 && orient(x0, y0, x1, y1, xl, yl) > 0;
+
+            if (convex && !inCircle(x0, y0, xr, yr, xl, yl, x1, y1)) {
+                t[a] = p1; t[b] = p0;
+                const hbl = he[bl], har = he[ar];
+                he[a] = hbl; if (hbl !== -1) he[hbl] = a;
+                he[b] = har; if (har !== -1) he[har] = b;
+                he[ar] = bl; he[bl] = ar;
+                if (i < edgeStack.length) edgeStack[i++] = b0 + (b + 1) % 3;
+            } else {
+                if (i === 0) break;
+                a = edgeStack[--i];
+            }
+        }
+    }
+}
+
+/** @param {number} ax @param {number} ay @param {number} bx @param {number} by @param {number} cx @param {number} cy */
+function orient(ax, ay, bx, by, cx, cy) {
+    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
+}
+
+// Whether p is inside the circumcircle of triangle (a, b, c). Sign is negated vs the usual
+// predicate to match earcut's CCW winding — the standard sign would build the anti-Delaunay mesh.
+/** @param {number} ax @param {number} ay @param {number} bx @param {number} by @param {number} cx @param {number} cy @param {number} px @param {number} py */
+function inCircle(ax, ay, bx, by, cx, cy, px, py) {
+    const dx = ax - px, dy = ay - py, ex = bx - px, ey = by - py, fx = cx - px, fy = cy - py;
+    const ap = dx * dx + dy * dy, bp = ex * ex + ey * ey, cp = fx * fx + fy * fy;
+    return dx * (ey * cp - bp * fy) - dy * (ex * cp - bp * fx) + ap * (ex * fy - ey * fx) < 0;
+}
+
+/** @param {number} e */
+function nextHE(e) { // next half-edge within the same triangle
+    return e - e % 3 + (e + 1) % 3;
+}
+
+// Grow the scratch arrays on demand (like earcut's z-order arrays). Allocating lazily here rather
+// than at module load lets the whole refine() block tree-shake away for callers who don't use it.
+/** @param {number} n */
+function ensureScratch(n) {
+    if (!edgeStack) edgeStack = new Int32Array(512);
+    if (!he || he.length < n) he = new Int32Array(n);
+    let size = 1;
+    while (size < n * 4) size <<= 1; // power-of-two table, load factor <= 0.25
+    if (!hTable || hTable.length < size) { hTable = new Int32Array(size); hStamp = new Uint32Array(size); }
+    hMask = size - 1;
+}
+
 exports.default = earcut;
 exports.deviation = deviation;
 exports.flatten = flatten;
+exports.refine = refine;
 
@@ -888,0 +1010,0 @@ Object.defineProperty(exports, '__esModule', { value: true });

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;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})});
+!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 r(t,n,e,r,x){let o=null;if(x===G(t,n,e,r)>0)for(let x=n;x<e;x+=r)o=C(x/r|0,t[x],t[x+1],o);else for(let x=e-r;x>=n;x-=r)o=C(x/r|0,t[x],t[x+1],o);return o&&O(o,o.next)&&(D(o),o=o.next),o}function x(t,r=t){const x=r===t;let o,i=t;do{o=!1,i===i.next||0!==n.size&&n.has(i)||!O(i,i.next)&&0!==_(i.prev,i,i.next)?(x||i!==r)&&(i=i.next,o=!x):((x||i===r)&&(r=i.prev),e=!0,D(i),i=i.prev,o=!0)}while(o||i!==r);return r}function o(t,n,r,o,c){c&&function(t,n,e,r){let x=t,o=0;do{x.z=I(x.x,x.y,n,e,r),Z[o++]=x,x=x.next}while(x!==t);!function(t){if(t<=32){for(let n=1;n<t;n++){const t=Z[n],e=t.z;let r=n-1;for(;r>=0&&Z[r].z>e;)Z[r+1]=Z[r],r--;Z[r+1]=t}return}A.length<t&&(A=new Uint32Array(t),z=new Uint32Array(t),b=new Array(t));for(let n=0;n<t;n++)A[n]=Z[n].z;k(t,Z,A,b,z,0),k(t,b,z,Z,A,8),k(t,Z,A,b,z,16),k(t,b,z,Z,A,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,r,o,c);let y=t,s=!1;for(;t.prev!==t.next;){const a=t.prev,h=t.next;if(_(a,t,h)<0&&(c?l(t,r,o,c):i(t)))n.push(a.i,t.i,h.i),D(t),t=h,y=h;else if((t=h)===y){if(e=!1,t=x(t),e){y=t;continue}if(!s){y=t=f(t,n),s=!0;continue}u(t,n,r,o,c);break}}}function i(t){const n=t.prev,e=t,r=t.next,x=n.x,o=e.x,i=r.x,l=n.y,f=e.y,u=r.y,c=Math.min(x,o,i),y=Math.min(l,f,u),s=Math.max(x,o,i),a=Math.max(l,f,u);let h=r.next;for(;h!==n;){if(h.x>=c&&h.x<=s&&h.y>=y&&h.y<=a&&(x!==h.x||l!==h.y)&&F(x,l,o,f,i,u,h.x,h.y)&&_(h.prev,h,h.next)>=0)return!1;h=h.next}return!0}function l(t,n,e,r){const x=t.prev,o=t,i=t.next,l=x.x,f=o.x,u=i.x,c=x.y,y=o.y,s=i.y,a=Math.min(l,f,u),h=Math.min(c,y,s),p=Math.max(l,f,u),v=Math.max(c,y,s),d=I(a,h,n,e,r),M=I(p,v,n,e,r);let g=t.prevZ;for(;g&&g.z>=d;){if(g.x>=a&&g.x<=p&&g.y>=h&&g.y<=v&&g!==i&&(l!==g.x||c!==g.y)&&F(l,c,f,y,u,s,g.x,g.y)&&_(g.prev,g,g.next)>=0)return!1;g=g.prevZ}let w=t.nextZ;for(;w&&w.z<=M;){if(w.x>=a&&w.x<=p&&w.y>=h&&w.y<=v&&w!==i&&(l!==w.x||c!==w.y)&&F(l,c,f,y,u,s,w.x,w.y)&&_(w.prev,w,w.next)>=0)return!1;w=w.nextZ}return!0}function f(t,n){let e=t,r=!1;do{const x=e.prev,o=e.next.next;P(x,e,e.next,o,!1)&&q(x,o)&&q(o,x)&&(n.push(x.i,e.i,o.i),D(e),D(e.next),e=t=o,r=!0),e=e.next}while(e!==t);return r?x(e):e}function u(t,n,e,r,i){let l=t;do{let t=l.next.next;for(;t!==l.prev;){if(l.i!==t.i&&T(l,t)){let f=B(l,t);return l=x(l,l.next),f=x(f,f.next),o(l,n,e,r,i),void o(f,n,e,r,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 r=t.x,x=t.y;let o,i=-1/0;if(O(t,e))return e;for(let n=0,l=0;n<p;n++,l+=4){if(x<h[l+1]||x>h[l+3]||h[l]>r||h[l+2]<=i)continue;const f=g(n);e=w(n);do{if(e.prev.next===e){if(O(t,e.next))return e.next;if(x<=e.y&&x>=e.next.y&&e.next.y!==e.y){const t=e.x+(x-e.y)*(e.next.x-e.x)/(e.next.y-e.y);if(t<=r&&t>i&&(i=t,o=e.x<e.next.x?e:e.next,t===r))return o}}e=e.next}while(e!==f)}if(!o)return null;const l=o.x,f=o.y,u=Math.min(x,f),c=Math.max(x,f);let y=1/0;for(let n=0,s=0;n<p;n++,s+=4){if(h[s+2]<l||h[s]>r||h[s+3]<u||h[s+1]>c)continue;const a=g(n);e=w(n);do{if(e.prev.next===e&&r>=e.x&&e.x>=l&&r!==e.x&&F(x<f?r:i,x,l,f,x<f?i:r,x,e.x,e.y)){const n=Math.abs(x-e.y)/(r-e.x);(q(e,t)||e.y===x&&e.next.y===x&&e.next.x>r)&&(n<y||n===y&&(e.x>o.x||e.x===o.x&&m(o,e)))&&(o=e,y=n)}e=e.next}while(e!==a)}return o}(t,n);if(!e)return n;const r=B(e,t);return M(e,r.next.next),x(r,r.next),x(e,e.next)}const a=16;let h=new Float64Array(0),p=0;const v=[],d=[];function M(t,n){let e=t;do{const t=p++;v[t]=e;let r=1/0,x=1/0,o=-1/0,i=-1/0,l=0;do{const n=e.next;e.z=t,e.x<r&&(r=e.x),e.x>o&&(o=e.x),e.y<x&&(x=e.y),e.y>i&&(i=e.y),n.x<r&&(r=n.x),n.x>o&&(o=n.x),n.y<x&&(x=n.y),n.y>i&&(i=n.y),e=n}while(++l<a&&e!==n);d[t]=e;const f=4*t;h[f]=r,h[f+1]=x,h[f+2]=o,h[f+3]=i}while(e!==n)}function g(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 m(t,n){return _(t.prev,t,n.prev)<0&&_(n.next,t,t.next)<0}const Z=[];let b=[],A=new Uint32Array(0),z=new Uint32Array(0);const U=new Uint32Array(256);function k(t,n,e,r,x,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]++;r[l]=n[i],x[l]=t}}function I(t,n,e,r,x){return(t=1431655765&((t=858993459&((t=252645135&((t=16711935&((t=(t-e)*x|0)|t<<8))|t<<4))|t<<2))|t<<1))|(n=1431655765&((n=858993459&((n=252645135&((n=16711935&((n=(n-r)*x|0)|n<<8))|n<<4))|n<<2))|n<<1))<<1}function j(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 F(t,n,e,r,x,o,i,l){return(x-i)*(n-l)>=(t-i)*(o-l)&&(t-i)*(r-l)>=(e-i)*(n-l)&&(e-i)*(o-l)>=(x-i)*(r-l)}function T(t,n){const e=O(t,n)&&_(t.prev,t,t.next)>0&&_(n.prev,n,n.next)>0;return t.next.i!==n.i&&(e||q(t,n)&&q(n,t)&&(0!==_(t.prev,t,n.prev)||0!==_(t,n.prev,n)))&&!function(t,n){const e=Math.min(t.x,n.x),r=Math.max(t.x,n.x),x=Math.min(t.y,n.y),o=Math.max(t.y,n.y);let i=t;do{const l=i.next;if(i.x>r&&l.x>r||i.x<e&&l.x<e||i.y>o&&l.y>o||i.y<x&&l.y<x)i=l;else{if(i.i!==t.i&&l.i!==t.i&&i.i!==n.i&&l.i!==n.i&&P(i,l,t,n))return!0;i=l}}while(i!==t);return!1}(t,n)&&(e||function(t,n){let e=t,r=!1;const x=(t.x+n.x)/2,o=(t.y+n.y)/2;do{const t=e.next;e.y>o!=t.y>o&&x<(t.x-e.x)*(o-e.y)/(t.y-e.y)+e.x&&(r=!r),e=t}while(e!==t);return r}(t,n))}function _(t,n,e){return(n.y-t.y)*(e.x-n.x)-(n.x-t.x)*(e.y-n.y)}function O(t,n){return t.x===n.x&&t.y===n.y}function P(t,n,e,r,x=!0){const o=_(t,n,e),i=_(t,n,r),l=_(e,r,t),f=_(e,r,n);return(o>0&&i<0||o<0&&i>0)&&(l>0&&f<0||l<0&&f>0)||!!x&&(!(0!==o||!S(t,e,n))||(!(0!==i||!S(t,r,n))||(!(0!==l||!S(e,t,r))||!(0!==f||!S(e,n,r)))))}function S(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 q(t,n){return _(t.prev,t,t.next)<0?_(t,n,t.next)>=0&&_(t,t.prev,n)>=0:_(t,n,t.prev)<0||_(t,t.next,n)<0}function B(t,n){const e=E(t.i,t.x,t.y),r=E(n.i,n.x,n.y),x=t.next,o=n.prev;return t.next=n,n.prev=t,e.next=x,x.prev=e,r.next=e,e.prev=r,o.next=r,r.prev=o,r}function C(t,n,e,r){const x=E(t,n,e);return r?(x.next=r.next,x.prev=r,r.next.prev=x,r.next=x):(x.prev=x,x.next=x),x}function D(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<h[e]&&(h[e]=n.x),n.y<h[e+1]&&(h[e+1]=n.y),n.x>h[e+2]&&(h[e+2]=n.x),n.y>h[e+3]&&(h[e+3]=n.y)}(t.prev,t.next)}function E(t,n,e){return{i:t,x:n,y:e,prev:null,next:null,z:0,prevZ:null,nextZ:null}}function G(t,n,e,r){let x=0;for(let o=n,i=e-r;o<e;o+=r)x+=(t[i]-t[o])*(t[o+1]+t[i+1]),i=o;return x}let H,J,K,L,N=0,Q=0;function R(t,n,e,r,x,o){return(e-t)*(o-n)-(r-n)*(x-t)}function V(t,n,e,r,x,o,i,l){const f=t-i,u=n-l,c=e-i,y=r-l,s=x-i,a=o-l,h=c*c+y*y,p=s*s+a*a;return f*(y*p-h*a)-u*(c*p-h*s)+(f*f+u*u)*(c*a-y*s)<0}function W(t){return t-t%3+(t+1)%3}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=r(t,0,f,i,!0);const v=[];if(!u||u.next===u.prev)return v;let d=0,g=0,w=0;if(l&&(u=function(t,e,o,i){const l=[];for(let x=0,o=e.length;x<o;x++){const f=r(t,e[x]*i,x<o-1?e[x+1]*i:t.length,i,!1);f===f.next&&n.add(f),l.push(j(f))}l.sort(y),function(t,n){const e=Math.ceil((t+2*n)/a)+n+2;h.length<4*e&&(h=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,x(o)}(t,e,u,i)),t.length>80*i){d=t[0],g=t[1];let n=d,e=g;for(let r=i;r<f;r+=i){const x=t[r],o=t[r+1];x<d&&(d=x),o<g&&(g=o),x>n&&(n=x),o>e&&(e=o)}w=Math.max(n-d,e-g),w=0!==w?32767/w:0}return o(u,v,d,g,w),v},t.deviation=function(t,n,e,r){const x=n&&n.length,o=x?n[0]*e:t.length;let i=Math.abs(G(t,0,o,e));if(x)for(let r=0,x=n.length;r<x;r++){const o=n[r]*e,l=r<x-1?n[r+1]*e:t.length;i-=Math.abs(G(t,o,l,e))}let l=0;for(let n=0;n<r.length;n+=3){const x=r[n]*e,o=r[n+1]*e,i=r[n+2]*e;l+=Math.abs((t[x]-t[i])*(t[o+1]-t[x+1])-(t[x]-t[o])*(t[i+1]-t[x+1]))}return 0===i&&0===l?0:Math.abs((l-i)/i)},t.flatten=function(t){const n=[],e=[],r=t[0][0].length;let x=0,o=0;for(const i of t){for(const t of i)for(let e=0;e<r;e++)n.push(t[e]);o&&(x+=o,e.push(x)),o=i.length}return{vertices:n,holes:e,dimensions:r}},t.refine=function(t,n,e=2){const r=t,x=r.length,o=n.length/e;!function(t){H||(H=new Int32Array(512));(!J||J.length<t)&&(J=new Int32Array(t));let n=1;for(;n<4*t;)n<<=1;(!K||K.length<n)&&(K=new Int32Array(n),L=new Uint32Array(n));N=n-1}(x),Q++,J.fill(-1,0,x);for(let t=0;t<x;t++){const n=r[t],e=r[W(t)],x=n<e?n:e,i=n<e?e:n;let l=2654435761*(i*o+x)>>>0&N;for(;L[l]===Q;){const n=K[l];if(-1!==n){const e=r[n],o=r[W(n)];if(e===x&&o===i||e===i&&o===x){J[t]=n,J[n]=t,K[l]=-1;break}}l=l+1&N}L[l]!==Q&&(K[l]=t,L[l]=Q)}for(let t=0;t<x;t++){if(-1===J[t])continue;let x=0,o=t;for(;;){const t=J[o],i=o-o%3,l=i+(o+2)%3;if(-1===t){if(0===x)break;o=H[--x];continue}const f=t-t%3,u=i+(o+1)%3,c=f+(t+2)%3,y=r[l],s=r[o],a=r[u],h=r[c],p=n[y*e],v=n[y*e+1],d=n[s*e],M=n[s*e+1],g=n[a*e],w=n[a*e+1],m=n[h*e],Z=n[h*e+1];if(R(p,v,d,M,m,Z)>0&&R(p,v,m,Z,g,w)>0&&!V(p,v,d,M,g,w,m,Z)){r[o]=h,r[t]=y;const n=J[c],e=J[l];J[o]=n,-1!==n&&(J[n]=o),J[t]=e,-1!==e&&(J[e]=t),J[l]=c,J[c]=l,x<H.length&&(H[x++]=f+(t+1)%3)}else{if(0===x)break;o=H[--x]}}}},Object.defineProperty(t,"__esModule",{value:!0})});

package.json

 {
   "name": "earcut",
-  "version": "3.1.1",
+  "version": "3.2.0",
   "description": "The fastest and smallest JavaScript polygon triangulation library for your WebGL apps",
   "main": "src/earcut.js",
   "type": "module",
+  "sideEffects": false,
   "exports": "./src/earcut.js",
@@ -8,0 +9,0 @@ "types": "src/earcut.d.ts",

README.md

 # Earcut
 
-The fastest and smallest JavaScript **polygon triangulation** library. 3.5KB gzipped.
+The fastest and smallest JavaScript **polygon triangulation** library. 4KB gzipped.
+[![Node](https://github.com/mapbox/earcut/actions/workflows/node.yml/badge.svg)](https://github.com/mapbox/earcut/actions/workflows/node.yml)
+[![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
 
-It is designed to be fast enough for real-time triangulation in the browser,
-sacrificing triangulation quality for raw speed and simplicity,
-while being robust enough to handle most practical datasets without crashing or producing garbage.
+![Earcut triangulation example](earcut.png)
+
+Earcut is designed to be fast enough for real-time [triangulation](https://en.wikipedia.org/wiki/Polygon_triangulation) in the browser,
+favoring raw speed and simplicity over triangulation quality,
+while being robust enough to handle most practical datasets without crashing or producing garbage,
+with an option to refine the result to [Delaunay](https://en.wikipedia.org/wiki/Delaunay_triangulation) quality at a small cost.
 Originally built for [Mapbox GL JS](https://www.mapbox.com/mapbox-gljs) (WebGL-based interactive maps),
 it's now also used by [Three.js](https://threejs.org/) and many other projects.
 
-![Earcut triangulation example](earcut.png)
+## [Demo](https://mapbox.github.io/earcut/viz/)
 
-[![Node](https://github.com/mapbox/earcut/actions/workflows/node.yml/badge.svg)](https://github.com/mapbox/earcut/actions/workflows/node.yml)
-[![Average time to resolve an issue](http://isitmaintained.com/badge/resolution/mapbox/earcut.svg)](http://isitmaintained.com/project/mapbox/earcut "Average time to resolve an issue")
-[![Percentage of issues still open](http://isitmaintained.com/badge/open/mapbox/earcut.svg)](http://isitmaintained.com/project/mapbox/earcut "Percentage of issues still open")
-[![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
-
 ## Usage
@@ -42,3 +42,4 @@
 benchmark of **119,680 real-world polygons** (1.9M vertices) drawn from a window of map tiles
-through zooms 4–16, it triangulates the whole set in **~480 ms** on a Macbook Pro M1 Pro (2021).
+through zooms 4–16, it triangulates the whole set in **~445 ms** on a Macbook Pro M1 Pro (2021),
+with optional Delaunay refinement taking additional **~184 ms**.
 You can run the benchmark yourself with `npm run bench`.
@@ -66,3 +67,3 @@
 ```js
-import earcut, {flatten, deviation} from 'earcut';
+import earcut, {flatten, deviation, refine} from 'earcut';
 ```
@@ -109,2 +110,19 @@
 
+### `refine(triangles, vertices[, dimensions = 2])`
+
+If triangle quality matters, you can run an optional refinement pass after triangulation:
+
+```js
+const triangles = earcut(vertices, holes, dimensions);
+refine(triangles, vertices, dimensions);
+```
+
+This mutates `triangles` in place, legalizing interior edges with Delaunay flips while preserving
+the polygon boundary and holes. It keeps the same number of triangles and the same index format,
+but usually removes many skinny triangles and reduces total triangle edge length.
+
+Refinement is a post-process, so it doesn't affect the speed of normal `earcut` calls unless you
+explicitly call it. It assumes a valid manifold triangulation, such as the output of `earcut`, and
+doesn't repair invalid polygon input or make the mesh conforming.
+
 ### `flatten(data)`
@@ -111,0 +129,0 @@

src/earcut.d.ts

@@ -36,2 +36,17 @@ /**
 /**
+ * Refine a triangulation toward the constrained Delaunay triangulation by legalizing every
+ * interior edge in place with Lawson flips — maximizing the minimum angle and removing most
+ * slivers. An optional post-pass for {@link earcut} output, or any manifold triangle-index array
+ * indexing into `coords`. Adapted from delaunator's edge legalization.
+ *
+ * Uses non-robust predicates: float input is fine, and the worst case is a not-quite-Delaunay
+ * edge, never an invalid mesh.
+ *
+ * @param {number[]} triangles triangle indices, as returned by {@link earcut}; mutated in place
+ * @param {ArrayLike<number>} coords the flat vertex coordinates passed to {@link earcut}
+ * @param {number} [dim=2] number of coordinates per vertex in `coords`
+ * @example refine(earcut(data), data);
+ */
+export function refine(triangles: number[], coords: ArrayLike<number>, dim?: number): void;
+/**
  * A vertex in a circular doubly linked list representing a polygon ring.
@@ -38,0 +53,0 @@ * `prev`/`next` are always linked (set immediately after {@link createNode}), so they're typed

src/earcut.js

@@ -876,1 +876,122 @@ /**
 }
+
+// Reusable module-level scratch for refine():
+//   he      = twin half-edge of each edge, or -1 on the polygon boundary
+//   hTable  = open-addressing hash, slot -> half-edge index, valid iff hStamp[slot] === gen
+/** @type {Int32Array} */ let edgeStack;
+/** @type {Int32Array} */ let he;
+/** @type {Int32Array} */ let hTable;
+/** @type {Uint32Array} */ let hStamp;
+let hMask = 0, gen = 0;
+
+/**
+ * Refine a triangulation toward the constrained Delaunay triangulation by legalizing every
+ * interior edge in place with Lawson flips — maximizing the minimum angle and removing most
+ * slivers. An optional post-pass for {@link earcut} output, or any manifold triangle-index array
+ * indexing into `coords`. Adapted from delaunator's edge legalization.
+ *
+ * Uses non-robust predicates: float input is fine, and the worst case is a not-quite-Delaunay
+ * edge, never an invalid mesh.
+ *
+ * @param {number[]} triangles triangle indices, as returned by {@link earcut}; mutated in place
+ * @param {ArrayLike<number>} coords the flat vertex coordinates passed to {@link earcut}
+ * @param {number} [dim=2] number of coordinates per vertex in `coords`
+ * @example refine(earcut(data), data);
+ */
+export function refine(triangles, coords, dim = 2) {
+    const t = triangles;
+    const n = t.length;
+    const V = coords.length / dim;
+    ensureScratch(n);
+    gen++;              // bumping the generation logically empties the hash (no clearing)
+    he.fill(-1, 0, n);
+
+    // Build half-edge twins with an undirected-edge hash; consumed slots mark linked pairs.
+    for (let e = 0; e < n; e++) {
+        const a = t[e], b = t[nextHE(e)];
+        const lo = a < b ? a : b, hi = a < b ? b : a;
+        let h = ((hi * V + lo) * 0x9e3779b1 >>> 0) & hMask;
+        while (hStamp[h] === gen) {
+            const s = hTable[h];
+            // s === -1 marks a consumed slot (a pair already linked) — skip past it
+            if (s !== -1) {
+                const sa = t[s], sb = t[nextHE(s)];
+                if ((sa === lo && sb === hi) || (sa === hi && sb === lo)) {
+                    he[e] = s; he[s] = e; hTable[h] = -1; // link, then consume the slot
+                    break;
+                }
+            }
+            h = (h + 1) & hMask;
+        }
+        if (hStamp[h] !== gen) { hTable[h] = e; hStamp[h] = gen; } // first occurrence: insert
+    }
+
+    for (let e0 = 0; e0 < n; e0++) {
+        if (he[e0] === -1) continue;
+        let i = 0, a = e0;
+        while (true) {
+            const b = he[a];
+            const a0 = a - a % 3;
+            const ar = a0 + (a + 2) % 3;
+            if (b === -1) { if (i === 0) break; a = edgeStack[--i]; continue; }
+
+            const b0 = b - b % 3;
+            const al = a0 + (a + 1) % 3;
+            const bl = b0 + (b + 2) % 3;
+            const p0 = t[ar], pr = t[a], pl = t[al], p1 = t[bl];
+
+            const x0 = coords[p0 * dim], y0 = coords[p0 * dim + 1];
+            const xr = coords[pr * dim], yr = coords[pr * dim + 1];
+            const xl = coords[pl * dim], yl = coords[pl * dim + 1];
+            const x1 = coords[p1 * dim], y1 = coords[p1 * dim + 1];
+
+            // Both triangles of the flipped diagonal p0-p1 must be CCW (i.e. the quad is convex).
+            // Flipping a reflex quad would push a triangle outside the polygon; this guards against
+            // it. Boundary/hole edges need no guard — they self-protect via he === -1.
+            const convex = orient(x0, y0, xr, yr, x1, y1) > 0 && orient(x0, y0, x1, y1, xl, yl) > 0;
+
+            if (convex && !inCircle(x0, y0, xr, yr, xl, yl, x1, y1)) {
+                t[a] = p1; t[b] = p0;
+                const hbl = he[bl], har = he[ar];
+                he[a] = hbl; if (hbl !== -1) he[hbl] = a;
+                he[b] = har; if (har !== -1) he[har] = b;
+                he[ar] = bl; he[bl] = ar;
+                if (i < edgeStack.length) edgeStack[i++] = b0 + (b + 1) % 3;
+            } else {
+                if (i === 0) break;
+                a = edgeStack[--i];
+            }
+        }
+    }
+}
+
+/** @param {number} ax @param {number} ay @param {number} bx @param {number} by @param {number} cx @param {number} cy */
+function orient(ax, ay, bx, by, cx, cy) {
+    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
+}
+
+// Whether p is inside the circumcircle of triangle (a, b, c). Sign is negated vs the usual
+// predicate to match earcut's CCW winding — the standard sign would build the anti-Delaunay mesh.
+/** @param {number} ax @param {number} ay @param {number} bx @param {number} by @param {number} cx @param {number} cy @param {number} px @param {number} py */
+function inCircle(ax, ay, bx, by, cx, cy, px, py) {
+    const dx = ax - px, dy = ay - py, ex = bx - px, ey = by - py, fx = cx - px, fy = cy - py;
+    const ap = dx * dx + dy * dy, bp = ex * ex + ey * ey, cp = fx * fx + fy * fy;
+    return dx * (ey * cp - bp * fy) - dy * (ex * cp - bp * fx) + ap * (ex * fy - ey * fx) < 0;
+}
+
+/** @param {number} e */
+function nextHE(e) { // next half-edge within the same triangle
+    return e - e % 3 + (e + 1) % 3;
+}
+
+// Grow the scratch arrays on demand (like earcut's z-order arrays). Allocating lazily here rather
+// than at module load lets the whole refine() block tree-shake away for callers who don't use it.
+/** @param {number} n */
+function ensureScratch(n) {
+    if (!edgeStack) edgeStack = new Int32Array(512);
+    if (!he || he.length < n) he = new Int32Array(n);
+    let size = 1;
+    while (size < n * 4) size <<= 1; // power-of-two table, load factor <= 0.25
+    if (!hTable || hTable.length < size) { hTable = new Int32Array(size); hStamp = new Uint32Array(size); }
+    hMask = size - 1;
+}

No alert changes

Improved metrics

Total package byte prevSize

104094

15.83%

Lines of code

1850

14.84%

Number of lines in readme file

155

13.14%

No dependency changes