Earcut 3.2.43
dotnet add package Earcut --version 3.2.43
NuGet\Install-Package Earcut -Version 3.2.43
<PackageReference Include="Earcut" Version="3.2.43" />
<PackageVersion Include="Earcut" Version="3.2.43" />
<PackageReference Include="Earcut" />
paket add Earcut --version 3.2.43
#r "nuget: Earcut, 3.2.43"
#:package Earcut@3.2.43
#addin nuget:?package=Earcut&version=3.2.43
#tool nuget:?package=Earcut&version=3.2.43

Earcut
The fastest and smallest polygon triangulation library.
A port of Mapbox's Earcut algorithm to F#.
https://github.com/mapbox/earcut
Status
Stable for .NET Standard 2.0 and JS via Fable.
A port of Mapbox Earcut v3.2.4, including all later upstream commits up to 934e54d.
All tests of the original JS version pass,
including the MVT regression suite over 119,680 real-world polygons.
The port produces element-for-element identical output to the reference JS implementation.
The only exception is degenerate input on .NET: if a single-point hole (Steiner point) sits exactly on the leftmost point
of at least two other holes, the order in which these holes get merged is not defined in the original either
(it depends on the sort algorithm of the JS engine), so the triangles can differ.
All relevant code is in Earcut.fs.
It contains the ported code without any major changes to the original logic.
It has no dependencies.
Performance
The F# port has about the same performance as the original JS version when compiled back to JS with Fable.
This holds for Release builds, the default of dotnet fable. In Debug builds (the default of dotnet fable watch)
array access is bounds-checked, which makes earcut about 1.5 times and refine about 4 times slower.
On .NET it is somewhat faster than the original running on Node.js.
Earcut is heavily optimized for its primary workload - triangulating polygons from
Mapbox Vector Tiles.
You can run the MVT benchmark (119,680 real-world polygons, 1.9M vertices) yourself with
node Test/bench/bench-tiles.js (after dotnet fable), and the refinement benchmark with
node Test/bench/bench-refine.js.
The algorithm
The library implements a modified ear slicing algorithm,
optimized by z-order curve and spatial 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 the original mapbox Earcut project is to create a 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,
with an option to refine the result to Delaunay quality at a small cost.
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.
Robustness
Earcut does not guarantee a correct triangulation on arbitrary input - it trades quality
for speed, aiming to always produce an acceptable result on practical data without crashing or
emitting garbage. The input is assumed to be a valid polygon: rings that don't self-cross or
overlap, holes that stay inside the outer ring, and no duplicate or zero-length edges. On input
that breaks these assumptions, the result can be noticeably wrong - overlapping triangles, gaps,
or triangles outside the polygon. If correctness matters, clean your input first (see also the
validate function below); for a guaranteed-correct triangulation even on bad data, see
libtess.js (slower and larger).
The output is also not conforming - a vertex may land in the middle of another triangle's edge (a T-junction). This is harmless for rendering but can break navmesh or FEM use; if you need a conforming mesh, remove T-junctions in a post-process.
Usage
let triangles = Earcut.earcut([| 10.;0.; 0.;50.; 60.;60.; 70.;10.|], [||], 2) // returns [1;0;3; 1;3;2]
Parameters:
vertices- A flat array of vertex coordinates like[x0, y0, x1, y1, x2, y2, ...].holeIndices- An array of hole starting indices. These indices refer to the point array, not the flattened vertices array.
If you have an index into the flattened vertices array, divide it bydimensionsto get the correct hole index.
(e.g.[|4|]means the hole starts at point 4, i.e. atvertices[4 * dimensions]).
Usenullor an empty array if there are no holes.dimensions- The number of coordinates per vertex in the vertices array:2if the vertices array is made of x and y coordinates only.3if it is made of x, y and z coordinates.
Only the first two are used for triangulation (xandy), and the rest are ignored.
Returns:
A list of integers. They are indices into the point array (not the flattened vertices array).
Every 3 integers represent the corner vertices of a triangle.
To look up coordinates in the flattened vertices array, multiply the index by dimensions:
x = vertices[i * dimensions]
y = vertices[i * dimensions + 1]
Output triangles always have a consistent winding order regardless of the input polygon's winding:
counter-clockwise in a y-up coordinate system (clockwise in y-down/screen space).
If you need the opposite orientation (e.g. for back-face culling or normals in 3D), reverse the result.
Convenience F# API: earcutTrianglesFromMembersxy and earcutTrianglesFromMembersXY
If your points are objects with x/y (or X/Y) properties, you can use the convenience functions
earcutTrianglesFromMembersxy and earcutTrianglesFromMembersXY instead of manually flattening coordinates.
They accept an IList of points (a ResizeArray, an array, ...) and an optional list of holes (also as ILists of points),
and return a flat float[] of triangle vertex coordinates [x0, y0, x1, y1, x2, y2, ...].
Every six consecutive values represent a triangle.
These functions use F# statically resolved type parameters, so any object with the matching members will work.
For example given these Polylines from Euclid:
let outerPoly: Polyline2D = ...
let hole1: Polyline2D = ...
let hole2: Polyline2D = ...
// For points with uppercase .X and .Y members:
let triangles = outerPoly.Points |> Earcut.earcutTrianglesFromMembersXY null
// With holes:
let holes = [|hole1.Points; hole2.Points|]
let triangles = outerPoly.Points |> Earcut.earcutTrianglesFromMembersXY holes
If your coordinates are already flat lists of numbers [x0, y0, x1, y1, ...], use Earcut.earcutTriangles in the same way.
It takes an IList<float> (a ResizeArray<float> or float[]) per ring and also returns the flat float[] of triangle coordinates.
All three functions skip empty holes.
Examples
Simple polygon (no holes)
// A quadrilateral with 4 vertices, 2D coordinates
let vertices = [| 10.; 0.; 0.; 50.; 60.; 60.; 70.; 10. |]
let triangles = Earcut.earcut(vertices, [||], 2)
// returns [1; 0; 3; 1; 3; 2]
// Triangle 1: points 1, 0, 3
// Triangle 2: points 1, 3, 2
// Retrieve triangle vertex coordinates:
for t in 0 .. 3 .. triangles.Count - 1 do
let i0 = triangles.[t]
let i1 = triangles.[t + 1]
let i2 = triangles.[t + 2]
printfn "Triangle: (%g, %g) (%g, %g) (%g, %g)"
vertices.[i0 * 2] vertices.[i0 * 2 + 1]
vertices.[i1 * 2] vertices.[i1 * 2 + 1]
vertices.[i2 * 2] vertices.[i2 * 2 + 1]
Polygon with a hole
// Outer square: points 0-3, hole square: points 4-7
let vertices = [|
0.;0.; 100.;0.; 100.;100.; 0.;100. // outer ring
20.;20.; 80.;20.; 80.;80.; 20.;80. // hole
|]
let triangles = Earcut.earcut(vertices, [|4|], 2) // hole starts at point index 4
// returns [0;4;7; 5;4;0; 5;0;1; 5;1;2; 3;0;7; 3;7;6; 6;5;2; 6;2;3]
3D coordinates
// 4 vertices with x, y, z (z is ignored for triangulation)
let vertices = [| 10.;0.;1.; 0.;50.;2.; 60.;60.;3.; 70.;10.;4. |]
let triangles = Earcut.earcut(vertices, null, 3)
// returns [1; 0; 3; 1; 3; 2]
// Retrieve coordinates using dimensions = 3:
let i = triangles.[0] // e.g. 1
let x = vertices.[i * 3] // 0.
let y = vertices.[i * 3 + 1] // 50.
let z = vertices.[i * 3 + 2] // 2.
Multiple holes
// Outer polygon with two holes
// Outer: points 0-5, Hole1: points 6-9, Hole2: points 10-13
let triangles = Earcut.earcut(vertices, [|6; 10|], 2)
// holeIndices = [|6; 10|] means:
// hole 1 starts at point 6 -> vertices.[6 * 2]
// hole 2 starts at point 10 -> vertices.[10 * 2]
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:
let data = Earcut.flatten(geojson.geometry.coordinates)
let triangles = Earcut.earcut(data.vertices, data.holes, data.dimensions)
Delaunay refinement with refine
If triangle quality matters, you can run an optional refinement pass after triangulation:
let triangles = Earcut.earcut(vertices, holes, dimensions)
Earcut.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.
Verification of triangulation correctness
After getting a triangulation, you can verify its correctness with Earcut.deviation:
let 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.
Input validation with validate
The original JS library does not validate its input. This F# port adds an optional validate function
that raises a descriptive System.ArgumentException if the input is malformed
(NaN/Infinity values, wrong array length, bad hole ordering, holes larger than the outer ring, etc.):
Earcut.validate(vertices, holes, dimensions)
earcut itself only rejects dimensions below 2. On .NET other malformed input, like a hole index past the end,
ends in an IndexOutOfRangeException or NullReferenceException. In Fable Release builds array access is unchecked,
as in the original, so call validate first if you don't trust the input.
Thread safety
On .NET, calls to earcut, its convenience wrappers, and refine are thread-safe:
each thread caches its own internal Workspace containing the reusable scratch buffers.
A workspace must never be shared between threads. Buffers grow on demand and are reused
by subsequent calls on the same thread.
Input collections must not be modified while a call is using them. Since refine mutates
its triangle list in place, concurrent calls must use separate triangle lists.
Fable/JavaScript uses one workspace per JS context, matching its synchronous execution model.
Build for .NET Standard 2.0
dotnet build
Build to JS with Fable
Install the pinned Fable version from .config/dotnet-tools.json with:
dotnet tool restore
then build to JS with:
dotnet fable
Run Tests
There are two test suites with the same tests.
For Fable/JS, build to JS with dotnet fable and run node Test/test.js
For .NET, run dotnet fsi Test/test.fsx
Run Benchmarks
For .NET, build the Release library and benchmark large polygons:
dotnet build -c Release
dotnet fsi Test/bench/bench-large.fsx
For Fable/JS, build with dotnet fable and run:
node Test/bench/bench-large.js
node Test/bench/bench-tiles.js
node Test/bench/bench-refine.js
The large-polygon benchmarks cover regular 10k/100k polygons, a concave star, a random-radius ring, and a rectangle with collinear boundary vertices. They report the median and range of five measured calls after one warmup. Run before/after versions in separate processes.
License
MIT
The original Mapbox Earcut that this library is ported from is ISC licensed,
see the third-party notice in LICENSE.md.
Images of test cases
bad-diagonals:

