mapbox / earcut Goto Github PK

View Code? Open in Web Editor NEW

2.1K 165.0 204.0 751 KB

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

License: ISC License

HTML 1.37% JavaScript 98.63%

triangulation tessellation polygon algorithm computational-geometry javascript

earcut's Introduction

Earcut

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

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)	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.

Usage

var 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:

var data = earcut.flatten(geojson.geometry.coordinates);
var triangles = earcut(data.vertices, data.holes, data.dimensions);

After getting a triangulation, you can verify its correctness with earcut.deviation:

var 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

NPM and Browserify:

npm install earcut

Browser builds on CDN:

Running tests:

npm test

Ports to other languages

Changelog

2.2.4 (Jul 5, 2022)

Improved performance by 10–15%.
Fixed another rare race condition that could lead to an infinite loop.

2.2.3 (Jul 8, 2021)

Fixed a rare race condition that could lead to an infinite loop.

2.2.2 (Jan 21, 2020)

Fixed yet another rare race condition when a hole shared an edge with an outer ring.

2.2.1 (Sep 19, 2019)

Fixed another rare case with touching holes.

2.2.0 (Sep 18, 2019)

Fixed a handful of rare race conditions.

2.1.5 (Feb 5, 2019)

Fixed a race condition with coincident holes that could lead to bad triangulation.

2.1.4 (Dec 4, 2018)

Fixed a race condition that could lead to a freeze on degenerate input.

2.1.3 (Jan 4, 2018)

Improved performance for bigger inputs (5-12%).

2.1.2 (Oct 23, 2017)

Fixed a few race conditions where bad input would cause an error.

2.1.1 (Mar 17, 2016)

Fixed a rare race condition where the split routine would choose bad diagonals.
Fixed a rare race condition in the "cure local intersections" routine.
Fixed a rare race condition where a hole that shares a point with the outer ring would be handled incorrectly.
Fixed a bug where a closing point wouldn't be filtered as duplicate, sometimes breaking triangulation.

2.1.0 (Mar 11, 2016)

Added earcut.deviation function for verifying correctness of triangulation.
Added earcut.flatten function for converting GeoJSON-like input into a format Earcut expects.

2.0.9 (Mar 10, 2016)

Fixed a rare race condition where a hole would be handled incorrectly.

2.0.8 (Jan 19, 2016)

Fixed a rare race condition with a hole touching outer ring.

2.0.7 (Nov 18, 2015)

Changed the algorithm to avoid filtering colinear/duplicate vertices unless it can't triangulate the polygon otherwise. Improves performance on simpler shapes and fixes some 3D use cases.

2.0.6 (Oct 26, 2015)

Improved robustness and reliability of the triangulation algorithm.
Improved performance by up to 15%.
Significantly improved source code clarity.

2.0.5 (Oct 12, 2015)

Fixed a z-curve hashing bug that could lead to unexpected results in very rare cases involving shapes with lots of points.

2.0.4 (Oct 8, 2015)

Fixed one more extremely rare race condition, lol!

2.0.3 (Oct 8, 2015)

Fixed yet another rare race condition (multiple holes connected with colinear bridges).
Fixed crash on empty input.

2.0.2 (Jul 8, 2015)

Fixed one more rare race condition with a holed polygon.

2.0.1 (May 11, 2015)

Added Steiner points support.

2.0.0 (Apr 30, 2015)

Breaking: changed the API to accept a flat input array of vertices with hole indices and return triangle indices. It makes the indexed output much faster than it was before (up to 30%) and improves memory footprint.

1.4.2 (Mar 18, 2015)

Fixed another rare edge case with a tiny hole in a huge polygon.

1.4.1 (Mar 17, 2015)

Fixed a rare edge case that led to incomplete triangulation.

1.4.0 (Mar 9, 2015)

Fixed indexed output to produce indices not multiplied by dimension and work with any number of dimensions.

1.3.0 (Feb 24, 2015)

Added a second argument to earcut that switches output format to flat vertex and index arrays if set to true.

1.2.3 (Feb 10, 2015)

Improved performance (especially on recent v8) by avoiding Array push with multiple arguments.

1.2.2 (Jan 27, 2015)

Significantly improved performance for polygons with self-intersections (e.g. big OSM water polygons are now handled 2-3x faster)

1.2.1 (Jan 26, 2015)

Significantly improved performance on polygons with high number of vertices by using z-order curve hashing for vertex lookup.
Slightly improved overall performance with better point filtering.

1.1.0 (Jan 21, 2015)

