Security News
Supply Chain Attack Detected in Solana's web3.js Library
A supply chain attack has been detected in versions 1.95.6 and 1.95.7 of the popular @solana/web3.js library.
The fastest and smallest JavaScript polygon triangulation library for your WebGL apps
The earcut npm package is a JavaScript library for triangulating polygons for WebGL rendering. It is a fast, lightweight, and robust library for polygon triangulation, which is the process of converting polygons into triangles that can be used for rendering 3D graphics.
Polygon Triangulation
This feature allows you to triangulate a polygon with or without holes. The 'vertices' array contains the x and y coordinates of the polygon's vertices, 'holes' is an array of indices that mark the start of each hole in the vertex array, and 'dimensions' is the number of coordinates per vertex (2 for 2D polygons). The 'earcut' function returns an array of indices that map to the triangulated vertices.
const earcut = require('earcut');
const vertices = [10, 0, 0, 50, 60, 60, 70, 10];
const holes = [4];
const dimensions = 2;
const triangles = earcut(vertices, holes, dimensions);
poly2tri is another polygon triangulation library for use with WebGL. Unlike earcut, which uses a modified ear clipping algorithm, poly2tri implements a constrained Delaunay triangulation algorithm. It can handle complex polygons with holes and is robust in handling degenerate cases, but it may be slower than earcut for simple polygons.
trianglify is a library for generating colorful triangle meshes that can be used as SVG backgrounds. While it also performs triangulation, its primary focus is on creating aesthetically pleasing patterns rather than providing a robust triangulation tool for 3D rendering.
The fastest and smallest JavaScript polygon triangulation library. 3KB gzipped.
The library implements a modified ear slicing algorithm, optimized by z-order curve hashing and extended to handle holes, twisted polygons, degeneracies and self-intersections in a way that doesn't guarantee correctness of triangulation, but attempts to always produce acceptable results for practical data.
It's based on ideas from FIST: Fast Industrial-Strength Triangulation of Polygons by Martin Held and Triangulation by Ear Clipping by David Eberly.
The aim of this project is to create a JS triangulation library that is 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. Some benchmarks using Node 0.12:
(ops/sec) | pts | earcut | libtess | poly2tri | pnltri | polyk |
---|---|---|---|---|---|---|
OSM building | 15 | 795,935 | 50,640 | 61,501 | 122,966 | 175,570 |
dude shape | 94 | 35,658 | 10,339 | 8,784 | 11,172 | 13,557 |
holed dude shape | 104 | 28,319 | 8,883 | 7,494 | 2,130 | n/a |
complex OSM water | 2523 | 543 | 77.54 | failure | failure | n/a |
huge OSM water | 5667 | 95 | 29.30 | failure | failure | n/a |
The original use case it was created for is Mapbox GL, WebGL-based interactive maps.
If you want to get correct triangulation even on very bad data with lots of self-intersections and earcut is not precise enough, take a look at libtess.js.
const triangles = earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 3,2,1]
Signature: earcut(vertices[, holes, dimensions = 2])
.
vertices
is a flat array of vertex coordinates like [x0,y0, x1,y1, x2,y2, ...]
.holes
is an array of hole indices if any
(e.g. [5, 8]
for a 12-vertex input would mean one hole with vertices 5–7 and another with 8–11).dimensions
is the number of coordinates per vertex in the input array (2
by default). Only two are used for triangulation (x
and y
), and the rest are ignored.Each group of three vertex indices in the resulting array forms a triangle.
// triangulating a polygon with a hole
earcut([0,0, 100,0, 100,100, 0,100, 20,20, 80,20, 80,80, 20,80], [4]);
// [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]
// triangulating a polygon with 3d coords
earcut([10,0,1, 0,50,2, 60,60,3, 70,10,4], null, 3);
// [1,0,3, 3,2,1]
If you pass a single vertex as a hole, Earcut treats it as a Steiner point.
Note that Earcut is a 2D triangulation algorithm, and handles 3D data as if it was projected onto the XY plane (with Z component ignored).
If your input is a multi-dimensional array (e.g. GeoJSON Polygon),
you can convert it to the format expected by Earcut with earcut.flatten
:
const data = earcut.flatten(geojson.geometry.coordinates);
const triangles = earcut(data.vertices, data.holes, data.dimensions);
After getting a triangulation, you can verify its correctness with earcut.deviation
:
const deviation = earcut.deviation(vertices, holes, dimensions, triangles);
Returns the relative difference between the total area of triangles and the area of the input polygon.
0
means the triangulation is fully correct.
Install with NPM: npm install earcut
, then import as a module:
import earcut from 'earcut';
Or use as a module directly in the browser with jsDelivr:
<script type="module">
import earcut from 'https://cdn.jsdelivr.net/npm/earcut/+esm';
</script>
Alternatively, there's a UMD browser bundle with an earcut
global variable (exposing the main function as earcut.default
):
<script src="https://cdn.jsdelivr.net/npm/earcut/dist/earcut.min.js"></script>
FAQs
The fastest and smallest JavaScript polygon triangulation library for your WebGL apps
The npm package earcut receives a total of 1,148,920 weekly downloads. As such, earcut popularity was classified as popular.
We found that earcut demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 0 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
A supply chain attack has been detected in versions 1.95.6 and 1.95.7 of the popular @solana/web3.js library.
Research
Security News
A malicious npm package targets Solana developers, rerouting funds in 2% of transactions to a hardcoded address.
Security News
Research
Socket researchers have discovered malicious npm packages targeting crypto developers, stealing credentials and wallet data using spyware delivered through typosquats of popular cryptographic libraries.