
Earcut
An F# port of Mapbox Earcut, the fast and small polygon triangulation library, for .NET and, via Fable, for JavaScript.
About Earcut
Earcut triangulates polygons with holes. It uses a modified ear slicing algorithm,
sped up with a z-order curve hash.
It trades triangulation quality for speed: it handles most practical data without crashing,
but does not guarantee a correct result on invalid input, such as self-intersecting rings or holes outside the outer ring.
Its output is not conforming either: a vertex can land in the middle of another triangle's edge.
See the README of the original for the algorithm, its robustness and a demo.
Status
A port of Mapbox Earcut v3.2.4, including all later upstream commits up to 934e54d from Oct 2026.
No dependencies, runs on .NET Standard 2.0 and JS via Fable.
Like in JS all code is in the single file Earcut.fs.
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.
Performance
When compiled back to JS with Fable, the F# port has about the same performance as the original JS version.
On .NET 11 the F# port is about 1.1 times faster than the original JS version for earcut and about 1.6 times faster for refine.
See the benchmark README for results and how to run the benchmarks.
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
For benchmarks, see the benchmark README.
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:

Earcut