Improved performance on polygons with holes by switching from Held to Eberly hole elimination algorithm
More robustness fixes and tests

1.0.1 — 1.0.6 (Jan 20, 2015)

Various robustness improvements and fixes.

1.0.0 (Jan 18, 2015)

Initial release.

earcut's People

Contributors

Stargazers

Watchers

Forkers

devil6666 gijs istoramandiri f4-group ezhangle thekashey trufi bot-b wanby iominh flimshaw dreamind mcanthony degot achirkin andreasplesch robertleeplummerjr wilt cnc-viewer hjanetzek kkotaro0111 bathlamos hdachev bagnell jjviscomi diaosenfa zhangwenjin sumbera rhuitl gaiyangjun npmcdn-to-unpkg-bot korczis srowhani wubenhe finscn brucelicong coyotey nickli sushrut141 cuulee weilix88 hotnany 1wheel testbigorg lyuehh maxgraey brendancol cawfree meai1 alexxnica kryndex fossabot ckehl anr2me kcoley dzw isaomatsunami deniscarriere naridal gbyfbi linebreaker rubythonode lovedna monschine codefalter ispring lucaslattari dhilip89 pengkan90 dlukashanets andarist lixun910 nicolasserrano sabrinaayu anke522 wegiangb liujiusheng dpmcmlxxvi fenghuif deployruby seem-sky hedonghuasir algorithms-gad nswamy14 opencai jhhsia tong3d sermonis forkkit qingfengyijiu jiaguobing yeeway lacerba haoyanioz dandandancj wanghuaichen gnaaobd a402539 weihongli2019 stewartoallen

earcut's Issues

Could the result of earcut be used as NavMesh in pathfinding ?

The sizes the triangles in result of earcut are uneven.

If I use them as NavMesh , are there some problems ?

going from 1.4 to latest, need guidance

So I upgraded, and I flattened the arrays. Here is the original code:

      for (; featureIndex < featureMax; featureIndex++) {
        rawVerts = [];
        feature = features[featureIndex];

        //***
        coords = feature.geometry.coordinates[0];
        for (i = 0, iMax = coords.length; i < iMax; i++) {
          rawVerts.push([coords[i][1], coords[i][0]]);
        }

        rawVerts.pop();
        currentColor = [Math.random(), Math.random(), Math.random()];

        triangles = earcut([rawVerts]);
        for (i = 0, iMax = triangles.length; i < iMax; i++) {
          triangle = triangles[i];
          pixel = L.glify.latLonToPixelXY(triangle[0], triangle[1]);
          verts.push(pixel.x, pixel.y, currentColor[0], currentColor[1], currentColor[2]
            /**random color -> **/ );
          //TODO: handle color
        }
      }

this is the output:

here is the upgraded, and broken code:

      for (; featureIndex < featureMax; featureIndex++) {
        rawVerts = [];
        feature = features[featureIndex];

        //***
        coords = feature.geometry.coordinates[0];
        for (i = 0, iMax = coords.length; i < iMax; i++) {
          rawVerts.push(coords[i][1], coords[i][0]);
        }

        rawVerts.pop();
        rawVerts.pop();

        currentColor = [Math.random(), Math.random(), Math.random()];

        triangles = earcut(rawVerts);

        for (i = 0, iMax = triangles.length; i < iMax; i += 2) {

          pixel = L.glify.latLonToPixelXY(triangles[i], triangles[i + 1]);
          verts.push(pixel.x, pixel.y, currentColor[0], currentColor[1], currentColor[2]
            /**random color -> **/ );
          //TODO: handle color
        }
      }

here is the output:

And, although my wife mentioned that it does look like a fabulous piece of art, it isn't my intended output. Where did I go wrong?

How to deal with holes correctly?

I have a low poly 2D camera mesh with three contours, and I'm having trouble triangulating it with earcut.

The way it should look, rendered with lineTo:

The way it looks, rendered with earcut triangles:

I'm wondering if you have any recommended modules/ideas to deal with this?

Here is my test case:

var earcut = require('earcut')
var canvas = document.createElement('canvas')
var context = canvas.getContext('2d')

var size = 800
canvas.width = canvas.height = size

render()

function render () {
  var scale = 0.25
  context.fillStyle = 'rgba(0,0,0,0.25)'
  context.strokeStyle = '#1d1d1d'
  context.lineWidth = 1 / scale

  context.clearRect(0, 0, size, size)
  context.save()

  context.scale(scale, scale)
  context.translate(150, 50)

  var points = [[[896,672],[1183,974],[881,1247],[608,945],[896,672]],[[1600,256],[1848,448],[1781,1589],[1,1579],[11,331],[427,224],[633,0],[1223,16],[1600,256]],[[896,1408],[1187,1300],[1340,1016],[1263,703],[896,512],[604,619],[451,903],[528,1216],[896,1408]]]

  // renderCanvas(points, '#1d1d1d')
  renderEarcut(points, '#1d1d1d')
}