bad-hole:

boxy:

building:

collinear-diagonal:

dude:

eberly-3:

eberly-6:

filtered-bridge-jhl:

hilbert:

hole-touching-outer:

hourglass:

issue111:

issue119:

issue131:

issue142:

issue149:

issue16:

issue17:

issue186:

issue29:

issue34:

issue35:

issue45:

issue52:

outside-ring:

rain:

self-touching:

shared-points:

simplified-us-border:

steiner:

touching-holes:

touching-holes2:

touching-holes3:

touching-holes4:

touching-holes5:

touching-holes6:

touching2:

touching3:

touching4:

water-huge2:

water:

water2:

water3:

water3b:

water4:

| Product | Versions Compatible and additional computed target framework versions. |
|---|---|
| .NET | net5.0 was computed. net5.0-windows was computed. net6.0 was computed. net6.0-android was computed. net6.0-ios was computed. net6.0-maccatalyst was computed. net6.0-macos was computed. net6.0-tvos was computed. net6.0-windows was computed. net7.0 was computed. net7.0-android was computed. net7.0-ios was computed. net7.0-maccatalyst was computed. net7.0-macos was computed. net7.0-tvos was computed. net7.0-windows was computed. net8.0 was computed. net8.0-android was computed. net8.0-browser was computed. net8.0-ios was computed. net8.0-maccatalyst was computed. net8.0-macos was computed. net8.0-tvos was computed. net8.0-windows was computed. net9.0 was computed. net9.0-android was computed. net9.0-browser was computed. net9.0-ios was computed. net9.0-maccatalyst was computed. net9.0-macos was computed. net9.0-tvos was computed. net9.0-windows was computed. net10.0 was computed. net10.0-android was computed. net10.0-browser was computed. net10.0-ios was computed. net10.0-maccatalyst was computed. net10.0-macos was computed. net10.0-tvos was computed. net10.0-windows was computed. |
| .NET Core | netcoreapp2.0 was computed. netcoreapp2.1 was computed. netcoreapp2.2 was computed. netcoreapp3.0 was computed. netcoreapp3.1 was computed. |
| .NET Standard | netstandard2.0 is compatible. netstandard2.1 was computed. |
| .NET Framework | net461 was computed. net462 was computed. net463 was computed. net47 was computed. net471 was computed. net472 was computed. net48 was computed. net481 was computed. |
| MonoAndroid | monoandroid was computed. |
| MonoMac | monomac was computed. |
| MonoTouch | monotouch was computed. |
| Tizen | tizen40 was computed. tizen60 was computed. |
| Xamarin.iOS | xamarinios was computed. |
| Xamarin.Mac | xamarinmac was computed. |
| Xamarin.TVOS | xamarintvos was computed. |
| Xamarin.WatchOS | xamarinwatchos was computed. |
-
.NETStandard 2.0
- FSharp.Core (>= 6.0.7)
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.
### Changed
- The NuGet release workflow publishes with [trusted publishing](https://learn.microsoft.com/en-us/nuget/nuget-org/trusted-publishing) (GitHub OIDC) instead of a long-lived API key secret. The 3.2.42 push failed because that key had expired, so 3.2.43 has the same library code.
### Fixed
- `ResizeArr.pop` emits the unchecked `pop()` only in Fable Release builds, like the other `Arr` and `ResizeArr` helpers. Debug builds keep the bounds check.