{"id":15098,"library":"earcut","title":"Earcut - Polygon Triangulation","description":"Earcut is a JavaScript library designed for fast and lightweight polygon triangulation, primarily optimized for WebGL applications. The current stable version is 3.0.2. It aims to provide real-time triangulation performance in browsers by prioritizing raw speed and simplicity over guaranteed correctness for highly degenerate or self-intersecting polygons. It implements a modified ear slicing algorithm using z-order curve hashing, capable of handling holes, twisted polygons, degeneracies, and self-intersections. While it doesn't guarantee perfectly correct triangulation for all edge cases, it typically produces acceptable results for practical datasets. It differentiates itself from alternatives by its significant speed advantage, as evidenced by benchmarks, and was originally developed for Mapbox GL. Earcut is a 2D algorithm, and for 3D inputs, it processes data as if projected onto the XY plane, ignoring the Z-component.","status":"active","version":"3.0.2","language":"javascript","source_language":"en","source_url":"git://github.com/mapbox/earcut","tags":["javascript"],"install":[{"cmd":"npm install earcut","lang":"bash","label":"npm"},{"cmd":"yarn add earcut","lang":"bash","label":"yarn"},{"cmd":"pnpm add earcut","lang":"bash","label":"pnpm"}],"dependencies":[],"imports":[{"note":"Since v3.0.0, Earcut is published as an ES module and drops CommonJS support. Use `import` syntax for modern environments. For CommonJS compatibility, use version 2.2.4 or earlier.","wrong":"const earcut = require('earcut');","symbol":"earcut","correct":"import earcut from 'earcut';"},{"note":"The `flatten` utility is a static method on the default export, useful for converting multi-dimensional arrays (e.g., GeoJSON Polygon format) into the flat array format expected by `earcut`.","symbol":"earcut.flatten","correct":"import earcut from 'earcut';\nconst data = earcut.flatten([[0,0,1],[10,0,1],[10,10,1],[0,10,1]]);"},{"note":"For legacy UMD browser bundles (available in v3.0.0 and later), the main `earcut` function is exposed as `earcut.default` to align with ESM interoperability. Older UMD versions exposed it directly.","wrong":"const triangles = earcut([10,0, 0,50, 60,60, 70,10]);","symbol":"earcut in browser UMD","correct":"const triangles = earcut.default([10,0, 0,50, 60,60, 70,10]);"}],"quickstart":{"code":"import earcut from 'earcut';\n\n// Triangulate a simple polygon (e.g., a square)\nconst vertices = [0, 0, 100, 0, 100, 100, 0, 100];\nconst simpleTriangles = earcut(vertices);\nconsole.log('Simple Polygon Triangles:', simpleTriangles);\n// Expected: [1,0,3, 2,1,3]\n\n// Triangulate a polygon with a hole\nconst polygonWithHoleVertices = [\n  0,0, 100,0, 100,100, 0,100,  // Outer ring (4 vertices)\n  20,20, 80,20, 80,80, 20,80   // Inner ring (4 vertices)\n];\nconst holeIndices = [4]; // The hole starts at index 4 (5th vertex)\nconst holedTriangles = earcut(polygonWithHoleVertices, holeIndices);\nconsole.log('Polygon with Hole Triangles:', holedTriangles);\n// Expected: [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]\n\n// Example with 3D coordinates (Z-component is ignored)\nconst vertices3D = [10,0,1, 0,50,2, 60,60,3, 70,10,4];\nconst triangles3D = earcut(vertices3D, null, 3); // dimensions = 3\nconsole.log('3D Input (Z ignored) Triangles:', triangles3D);\n// Expected: [1,0,3, 3,2,1]","lang":"javascript","description":"Demonstrates basic polygon triangulation for both simple shapes and those with holes, including how 3D vertex data is handled (Z-component ignored)."},"warnings":[{"fix":"Migrate to ES module import syntax (`import earcut from 'earcut';`). If CommonJS compatibility is strictly required, pin to version 2.2.4 or earlier, or use a build tool that handles ESM to CJS transpilation.","message":"Version 3.0.0 switched to publishing as an ES module, dropping direct CommonJS support. Existing `require()` statements will fail.","severity":"breaking","affected_versions":">=3.0.0"},{"fix":"If IE11 compatibility is necessary, you must transpile Earcut in your build process (e.g., using Babel) to an older ES target.","message":"Version 3.0.0 adopted modern ES syntax, which dropped native support for Internet Explorer 11 (IE11).","severity":"breaking","affected_versions":">=3.0.0"},{"fix":"When using the UMD bundle in a browser, access the triangulation function via `earcut.default()` instead of `earcut()`.","message":"For UMD browser bundles generated from v3.0.0 onwards, the main Earcut function is exposed as `earcut.default`.","severity":"breaking","affected_versions":">=3.0.0"},{"fix":"Ensure your input data is suitable for 2D projection, or if the Z-axis is critical, consider alternative 3D triangulation or meshing libraries.","message":"Earcut is a 2D triangulation algorithm. When provided with 3D coordinates, it processes only the X and Y components, completely ignoring the Z-component.","severity":"gotcha","affected_versions":"all"},{"fix":"For applications requiring absolute geometric correctness on all inputs, especially highly pathological ones, consider more robust libraries like `libtess.js`, which implement different algorithms with stronger guarantees.","message":"Earcut prioritizes speed over guaranteed geometric correctness for highly complex, self-intersecting, or degenerate polygons. It might produce suboptimal or incorrect triangulations for such 'bad data'.","severity":"gotcha","affected_versions":"all"}],"env_vars":null,"last_verified":"2026-04-21T00:00:00.000Z","next_check":"2026-07-20T00:00:00.000Z","problems":[{"fix":"Update your import statement to `import earcut from 'earcut';` if using an ES module-aware environment, or revert to Earcut v2.2.4 for CommonJS compatibility.","cause":"Attempting to use `require('earcut')` in a CommonJS environment with Earcut v3.0.0+.","error":"TypeError: earcut is not a function"},{"fix":"Access the main function via `earcut.default()` for UMD bundles of version 3.0.0 and later.","cause":"Accessing `earcut()` directly in a browser environment using a UMD bundle of Earcut v3.0.0+.","error":"ReferenceError: earcut is not defined"},{"fix":"Verify that `vertices` is a flat array of numbers `[x0, y0, x1, y1, ...]` and `holes` contains valid start indices within the `vertices` array for each inner ring.","cause":"Providing an empty or malformed `vertices` array, or `holes` array with invalid indices that exceed the bounds of `vertices`.","error":"RangeError: Invalid array length"}],"ecosystem":"npm"}