function renderCanvas (poly, color) {
  context.fillStyle = context.strokeStyle = color
  context.beginPath()
  poly.forEach(function (path) {
    path.forEach(function (point, i) {
      if (i === 0) context.moveTo(point[0], point[1])
      else context.lineTo(point[0], point[1])
    })
  })
  context.fill()
}

function renderEarcut (poly, color) {
  var result = flattenData(poly)
  var verts = result.vertices
  var cells = earcut(verts, result.holes, result.dimensions)
  context.fillStyle = context.strokeStyle = color
  context.beginPath()
  for (var i = 0; i < cells.length; i+=3) {
    var a = cells[i], b = cells[i+1], c = cells[i+2]
    context.moveTo(verts[a * 2], verts[a * 2 + 1])
    context.lineTo(verts[b * 2], verts[b * 2 + 1])
    context.lineTo(verts[c * 2], verts[c * 2 + 1])
    context.lineTo(verts[a * 2], verts[a * 2 + 1])
  }
  context.fill()
  context.restore()
}

function flattenData (data) {
  var dim = data[0][0].length,
    result = {vertices: [], holes: [], dimensions: dim},
    holeIndex = 0

  for (var i = 0; i < data.length; i++) {
    for (var j = 0; j < data[i].length; j++) {
      for (var d = 0; d < dim; d++) result.vertices.push(data[i][j][d])
    }
    if (i > 0) {
      holeIndex += data[i - 1].length
      result.holes.push(holeIndex)
    }
  }

  return result
}

document.body.appendChild(canvas)

More efficient hole elimination

Held's hole elimination algorithm is very slow on some input (e.g. takes 70% on test/fixtures/water-huge.json because of 2 bad holes).

There's a much more efficient algorithm described by Eberly in http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

reflect polygon winding order in triangle winding order

Currently, earcut will always produce triangles in a clockwise winding order, regardless of the sense of the winding order of the original polygon. In 3d, this can reverse the direction of the normal vector which is used for example for lighting calculations of the generated triangles with respect to the original polygon. So for 3d applications it is often required to reflect the winding order of the original polygon in the winding order of the triangles.
I created a branch with a few, simple modifications to this effect here:
https://github.com/andreasplesch/earcut/tree/ccw-winding
I would gladly submit a pull request if there is a desire to accommodate such a feature. There is a performance cost for ccw polygons since the array of indices needs to be reversed. array.reverse(), however, is a native array function, and hopefully optimized. To avoid this cost, it would be necessary to take into account winding order during construction of the triangle list which is also possible.

Tessellation error with two holes (one touching outer vertex)

Here's a sample that results in an incorrect tessellation. Appears to be caused when there are two holes where one touches the outer ring and the other does not. Below is an example.

The first is the actual polygon (gray polygon, white holes), the second is it after running through Earcut, where the dark gray is overlap of triangles. The third is the same as the second except with each triangle having its edges highlighted.

Note it does not actually matter where the hole that is entirely enclosed is. The one that does touch the ring must be touching a vertex.

Vertices: [10,10, 25,10, 25,40, 10,40, 15,30, 20,35, 10,40, 15,15, 15,20, 20,15]
Hole Indicies: [4, 7]
Triangle Indices (result): [9,7,0, 0,7,8, 2,6,5, 4,6,0, 0,1,2, 5,4,0, 0,2,5]

[x, y, z] seems to be broken

There are also no tests for a [x, y, z] file!

Show error 'Uncaught ReferenceError: module is not defined earcut.js:3'

Currentry:

module.exports = earcut;

Better:

if( typeof module !== 'undefined' && typeof module.exports !== 'undefined'){
  module.exports = earcut;
}

Triagulation doesn't work when polygon is vertical

The triangulation comes back as an empty array if the vertices of the polygon are in a vertical plane, e.g.

polygon = [0,0,0,  1,0,1,  2,0,0]
earcut['default'](polygon, null, 3)

will return []

Another race condition

Originally from mapbox/earcut.hpp#11, reduced to the following test case:

[
    [[800,300],[500,800],[1200,800]],
    [[798,572],[792,606],[768,614],[758,586]],
    [[892,584],[894,594],[882,588]],
    [[842,596],[860,626],[848,622]],
]

