Splits a flat polygon with holes into triangles, for caps of extruded sections and faces with holes.
How the precision is kept
The routine returns indexes into the input points and creates no coordinates, so vertex values pass through unchanged. Its yes-or-no decisions (which way a ring winds, whether a corner is an ear, whether a point lies in a triangle, whether two edges cross) are signs of 64-bit cross products compared with zero, with no tolerance and no exact arithmetic.
Calculations under this policy
9 calculations in 1 source file. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
The triangles of a polygon, as indexes into its point list.
Only indexes are returned; no coordinate is computed or changed. The triangles depend on the sign tests in the functions below.
usd/earcut.js
lines 24 to 33
CadCraft 0.8.2
export function earcut(data, holeIndices = [], dim = 2) {
const hasHoles = holeIndices.length;
const outerLen = hasHoles ? holeIndices[0] * dim : data.length;
let outerNode = linkedList(data, 0, outerLen, dim, true);
const triangles = [];
if (!outerNode || outerNode.next === outerNode.prev) return triangles;
if (hasHoles) outerNode = eliminateHoles(data, holeIndices, outerNode, dim);
earcutLinked(outerNode, triangles, dim, 0);
return triangles;
}
Winding of a ring
64-bit
Whether a ring runs clockwise or counterclockwise.
sum = Σ (xⱼ − xᵢ) × (yᵢ + yⱼ)
A 64-bit sum over the ring's edges in order; only its sign is used. Each term multiplies by yᵢ + yⱼ, so for a ring far from the origin the terms are large and nearly cancel.
usd/earcut.js
lines 272 to 279
CadCraft 0.8.2
function signedArea(data, start, end, dim) {
let sum = 0;
for (let i = start, j = end - dim; i < end; i += dim) {
sum += (data[j] - data[i]) * (data[i + 1] + data[j + 1]);
j = i;
}
return sum;
}
Orientation of three points
64-bit
On which side of the line through two points a third point lies.
Two products of coordinate differences subtracted in 64-bit. The callers use only the sign or an exact test against zero; for three nearly collinear points the two products are nearly equal and the sign can be wrong.
Drops points that repeat their neighbor or lie on the line between their neighbors.
A point is removed when it equals the next point exactly or when the orientation value is exactly 0. There is no tolerance, so a point that is off the line by rounding only is kept.
usd/earcut.js
lines 46 to 60
CadCraft 0.8.2
function filterPoints(start, end) {
if (!start) return start;
if (!end) end = start;
let p = start, again;
do {
again = false;
if (!p.steiner && (equals(p, p.next) || area(p.prev, p, p.next) === 0)) {
removeNode(p);
p = end = p.prev;
if (p === p.next) break;
again = true;
} else p = p.next;
} while (again || p !== end);
return end;
}
Ear test
64-bit
Whether a corner can be cut off as a triangle: it is convex and no other point of the ring lies inside it.
A corner with orientation value 0 or above is not an ear. Other points are tested only inside the triangle's bounding box, with exact comparisons.
usd/earcut.js
lines 84 to 96
CadCraft 0.8.2
function isEar(ear) {
const a = ear.prev, b = ear, c = ear.next;
if (area(a, b, c) >= 0) return false;
const ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y;
const x0 = Math.min(ax, bx, cx), y0 = Math.min(ay, by, cy), x1 = Math.max(ax, bx, cx), y1 = Math.max(ay, by, cy);
let p = c.next;
while (p !== a) {
if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 &&
pointInTriangleExceptFirst(ax, ay, bx, by, cx, cy, p.x, p.y) && area(p.prev, p, p.next) >= 0) return false;
p = p.next;
}
return true;
}
Point in triangle
64-bit
Whether a point lies inside or on a triangle.
three cross products of (corner − point) pairs, each ≥ 0
Three comparisons of 64-bit products of differences from the tested point; a point on an edge counts as inside.
The intersection of a horizontal ray with each edge is one 64-bit expression; the division is guarded by p′.y ≠ p.y and the tangent by h.x ≠ p.x. Ties are settled by exact equality.
usd/earcut.js
lines 155 to 188
CadCraft 0.8.2
function findHoleBridge(hole, outerNode) {
let p = outerNode;
const hx = hole.x, hy = hole.y;
let qx = -Infinity, m;
if (equals(hole, p)) return p;
do {
if (equals(hole, p.next)) return p.next;
if (hy <= p.y && hy >= p.next.y && p.next.y !== p.y) {
const x = p.x + (hy - p.y) * (p.next.x - p.x) / (p.next.y - p.y);
if (x <= hx && x > qx) {
qx = x;
m = p.x < p.next.x ? p : p.next;
if (x === hx) return m;
}
}
p = p.next;
} while (p !== outerNode);
if (!m) return null;
const stop = m, mx = m.x, my = m.y;
let tanMin = Infinity;
p = m;
do {
if (hx >= p.x && p.x >= mx && hx !== p.x &&
pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p.x, p.y)) {
const tan = Math.abs(hy - p.y) / (hx - p.x);
if (locallyInside(p, hole) && (tan < tanMin || (tan === tanMin && (p.x > m.x || (p.x === m.x && sectorContainsSector(m, p)))))) {
m = p;
tanMin = tan;
}
}
p = p.next;
} while (p !== stop);
return m;
}
Do two segments cross
64-bit
Whether two edges intersect, including touching and collinear overlap.
Four orientation signs are compared; a sign of exactly 0 leads to a bounding-box test on the segment. The signs come from the unguarded 64-bit cross product.
Whether a diagonal between two corners runs through the inside of the polygon.
midpoint = ((a.x + b.x) ÷ 2, (a.y + b.y) ÷ 2); even-odd count of edges crossed by a ray
The midpoint is one addition and one halving per coordinate in 64-bit. Each edge crossing is one 64-bit expression whose division is guarded by p′.y ≠ p.y.
usd/earcut.js
lines 244 to 252
CadCraft 0.8.2
function middleInside(a, b) {
let p = a, inside = false;
const px = (a.x + b.x) / 2, py = (a.y + b.y) / 2;
do {
if (((p.y > py) !== (p.next.y > py)) && p.next.y !== p.y && (px < (p.next.x - p.x) * (py - p.y) / (p.next.y - p.y) + p.x)) inside = !inside;
p = p.next;
} while (p !== a);
return inside;
}
In detail
Method
Ear clipping after the algorithm of mapbox/earcut, as the file header says: holes are bridged into the outer ring, ears are clipped, and when clipping stalls, local self-intersections are cured and the polygon is split along a valid diagonal. The z-order hash is left out.
Number types
64-bit numbers for coordinates; integer vertex indexes.
Tolerances
None. Collinear and duplicate points are found by exact comparison with zero.
Limits
For nearly collinear points the rounding of the cross product can give the wrong sign, which changes which triangles are produced. The input must already be 2D.
Approach: 64-bit, direct
Every value is a 64-bit number from input to result. Formulas are closed form or a direct solve, and every comparison uses a stated tolerance.