Splits a flat face, with any holes, into triangles.
How the precision is kept
Ear clipping after the algorithm of mapbox/earcut, as the file's header states. Every decision is the sign of a cross product, or a comparison of such products, in 64-bit numbers with no tolerance; these are not exact predicates. The output is a list of vertex indexes: no coordinate is computed or changed, so the triangles use the face's own points.
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 face as triples of vertex indexes.
Returns indexes into the input points only. A ring with fewer than three distinct points gives no triangles.
m3d/earcut.js
lines 23 to 32
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;
}
Orientation of three points
64-bit
Twice the signed area of a triangle, whose sign says which way three points turn.
(q_y − p_y)(r_x − q_x) − (q_x − p_x)(r_y − q_y)
Two products of coordinate differences are subtracted. For nearly collinear points the products are nearly equal and the sign can be decided by rounding; the code compares the result with exact zero.
Whether a ring of points runs clockwise or counterclockwise.
Σ (x_j − x_i)(y_i + y_j)
Only the sign of the sum is used. The terms contain sums of y values, so for a ring far from the origin the terms are large and nearly cancel, and the sum carries fewer good digits than the coordinates.
m3d/earcut.js
lines 271 to 278
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;
}
Is a corner an ear
64-bit
Whether the triangle at a corner is convex and holds no other point of the polygon.
The corner must turn the right way (area below zero); then every other point inside the triangle's bounding box is tested with the point-in-triangle comparisons. No tolerance.
m3d/earcut.js
lines 83 to 95
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 a triangle
64-bit
Whether a point lies in or on a triangle.
three comparisons (c − p) × (a − p) ≥ 0, each written as product ≥ product
Each test compares two products of differences from the point, without subtracting them first. A point on an edge counts as inside.
Drops points that repeat their neighbor or lie exactly on the line between their neighbors.
A point is dropped only when its coordinates are identical to the next point's or the cross product is exactly zero. A point that is off the line by one rounding step is kept and gives a sliver triangle.
m3d/earcut.js
lines 45 to 59
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;
}
Bridge from a hole to the outer ring
64-bit
The outer-ring point a hole is connected to, found by a ray to the left from the hole's leftmost point.
The division for the crossing is guarded: horizontal edges are skipped. The tangent's divisor is guarded by requiring the candidate's x to differ from the hole point's x. Ties are compared with exact equality.
m3d/earcut.js
lines 154 to 187
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 edges cross
64-bit
Whether two segments intersect, used to keep a diagonal from crossing the polygon.
Signs of four orientation values, with a collinear case handled by a bounding-box test. The signs come from 64-bit cross products with no tolerance.
Whether the middle of a candidate diagonal lies inside the polygon.
crossing count of a ray from ((a_x + b_x) ÷ 2, (a_y + b_y) ÷ 2)
An even-odd crossing count. The division by the edge's height is guarded by skipping horizontal edges.
m3d/earcut.js
lines 243 to 251
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
Holes are bridged into the outer ring, then ears are clipped; when clipping stalls, local self-intersections are cured and the polygon is split along a valid diagonal. The z-order hash of the original is left out.
Number types
64-bit numbers; indexes are whole numbers.
Tolerances
None. Points are equal only when both coordinates are identical; three points are collinear only when the cross product is exactly zero.
Limits
For nearly collinear points or coordinates far from the origin, rounding decides the sign of a cross product, and with it which triangles are made.
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.