cc @jfirebaugh

Flat array of points

This library looks awesome, my only issue with it is the format the data input is in. Up until now we have been using PolyK which has worked OK but is kind of slow and buggy.

I want to switch to this library but our data is a flat array of 2D coords ([x, y, x, y, x, y, ...]) and I would have to convert it to the format used here in order to make it work with this lib. The GC churn that would be caused by creating so many array objects is not desired. Is there anyway for this library to support a flat-array of coords syntax?

Broken triangulation

Hey - I'm sorry I don't know if this package is still maintained - I have a 3d quad with the following vertices:

[
2.456295967102051,
1.5326589345932007,
0.5580052137374878,
2.3840434551239014,
1.6075363159179688,
0.5736544132232666,
2.3840434551239014,
1.6075363159179688,
0.4867267608642578,
2.456295967102051,
1.5326589345932007,
0.471077561378479
]

and many more such quads - ex.

[
2.8560659885406494,
0.7904728651046753,
0.4427383840084076,
2.8363993167877197,
0.8773361444473267,
0.45491600036621094,
2.8363993167877197,
0.8773361444473267,
0.36798834800720215,
2.8560659885406494,
0.7904728651046753,
0.3558107316493988
]

And earcut is returning an empty array after executing earcut(vertices, null, 3)

Some quads (non co-planar quads) it is returning at least one triangle - and I can correct this by adding the missing vertice to a triangle sharing an edge and all is fine - but I cannot solve the case where earcut is returning nothing - i would have to do the triangulation manually.

I really need to get this to work - or can someone point me to a triangulation library which works the same as earcut? It doesn't have to be fast at all - just produce a triangle list of 3d coordinates from a list of vertices - exactly the way earcut does it - i tried plntri but the examples are poor and cannot figure out a way to call the function for 3d coordinates - libtess seems super complicated i have no idea how to get it working - the example webpage is terribly confusing and not documented at all.

any help would be MUCH MUCH appreciated..

Reduce sliver triangles on heavily simplified polygons

Simplification on polygons introduces minor self-intersections that can cause sliver triangles in the resulting triangulation. One thing that appears to improve results on data like this a lot is rejecting ears with points very close to them, not necessarily strictly inside the triangle. The trouble is coming up with a point-near-or-in-triangle test that is:

reliable,
with relative threshold so that it works on different coordinate scales
doesn't cause a significant perf hit.

crashes on empty input

earcut([]) produces:

