Resources Numerical accuracy Calculation policy
Measures a closed outline with other shapes cut out of it: the remaining area, the length of outline left and the length of the cuts, as used for planted areas around paving, walls and steps.
64-bit numbers throughout. The area is summed over horizontal slabs cut at every vertex and every edge crossing, where the region's width is linear, so no sampling is involved for straight edges. Crossings come from one division each, with a tolerance of 1e-9 scaled to the edge lengths. Crossing parameters are rounded to 9 decimals before the boundary pieces are cut.
Open item. Scale the absolute 1e-9 thresholds for short edges, thin slabs and small holes to the size of the outline.
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 bin/test-landscape.mjs
The signed area of a closed outline.
A = −½ Σ (xⱼ + xᵢ)(yⱼ − yᵢ)
The trapezoid form of the shoelace sum on the coordinates as given, added in vertex order. Coordinates are not shifted to a local origin, so for a small outline far from the origin the terms are large and nearly cancel.
export function polyArea(pts) { let a = 0; for (let i = 0, j = pts.length - 1; i < pts.length; j = i++) a += (pts[j].x + pts[i].x) * (pts[j].y - pts[i].y); return -a / 2; }Whether a point lies inside an outline, used to keep or drop each boundary piece.
count edges with (aᵧ > y) ≠ (bᵧ > y) and x < x on the edge at height y
Even-odd ray casting with one division per straddling edge and no tolerance, so a point exactly on an edge can fall either way. The strict and non-strict comparisons on y mean the divisor is never zero.
export function pointIn(x, y, pts) {
let c = false;
for (let i = 0, j = pts.length - 1; i < pts.length; j = i++) {
const a = pts[i], b = pts[j];
if ((a.y > y) !== (b.y > y) && x < ((b.x - a.x) * (y - a.y)) / (b.y - a.y) + a.x) c = !c;
}
return c;
}The position along one edge where another edge crosses or touches it.
t = ((c − a) × s) ÷ (r × s); u = ((c − a) × r) ÷ (r × s)
The parallel test scales with the two edge lengths: |r × s| below 1e-9 × (|r||s| + 1e-9) returns no crossing. t and u are accepted from −1e-9 to 1 + 1e-9 and t is clamped to [0, 1].
/** Where segment ab crosses segment cd (proper or touching), as t along ab, else null. Parallel lines never cross here. */
export function segCross(a, b, c, d) {
const rx = b.x - a.x, ry = b.y - a.y, sx = d.x - c.x, sy = d.y - c.y, den = rx * sy - ry * sx;
if (Math.abs(den) < EPS * (Math.hypot(rx, ry) * Math.hypot(sx, sy) + EPS)) return null;
const t = ((c.x - a.x) * sy - (c.y - a.y) * sx) / den, u = ((c.x - a.x) * ry - (c.y - a.y) * rx) / den;
return t >= -EPS && t <= 1 + EPS && u >= -EPS && u <= 1 + EPS ? Math.min(1, Math.max(0, t)) : null;
}The area of the outline with every hole removed, overlaps counted once.
area = Σ over slabs of (width inside the outline and outside all holes at mid-height) × slab height
Slab heights are differences of sorted y values, and the widths are differences of sorted x crossings at mid-height; both are sums of many terms added in order. Slabs thinner than 1e-9 in absolute height are skipped.
// the area, slab by slab
const Y = [...ys].sort((p, q) => p - q);
let area = 0;
for (let s = 0; s + 1 < Y.length; s++) {
const h = Y[s + 1] - Y[s];
if (h < EPS) continue;
const ym = (Y[s] + Y[s + 1]) / 2, xs = [];
for (const e of edges) {
if ((e.a.y > ym) === (e.b.y > ym)) continue;
xs.push({ x: e.a.x + ((ym - e.a.y) * (e.b.x - e.a.x)) / (e.b.y - e.a.y), pi: e.pi });
}
xs.sort((p, q) => p.x - q.x);
const par = new Uint8Array(polys.length);
let holesIn = 0, w = 0;
for (let k = 0; k < xs.length; k++) {
const { x, pi } = xs[k];
if (pi > 0) holesIn += par[pi] ? -1 : 1;
par[pi] ^= 1;
if (k + 1 < xs.length && par[0] && holesIn === 0) w += xs[k + 1].x - x;
}
area += w * h;
}The pieces of the outline that remain and the pieces of the holes that cut it, with their total lengths.
length = Σ |b − a| over kept pieces; a = e.a + t₀(e.b − e.a), b = e.a + t₁(e.b − e.a)
Each crossing parameter is rounded to 9 decimals (Math.round(t × 1e9) ÷ 1e9) before the pieces are cut, so a piece's end point can sit up to 5e-10 of the edge length from the computed crossing. Pieces shorter than 1e-9 in parameter are dropped.
// the boundary pieces
const out = [];
let outlineLength = 0, cutLength = 0;
for (const e of edges) {
const ts = [...new Set(e.ts.map((t) => Math.round(t * 1e9) / 1e9))].sort((p, q) => p - q);
for (let k = 0; k + 1 < ts.length; k++) {
const t0 = ts[k], t1 = ts[k + 1];
if (t1 - t0 < 1e-9) continue;
const tm = (t0 + t1) / 2, mx = e.a.x + tm * (e.b.x - e.a.x), my = e.a.y + tm * (e.b.y - e.a.y);
const keep = e.pi === 0 ? !inHole(mx, my) : pointIn(mx, my, A) && !inHole(mx, my, e.pi);
if (!keep) continue;
const a = { x: e.a.x + t0 * (e.b.x - e.a.x), y: e.a.y + t0 * (e.b.y - e.a.y) }, b = { x: e.a.x + t1 * (e.b.x - e.a.x), y: e.a.y + t1 * (e.b.y - e.a.y) };
const L = Math.hypot(b.x - a.x, b.y - a.y);
if (e.pi === 0) outlineLength += L; else cutLength += L;
out.push({ a, b, from: e.pi === 0 ? 'outline' : 'cut' });
}
}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.