Resources Numerical accuracy Calculation policy
Splits a flat polygon with holes into triangles for IFC shapes.
All decisions are 64-bit cross products compared with zero, with no tolerance. A ring that cannot be finished is closed with a fan so nothing is lost.
5 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.
Tests tools/ifc-test/test.mjs
The signed area that decides if a ring runs counter-clockwise.
A = ½ Σ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ)
Shoelace sum of a×b cross terms in 64-bit, divided by 2; only its sign is used.
const area = (r) => { let s = 0; for (let i = r.start, e = r.start + r.n; i < e; i++) { const a = pts[i], b = pts[i + 1 < e ? i + 1 : r.start]; s += a[0] * b[1] - b[0] * a[1]; } return s / 2; };Which side of a line a point lies on and whether a point is inside a triangle.
cross = (bx−ax)(cy−ay) − (by−ay)(cx−ax)
One 64-bit cross product and three comparisons with 0 (>= 0 counts the boundary as inside). No tolerance.
const cross = (a, b, c) => (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
function inTri(a, b, c, p) {
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}The vertex of the outer ring a hole is joined to.
Finds the nearest outer edge crossed by the ray from the hole vertex to +x with x = a.x + (m.y − a.y)(b.x − a.x) ÷ (b.y − a.y) (horizontal edges are handled separately), then the visible vertex with the smallest tangent; tan divides by (p.x − m.x) or 1e-300 if that is 0.
/** Join a hole (rightmost vertex m) to the outer ring; → the outer ring's head. */
function bridgeHole(m, outer) {
// the nearest edge crossing the ray from m to +x
let p = outer, best = null, qx = Infinity;
do {
const a = p, b = p.next;
if ((a.y <= m.y && b.y >= m.y) || (b.y <= m.y && a.y >= m.y)) {
if (a.y !== b.y) {
const x = a.x + (m.y - a.y) * (b.x - a.x) / (b.y - a.y);
if (x >= m.x && x < qx) { qx = x; best = a.x > b.x ? a : b; if (x === m.x) break; }
} else if (Math.min(a.x, b.x) >= m.x && Math.min(a.x, b.x) < qx) { qx = Math.min(a.x, b.x); best = a.x < b.x ? a : b; }
}
p = p.next;
} while (p !== outer);
if (!best) return outer;
// a vertex inside the triangle (m, hit, best) with the smallest angle to the ray is visible instead
const hit = { x: qx, y: m.y };
let sel = best, tanMin = Infinity;
p = outer;
do {
if (p !== best && m.x <= p.x && p.x <= best.x) {
const inside = m.y < best.y ? inTri(m, hit, best, p) || inTri(m, best, hit, p) : inTri(m, best, hit, p) || inTri(m, hit, best, p);
if (inside && !(p.x === m.x && p.y === m.y)) {
const tan = Math.abs(m.y - p.y) / (p.x - m.x || 1e-300);
if (tan < tanMin || (tan === tanMin && p.x > sel.x)) { tanMin = tan; sel = p; }
}
}
p = p.next;
} while (p !== outer);
split(sel, m);
return outer;
}Whether a corner can be cut off as a triangle.
The corner must have a positive cross product, and no other vertex (one that is not equal in position to a, b or c) may lie inside the triangle while itself being a reflex or straight corner (cross <= 0). All comparisons are exact.
function isEar(e) {
const a = e.prev, b = e, c = e.next;
if (cross(a, b, c) <= 0) return false;
let p = c.next;
while (p !== a) {
if (p.i !== a.i && p.i !== b.i && p.i !== c.i && (p.x !== a.x || p.y !== a.y) && (p.x !== c.x || p.y !== c.y) && (p.x !== b.x || p.y !== b.y) && inTri(a, b, c, p) && cross(p.prev, p, p.next) <= 0) return false;
p = p.next;
}
return true;
}The triangles of 3D rings that lie on one plane.
Projects onto the two axes left after dropping the largest component of the Newell normal (from geo-math.js, not in this review) and keeps the winding by swapping axes when that component is negative. Projection only drops a coordinate, so nothing is rounded.
/** Triangulate 3D rings on (about) one plane: [outer, ...holes] of [x, y, z] → indexes into their concatenation. */
export function planeTriangulate(rings) {
if (!rings.length || rings[0].length < 3) return [];
const n = newell(rings[0]);
const ax = Math.abs(n[0]), ay = Math.abs(n[1]), az = Math.abs(n[2]);
// drop the largest axis; keep the winding consistent with the normal
let proj;
if (az >= ax && az >= ay) proj = n[2] >= 0 ? (p) => [p[0], p[1]] : (p) => [p[1], p[0]];
else if (ax >= ay) proj = n[0] >= 0 ? (p) => [p[1], p[2]] : (p) => [p[2], p[1]];
else proj = n[1] >= 0 ? (p) => [p[2], p[0]] : (p) => [p[0], p[2]];
if (rings.length === 1 && rings[0].length === 3) return [0, 1, 2];
const r2 = rings.map((r) => r.map(proj));
return triangulate(r2[0], r2.slice(1));
}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.