/Users/john/Development/earcut/src/earcut.js:73
        if (!node.steiner && (equals(data, node.i, node.next.i) || orient(data
                 ^
TypeError: Cannot read property 'steiner' of undefined
    at filterPoints (/Users/john/Development/earcut/src/earcut.js:73:18)
    at earcut (/Users/john/Development/earcut/src/earcut.js:11:21)
    at Test.<anonymous> (/Users/john/Development/earcut/test/test.js:26:19)
    at Test.bound [as _cb] (/Users/john/Development/earcut/node_modules/tape/lib/test.js:63:32)
    at Test.run (/Users/john/Development/earcut/node_modules/tape/lib/test.js:76:10)
    at Test.bound [as run] (/Users/john/Development/earcut/node_modules/tape/lib/test.js:63:32)
    at Object.next [as _onImmediate] (/Users/john/Development/earcut/node_modules/tape/lib/results.js:70:15)
    at processImmediate [as _immediateCallback] (timers.js:354:15)

Expected it to return an empty array.

tesselation error in Stockholm archipelago

Tile coords: 12/2261/1208
Geo coords: 14/59.1396/18.7855

https://gist.github.com/jfirebaugh/4239c88c5418c3c7b303

error in findHoleBridge

I'm getting an error in the function findHoleBridge() on this line:
297: if (hy <= p.y && hy >= p.next.y) {

p is null.

I've been working on this for a few hours and I haven't made any headway. I'm using 3-dimensional polygons with several holes. What might cause this problem?

created indices are wrong

@mourner In the README.md it is stated about the creation of indices:

Alternatively, you can get triangulation results in the form of flat index and vertex arrays by passing true as a second argument to earcut (convenient for uploading results directly to WebGL as buffers):

    var triangles = earcut([[[10,0],[0,50],[60,60],[70,10]]], true);
    // {vertices: [0,50, 10,0, 70,10, 60,60], indices: [1,0,2, 3,2,1]}

But the current implementation creates indices which are a multiple of the passed-in dimension. For the given 2D case it produces something like this: [2,0,4, 6,4,2]. And passing in 3D coords like this [[[10,0,0],[0,50,0],[60,60,0],[70,10,0]]] it produces something like this: [3,0,6, 9,6,3].

Is this a bug in the description or a bug in the implementation? If you want to be able to upload the produced indices directly into a WebGL index buffer, the implementation needs to be changed to follow the description given above. Right now, I need to divide each generated index by 2 or 3 (depending on the passed-in dimensionality of the passed-in vertices).

Troublesome tiles

After rendering some vector-tiles with the new v2 specification, I found a few tiles with significant area deviations between their area and the earcut-calculated area.

Tile	Layer	Deviation	Validity failures
12,2244,1715	contour	253.64864864864865	interior_rings_outside
13,4817,4321	contour	241.72	interior_rings_outside
11,1556,777	contour	73	interior_rings_outside
12,3233,1464	contour	31.794736842105262	interior_rings_outside
12,1988,1777	contour	27.457142857142856	interior_rings_outside
14,5587,8896	contour	13.777889723392562	interior_rings_outside
11,1492,861	contour	10.678260869565218	self_intersections_method_t

These are just initial test results, but should be a good way to find patterns that could point to the source of area differences - either in invalid geometries or earcut edge cases.

cc/ @mourner @flippmoke

Hole connection bug

Test case:

[
[[1920,552],[1904,616],[1912,664],[1984,672],[2008,712],[1944,720],[1904,760],[1896,800],[1856,760],[1824,768],[1824,832],[1864,864],[1888,864],[1904,936],[1936,944],[1936,1064],[1936,1112],[1872,1136],[1856,1160],[1840,1144],[1792,1152],[1784,1112],[1752,1096],[1608,1096],[1600,1064],[1640,1040],[1664,992],[1640,968],[1568,1024],[1560,1056],[1480,1048],[1440,1072],[1440,1032],[1400,1032],[1400,1088],[1336,1136],[1320,1136],[1264,1072],[1232,1080],[1240,1104],[1200,1096],[1232,1048],[1272,1032],[1272,1000],[1232,1024],[1176,1024],[1176,1000],[1248,952],[1344,944],[1352,904],[1424,880],[1448,848],[1496,840],[1512,800],[1568,760],[1616,752],[1640,640],[1680,600],[1736,592],[1776,560],[1776,536],[1840,464],[1848,400],[1888,328],[1952,264],[2000,240],[2040,240],[2040,264],[1968,376],[1912,424],[1936,512],[1920,528],[1880,528],[1872,552],[1920,552]],
[[1608,800],[1576,848],[1520,840],[1512,872],[1456,904],[1440,952],[1528,936],[1552,912],[1584,912],[1608,880],[1664,864],[1680,816],[1656,776],[1608,800]],
[[1720,792],[1736,792],[1720,780],[1720,792]],
[[1656,728],[1670,752],[1672,728],[1656,728]],
[[1712,680],[1696,720],[1720,728],[1736,704],[1736,680],[1712,680]],
[[1968,712],[2000,712],[1968,688],[1968,712]]
]

It looks like this happens when a hole connects to outer polygon, then another hole connects to that hole through the same vertice, but since there are two vertices after eliminating the hole, one of the two connections leads to a broken outline. Should be fixable with some more checks in the findHoleBridge routine.

cc @flippmoke @hjanetzek @jakepruitt

preserve colinear segments

It looks like earcut filters out points along colinear segments of the polygon as these are not required to cover the polygon with triangles. However, I would like to have triangles with a vertex at these filtered out points since the same set of points is used for something else (the sides of a 3d extrusion of the polygon). which does not need the filtering.
Is there a way to avoid the filtering ? It looks the algorithm may rely on not having colinear segments ? Eg. this is done not just for performance reasons ?

Cure small self-intersections locally

When we reach a point where we can't find any valid ears to cut off (usually when there are self-intersections left), we proceed to polygon splitting routine which tries to find a valid diagonal. This step is very expensive — it's O(n^3) worst-case.

Polygons like OSM water contain a lot of small local self-intersections where edge (i-1,i) intersects edge (i+1,i+2). All these can be detected and cured much faster (O(n) in one pass) before we resort to diagonal search.

tesselation error over St. Petersburg FL

@ z6:

Should look closer to the z7 rendering:

Tile 6/17/26.

tesselation error over SF

@ z7:

Will reduce a test case.

Hashing reflex vertices

Currently the most expensive operation when triangulating is checking whether a potential ear contains any reflex vertices (which means it can't be cut off). It requires looping through all the points on each ear, which makes earcut perform poorly on shapes with thousands of points.

In FIST paper, Martin Held proposes using a simple grid for indexing the vertices, with conclusion that it improves performance dramatically for polygons with high number of points (in tests, it starts to pay off with >64).

In Earcut and JS, the overhead of hashing will probably be bigger, so it'll start to pay off much later, but it's still worth exploring. A very rough rbush-based implementation on earcut pays off only at >1-2k vertices, but with an optimized, earcut-specific grid, it'll probably be much faster.

Floating point precision can lead to incorrect triangulation

In rare cases the triangulation fails and appears to originate from the precision of the data sent to the earcut function.

Below is data for a simple ring with a hole which triangulates correctly:

[[143.129527283745121, 61.240160826593642, 12.157953862848911],
  [147.399527283763751, 74.780160826630892, 12.157953862848911],
  [154.049527283757931, 90.260160827077932, 12.157953862848911],
  [174.429527283762581, 81.710160826332872, 12.157953862848911],
  [168.03952728374861, 67.040160826407372, 12.157953862848911],
  [159.099527283746281, 53.590160826221112, 12.157953862848911]],

[[156.85952728375561, 67.430160827003422, 12.157953862848911],
  [157.489527283760251, 67.160160826519132, 12.157953862848911],
  [159.969527283741631, 68.350160826928912, 12.157953862848911],
  [161.339527283766071, 67.640160826966172, 12.157953862848911],
  [159.649527283763751, 63.310160826891662, 12.157953862848911],
  [155.759527283749781, 64.880160826258362, 12.157953862848911]]
]

Modifying the y-coordinate of the first ring point slightly (61.240160826593642 -> 61.240160826593640) produces incorrect triangles (tested with the triangulation test of earcut):

[[143.129527283745121, 61.240160826593640, 12.157953862848911],
  [147.399527283763751, 74.780160826630892, 12.157953862848911],
  [154.049527283757931, 90.260160827077932, 12.157953862848911],
  [174.429527283762581, 81.710160826332872, 12.157953862848911],
  [168.03952728374861, 67.040160826407372, 12.157953862848911],
  [159.099527283746281, 53.590160826221112, 12.157953862848911]],

[[156.85952728375561, 67.430160827003422, 12.157953862848911],
  [157.489527283760251, 67.160160826519132, 12.157953862848911],
  [159.969527283741631, 68.350160826928912, 12.157953862848911],
  [161.339527283766071, 67.640160826966172, 12.157953862848911],
  [159.649527283763751, 63.310160826891662, 12.157953862848911],
  [155.759527283749781, 64.880160826258362, 12.157953862848911]]
]

In the above case, the triangulation appears to deviate in the isEar function, around line 250, where in one case we have a value of t at -1.xxxe-13 and in the other at +1.xxxe-13 leading to different test results on (t >= 0).

Tested with version 1.4.0 of earcut.

Strange issue triangulating certain polygons

I'm comparing some of the different triangulation libraries on opentype fonts, and have run into a strange issue with earcut that I can't solve. See the image below:

As you can see, the upper hole for the percent-sign is not correct with earcut.

Less point filtering

Currently point filtering routine is run on the whole polygon after a split. We should do this only on affected nodes instead.

Race condition with tiny hole in huge polygon

[[
[-20037508.34,19971868.877628453,0],
[-20037508.34,-19971868.877628453,0],
[20037508.34,-19971868.877628453,0],
[20037508.34,19971868.877628453,0]
],
[
[537637.6007702783,5907542.234420554,0],
[539500.1483225027,5905165.501947839,0],
[538610.3146341922,5905217.430281373,0],
[538040.6306361248,5906132.0755739985,0],
[538068.958329954,5906571.138846622,0],
[537711.0379352621,5906645.06648362,0],
[537629.886026485,5907533.69114742,0]
]]

Ref: #16 (comment) @sctf4

Support for triangulating in other projection planes in 3D (x-z, y-z)

I'm looking to use earcut for some 3D triangulation. I've tried running through some of my existing data and have met mixed results.

This 3D polygon triangulates ok:

var earcut = require("earcut");

// x, y, height
var points = [458875, 5438350, 116, 458885, 5438350, 116, 458885, 5438355, 116, 458875, 5438355, 116, 458875, 5438350, 116];

// Returns [ 2, 3, 0, 0, 1, 2 ]
console.log(earcut(points, null, 3));

Yet this one returns nothing:

var earcut = require("earcut");

// x, y, height
var points = [458875, 5438355, 112, 458875, 5438350, 112, 458875, 5438350, 116, 458875, 5438355, 116, 458875, 5438355, 112];

// Returns []
console.log(earcut(points, null, 3));

From what I can see, the polygon that doesn't work is valid. The only difference being that it might be winding differently in 2D space (eg. by ignoring one of the axis), though that can't be controlled in 3D space.

Any ideas?

Question: What's the quickest way to find neighbours of a given triangle

Hi there,

I understand earcut produces the triangles in cw winding order (I saw the thread to get ccw). However, obviously given the original geojson, the winding order doesn't guarantee the position of neighbouring triangles within the array (or am I mistaken? I'm thinking about cases where some triangles have only one or two neighbours vs three...)

What would be the quickest way to find the neighbouring triangles of a given triangle in the results array? short of obviously linearly running through the entire results...

Investigate storing vertex coords in Node for performance

Ref: mapbox/earcut.hpp#10. We should try this and benchmark. cc @jfirebaugh

Conservative run / early bail

I know that it's not earcut's goal to be perfect, but just to be acceptable in practice. What I'm wondering is, if it's possible to run earcut as a fast optimistic pass, and fallback to something slower but more robust for problematic geometry. That of course requires earcut to be aware when it might be wrong, or maybe even more conservative just that the input is possibly problematic. Is there a way to sort of use earcut "conservatively", and bail out with an error if there is not a guarantee for the answer to be correct?

I know in a way it's probably asking a lot, but of course it would be great to have the performance improvement for earcut in the 95% of cases where it can handle it, and otherwise fall back to something like tess2.

Maybe worded in a different way, is it sort of clearly known when and where earcut can go wrong? Is it realistic to possibly categorize (hopefully efficiently) inputs that are / are not simple in the eyes of earcut? Even if if there was some performance overhead but half of the time earcut could be used, it would still be a win.

PS: I saw deviation, but I was thinking of something more along the lines of a quick pre-pass or an early bail out, not a post analysis. And also somehow my instinct tells me that just comparing the signed area might not always work. Couldn't it be possible that there are just multiple errors that cancel out in regards to area?

Thanks

Investigate algorithm modifications that produce better quality triangulation

Currently ear slicing is done sequentially, which is very fast but produces bad triangulation quality. We could try some modifications of the algorithm that produce much better triangles:

randomized ear selection
sorted ear selection (using a priority queue and picking the best ear each time)

Then we'd look if we can make this optional so you can choose between max quality triangulation and max speed triangulation.

3d polygon in XZ plane

Are three dimensions fully supported or only if the polygon can be mapped to the XY plane, effectively by just ignoring the Z coordinate ?

This square in the XZ plane does not return any triangles in my testing:

earcut([0,0,0, 10,0,0, 10,0,10, 0,0,10, 0,0,0], null, 3);

Errors when a hole is touching an outer ring

Here's a bunch of OSM samples from @lbud with an Earcut error where the cause seems to be the same, a hole touching an outer ring.

Bad triangulation in shape with duplicate vertices

I have data sets that can contain duplicate vertices.

In this case the holes aren't handled correctly.

When I remove the duplicate vertices the holes are handled correctly.

It is possible to solve this by filtering out the duplicate vertices, but in some cases it would be useful to have the triangulation match the data set. (issue might be related to #52)

I've created an ESbin with example code

Multipolygon speed-up

While earcut is great for single polygon calculations, for multipolygon cases it could provide advanced API for more efficient working with Arrays:

provide input params to work on data range for input data so earcut can work on single big user-pre-allocated array taking its slices (dStar, dEnd)
provide input params to work on user pre-allocated triangles array as well, saving the results on specified offset and with correct index pointing to the data array being worked from dStart and dEnd.
return new offset from writing new indices into the triangles.

all above is enabling to efficiently earcut hundreds of thousands polygons and passing the resulting arrays directly into the WebGL buffers.

I did that as experiment and saved hundreds of ms in total (for all polygons processing). Branch of this approach available here : https://github.com/Sumbera/earcut/tree/multipolygon

Bower Package

Awesome library. It would be fantastic to make this available as a bower package, too. Any plans for this?

Eracut gives an empty result

Coords: [10, 10, 610, 10, 610, 610, 10, 610]
HoleIndices: [50, 50, 150, 50, 150, 150, 50, 150]
numDimensions: 2

Eracut is returning an empty result for the above data set and both are rectangle vertices.

How to deal with multi-holes correctly?

const outer = [0,0, 100,0, 100,100, 0,100];
const holes = [60,0, 80,0, 80,50, 60,50, 20,0, 40,0, 40,50, 20,50];
const conc = outer.concat(inner);
earcut(conc, [4])

printout => [3, 0, 11, 2, 3, 11, 2, 11, 10, 10, 9, 7, 4, 11, 0, 2, 10, 7, 2, 7, 6, 1, 2, 6, 1, 6, 5]

I am using [email protected]. could't find out why this one not working, all my outer and holes are anticlockwise.

Less than expected number of triangles?

Hi,

First, thanks for creating this amazing library and open sourcing it! I've enjoyed using it but I'm having trouble understanding the following results:

 earcut([-180, -90, -180, 0, -180, 90, -90, -90, -90, 0, -90, 90, 0, -90, 0, 0, 0, 90, 90, -90, 90, 0, 90, 90, 180, -90, 180, 0, 180, 90]);

The result I get back is 4 triangles but shouldn't there be 8 triangles since there are no holes?

[3, 2, 0, 12, 11, 9, 9, 8, 6, 6, 5, 3]

Taking a step back, I'm working on partitioning the globe with 15 points (lon, lat) to visualize on a map but the problem is that when I render these triangles, I'm left with 4 triangle holes when I'm not expecting any?

Indexed vertices API

Instead of outputting triangles as 3 vertices each, we could output unique vertices + list of indexes for triangles instead, like e.g. https://github.com/claus/libtess2.js/. This can save a lot of memory and vertex processing time when uploading vertices data to GL.

Type annotations

In preparation of porting this code to C++, it'd be cool to add type annotations to all variables, and especially parameters.

I haven't used it, but Flow might be a candidate syntax. Alternatively, TypeScript might be another one.

Steiner points support

It should be relatively easy to add. They'd be handled the same way as holes, with the only problem being that currently it would filter out the connection as collinear.

Vertex missing from triangle output

I've found that some of the vertices in my polygons are being ignored when run through earcut, resulting in less triangles than would be expected.

For example, take the following points:

[68238.985, 268.575, 68248.747, 268.512, 68248.747, 259.248, 68238.985, 259.248, 68238.338, 259.248, 68238.338, 268.58, 68238.985, 268.575]

There are 6 unique vertices (7 minus the duplicated start/end vertex), which when run through earcut produce the following 3 triangles:

[5, 4, 2, 2, 1, 6, 6, 5, 2]

Which looks like this (notice how the vertex second from left at the bottom is part of no face):

When the same polygon is run through poly2tri the results are as per expected; 4 triangles using all vertices:

Is this expected with earcut, or is something wrong? I notice in the readme that it's suggested that earcut can sacrifice triangulation quality so I want to be sure that's the cause before moving to another triangulation approach for now.

client-side/Node environment

When using earcut on client-side I get the error: "module is undefined"

I suggest changing the first line from:

module.exports = earcut;

to:

if ( 'undefined' !== typeof exports && 'undefined' !== typeof module ) {
    module.exports = earcut;
}

that way it should work normally on Node and on client-side.

Comparison between earcut and libtess.

Not sure this fits here, but I wanted to say this.

I tried to use this library to cut my maps' walls into convex pieces for box2d. I thought the fact that all my point were on a grid would make this library perform correctly. It ended up being wrong on some maps:

earcut: http://i.imgur.com/F4aC3S2.png
libtess: http://i.imgur.com/PZ41Gkf.png

A few test cases with bad triangulations

Processed ~5 million polygons from a Mapbox Terrain subset and found just 79 cases with deviations that are not fixed by filtering out collinear points (fix-alt branch): https://gist.github.com/mourner/738f8ff6c7dae5a1144e (for reference, it's 159 on master without filtering).

edit: it's down to 4 failing cases with the latest patches.

This is a great set of cases to investigate and fix remaining Earcut issues. A lot of them seem to be about rings sharing a point (edges touching by an endpoint).

I'll look into them in the next few days but any help is appreciated too. cc @hjanetzek @mrgreywater

The biggest failing sample looks like this (it's a hole on the left):

Expose earcutArea function

For tile providers, it helps to do the same comparison between geometry area and earcut area that is done in earcut's tests, which helps ensure that the tiles are 100% compatible with earcut's algorithm. Would it be possible to expose this calculation as a helper method, like earcutArea(geom) that returns the sum of the areas of the earcut triangles? Having it exposed would reduce the likelihood of area miscalculation in tile provider tests, and would prevent the tests from getting out of sync.

cc/ @mapsam @mourner @springmeyer

Yet another race condition

From mapbox/earcut.hpp#14. Working on a reduced test case.