Convert Figma logo to code with AI

mapbox logoearcut

The fastest and smallest JavaScript polygon triangulation library for your WebGL apps

2,314
210
2,314
25
View on GitHubView on NPM

Top Related Projects

mapbox's avatar

supercluster

2,237

A very fast geospatial point clustering library for browsers and Node.

mapbox's avatar

geojson-vt

1,971

Slice GeoJSON into vector tiles on the fly in the browser

Quick Overview

Earcut is a fast, small, and robust polygon triangulation library for JavaScript and TypeScript. It is designed to be a high-performance, low-overhead solution for triangulating complex polygons, making it suitable for use in various geospatial and graphics applications.

Pros

  • High Performance: Earcut is known for its exceptional speed, making it a great choice for real-time applications that require fast polygon triangulation.
  • Robustness: The library is designed to handle complex and even self-intersecting polygons, ensuring reliable and accurate triangulation results.
  • Small Footprint: Earcut has a small file size, making it suitable for use in web-based and mobile applications where file size is a concern.
  • Cross-Platform Compatibility: Earcut is written in JavaScript and can be used in both browser-based and server-side (Node.js) environments.

Cons

  • Limited Functionality: Earcut is primarily focused on polygon triangulation and does not provide additional features like polygon clipping or boolean operations.
  • Lack of Documentation: The project's documentation could be more comprehensive, which may make it challenging for new users to get started.
  • Potential Precision Issues: In some cases, Earcut may produce triangulation results that are not pixel-perfect, which could be a concern for certain graphics applications.
  • No Official Maintenance: The project is not actively maintained by the Mapbox team, which could be a concern for long-term usage and potential bug fixes.

Code Examples

Here are a few examples of how to use Earcut in your JavaScript or TypeScript projects:

import earcut from 'earcut';

// Triangulate a simple polygon
const polygon = [[0, 0], [10, 0], [10, 10], [0, 10]];
const triangles = earcut(polygon);
console.log(triangles); // Output: [0, 1, 3, 1, 2, 3]

import earcut from 'earcut';

// Triangulate a polygon with holes
const polygon = [
  [0, 0], [10, 0], [10, 10], [0, 10], // Outer ring
  [2, 2], [4, 2], [4, 4], [2, 4] // Inner ring
];
const triangles = earcut(polygon, [8]); // Pass the hole indices
console.log(triangles); // Output: [0, 1, 3, 1, 2, 3, 4, 5, 7, 5, 6, 7]

import earcut from 'earcut';

// Triangulate a polygon with custom data
interface PolygonPoint {
  x: number;
  y: number;
  data: any;
}

const polygon: PolygonPoint[] = [
  { x: 0, y: 0, data: 'A' },
  { x: 10, y: 0, data: 'B' },
  { x: 10, y: 10, data: 'C' },
  { x: 0, y: 10, data: 'D' }
];

const triangles = earcut(
  polygon.flatMap(p => [p.x, p.y]),
  null,
  2
);

console.log(triangles.map(i => polygon[i]));
// Output: [
//   { x: 0, y: 0, data: 'A' },
//   { x: 10, y: 0, data: 'B' },
//   { x: 0, y: 10, data: 'D' }
// ]

Getting Started

To use Earcut in your project, you can install it via npm:

npm install earcut

Then, you can import the earcut function and use it to triangulate your polygons:

import earcut from 'earcut';

// Triangulate a polygon
const polygon = [[0, 0], [10, 0], [10, 10], [0, 10]];
const triangles = earcut(polygon);

// Use the triangles

Competitor Comparisons

mapbox logo

supercluster

2,237

A very fast geospatial point clustering library for browsers and Node.

Pros of Supercluster

  • Supercluster is a fast geospatial clustering library for rendering large datasets on maps.
  • It provides a simple and efficient way to cluster large sets of points on a map, making it suitable for use in web applications.
  • Supercluster supports a variety of input data formats, including GeoJSON, and can be easily integrated with popular mapping libraries like Mapbox GL JS.

Cons of Supercluster

  • Supercluster is primarily focused on clustering points, and may not be as well-suited for other types of geospatial data, such as polygons or lines.
  • The library can be more complex to set up and configure compared to simpler solutions like Earcut.
  • Supercluster may have a higher memory footprint than Earcut, especially for very large datasets.

Code Comparison

Earcut:

const earcut = require('earcut');
const data = [0, 0, 10, 0, 10, 10, 0, 10];
const holes = [];
const indices = earcut(data, holes, 2);

Supercluster:

const Supercluster = require('supercluster');
const index = Supercluster({
  radius: 40,
  maxZoom: 16
});
index.load([
  { type: 'Feature', geometry: { type: 'Point', coordinates: [0, 0] } },
  { type: 'Feature', geometry: { type: 'Point', coordinates: [10, 10] } }
]);
const clusters = index.getClusters([-180, -90, 180, 90], 1);
mapbox logo

geojson-vt

1,971

Slice GeoJSON into vector tiles on the fly in the browser

Pros of GeoJSON-VT

  • Optimizes GeoJSON data for fast rendering on the client-side, reducing the need for server-side processing.
  • Provides a simple and efficient API for querying and rendering vector tiles.
  • Supports advanced features like tile clipping, simplification, and indexing.

Cons of GeoJSON-VT

  • Requires the input data to be in GeoJSON format, which may not be suitable for all use cases.
  • May not be as performant as more specialized vector tile formats like Mapbox Vector Tiles.
  • Lacks some of the advanced features and customization options available in other vector tile libraries.

Code Comparison

GeoJSON-VT:

var tileIndex = geojsonvt(data, {
  maxZoom: 14,
  tolerance: 3,
  extent: 4096,
  buffer: 64
});

var tile = tileIndex.getTile(12, 656, 1583);

Earcut:

var triangles = earcut(data.coordinates[0], null, 2);

Convert Figma logo designs to code with AI

Visual Copilot

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

README

Earcut

The fastest and smallest JavaScript polygon triangulation library. 3KB gzipped.

Node Average time to resolve an issue Percentage of issues still open

The algorithm

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.

Why another triangulation library?

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)ptsearcutlibtesspoly2tripnltripolyk
OSM building15795,93550,64061,501122,966175,570
dude shape9435,65810,3398,78411,17213,557
holed dude shape10428,3198,8837,4942,130n/a
complex OSM water252354377.54failurefailuren/a
huge OSM water56679529.30failurefailuren/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.

Usage

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

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>

Ports to other languages

NPM DownloadsLast 30 Days