Finds the closed rooms and the outer outline that a set of wall outlines encloses, with each room's area, perimeter and centroid.
How the precision is kept
Wall edges are split where they cross or overlap, the pieces on the boundary between wall and open space are kept, and they are walked into loops. Coordinates stay 64-bit and unrounded; points are matched by a grid of 0.001 mm. Areas come from the shoelace formula and perimeters from sums of edge lengths.
Calculations under this policy
11 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.
Finds where two wall edges cross, touch or run along each other.
t = (c − a) × s ÷ (r × s); u = (c − a) × r ÷ (r × s)
Edges are parallel when |r × s| is below 1e-12 × |r| |s|, a relative test. Parallel edges are cut at each other's ends only when collinear within 1e-6 × |r|. A crossing is kept when its parameter lies inside (1e-6, 1 − 1e-6), a tolerance relative to the edge's length.
addons/trusscraft/lib/bim/model-rooms.js
lines 30 to 42
CadCraft 0.8.2
const r = sub(b, a), s = sub(d, c), den = cross(r, s), ca = sub(c, a);
if (Math.abs(den) < 1e-12 * Math.hypot(...r) * Math.hypot(...s)) {
// parallel: overlapping when collinear — each cut at the other's ends
if (Math.abs(cross(ca, r)) > 1e-6 * Math.hypot(...r)) continue;
const rr = dot(r, r), ss = dot(s, s);
for (const q of [c, d]) { const t = dot(sub(q, a), r) / rr; if (t > EPS && t < 1 - EPS) cuts[i].push(t); }
for (const q of [a, b]) { const t = dot(sub(q, c), s) / ss; if (t > EPS && t < 1 - EPS) cuts[j].push(t); }
continue;
}
const t = cross(ca, s) / den, u = cross(ca, r) / den;
if (t < -EPS || t > 1 + EPS || u < -EPS || u > 1 + EPS) continue;
if (t > EPS && t < 1 - EPS) cuts[i].push(t);
if (u > EPS && u < 1 - EPS) cuts[j].push(u);
Points matched on a grid
64-bit
Decides when two split points are the same point.
key = (round(x ÷ 0.001), round(y ÷ 0.001))
Points are identified by rounding to a grid of 0.001 mm, and the first point that lands in a cell keeps its unrounded coordinates. Cut parameters are rounded to 9 decimals to remove duplicates. Two points closer than the grid can still fall in different cells.
Keeps the pieces that have a wall on one side and open space on the other.
test points = middle ± n × min(0.5, length ÷ 4)
A point just left and a point just right of the piece's middle are tested against every wall outline. The offset is 0.5 mm, or a quarter of the piece's length when that is smaller.
addons/trusscraft/lib/bim/model-rooms.js
lines 63 to 65
CadCraft 0.8.2
const m = [(p[0] + q[0]) / 2, (p[1] + q[1]) / 2], n = [-d[1] / L, d[0] / L], h = Math.min(0.5, L / 4);
const left = inside(m[0] + n[0] * h, m[1] + n[1] * h), right = inside(m[0] - n[0] * h, m[1] - n[1] * h);
if (left === right) continue;
Next piece at a joint
64-bit
Chooses which boundary piece a loop follows where several meet.
a = (angle back − angle of piece), brought into (0, 2π]
Directions are atan2 angles; the difference is shifted by whole turns until it lies above 1e-9 and at most 2π + 1e-9, and the smallest wins.
addons/trusscraft/lib/bim/model-rooms.js
lines 82 to 88
CadCraft 0.8.2
const back = Math.atan2(pts.get(cur)[1] - pts.get(at)[1], pts.get(cur)[0] - pts.get(at)[0]);
// the first piece clockwise from the way back
let best = null, bestA = Infinity;
for (const c of out.get(at) || []) {
if (c.used) continue;
let a = back - c.ang; while (a <= 1e-9) a += 2 * Math.PI; while (a > 2 * Math.PI + 1e-9) a -= 2 * Math.PI;
if (a < bestA) { bestA = a; best = c; }
Room area and perimeter
64-bit
Tells rooms from islands and gives each room its net area and full perimeter.
area = loop area − Σ hole areas; perimeter = loop + Σ hole perimeters
A loop is a room when its area is above 1 mm² and an island when below −1 mm². Hole areas are subtracted and hole perimeters added after the loops are found.
addons/trusscraft/lib/bim/model-rooms.js
lines 97 to 110
CadCraft 0.8.2
const A = area(l);
if (A > 1) rooms.push({ poly: l, holes: [], area: A, perimeter: perim(l), centroid: centroid(l) });
else if (A < -1) islands.push(l);
}
// a clockwise loop inside a room is an island in it (a hole); otherwise it runs round a building
for (const l of islands) {
const host = rooms.filter((r) => inPoly(l[0][0], l[0][1], r.poly)).sort((a, b) => a.area - b.area)[0];
if (host && Math.abs(area(l)) < host.area) host.holes.push(l.slice().reverse());
else { const o = l.slice().reverse(); outlines.push({ poly: o, area: area(o), perimeter: perim(o) }); }
}
for (const r of rooms) {
if (!r.holes.length) continue;
r.area -= r.holes.reduce((s, h) => s + area(h), 0);
r.perimeter += r.holes.reduce((s, h) => s + perim(h), 0);
Polygon area
64-bit
The signed area of a loop.
A = ½ Σ (xᵢ yᵢ₊₁ − xᵢ₊₁ yᵢ)
The shoelace sum over absolute coordinates, added in point order. For a plan far from the origin the products are large and partly cancel.
addons/trusscraft/lib/bim/model-rooms.js
line 121
CadCraft 0.8.2
export function area(p) { let s = 0; for (let i = 0; i < p.length; i++) { const a = p[i], b = p[(i + 1) % p.length]; s += a[0] * b[1] - a[1] * b[0]; } return s / 2; }
Polygon perimeter
64-bit
The length round a loop.
P = Σ √(Δx² + Δy²)
A sum of Math.hypot edge lengths in point order.
addons/trusscraft/lib/bim/model-rooms.js
line 122
CadCraft 0.8.2
export function perim(p) { let s = 0; for (let i = 0; i < p.length; i++) { const a = p[i], b = p[(i + 1) % p.length]; s += Math.hypot(b[0] - a[0], b[1] - a[1]); } return s; }
Polygon centroid
64-bit
The center of area of a loop.
C = Σ (a + b)(a × b) ÷ (3 Σ a × b)
The standard polygon centroid on absolute coordinates. When the doubled area is under 1e-9 the first point is returned instead of dividing.
addons/trusscraft/lib/bim/model-rooms.js
lines 123 to 127
CadCraft 0.8.2
export function centroid(p) {
let A = 0, x = 0, y = 0;
for (let i = 0; i < p.length; i++) { const a = p[i], b = p[(i + 1) % p.length], c = a[0] * b[1] - b[0] * a[1]; A += c; x += (a[0] + b[0]) * c; y += (a[1] + b[1]) * c; }
return Math.abs(A) < 1e-9 ? p[0] : [x / (3 * A), y / (3 * A)];
}
Label point inside a room
64-bit
A point well inside a room for its label.
The centroid when it is inside the polygon; otherwise the middle of the widest stretch of the horizontal line through the centroid, found by linear interpolation along the crossed edges.
addons/trusscraft/lib/bim/model-rooms.js
lines 128 to 141
CadCraft 0.8.2
/** A point well inside a polygon (for a label): the centroid when it is inside, else the middle of the widest span through it. */
export function labelPoint(p) {
const c = centroid(p);
if (inPoly(c[0], c[1], p)) return c;
const xs = [];
for (let i = 0; i < p.length; i++) {
const a = p[i], b = p[(i + 1) % p.length];
if ((a[1] > c[1]) !== (b[1] > c[1])) xs.push(a[0] + (c[1] - a[1]) / (b[1] - a[1]) * (b[0] - a[0]));
}
xs.sort((a, b) => a - b);
let best = null;
for (let i = 0; i + 1 < xs.length; i += 2) if (!best || xs[i + 1] - xs[i] > best[1] - best[0]) best = [xs[i], xs[i + 1]];
return best ? [(best[0] + best[1]) / 2, c[1]] : c;
}
Point inside a polygon
64-bit
Tests whether a plan point lies inside a polygon.
Even-odd ray crossing with strict comparisons and one division per crossed edge. A point exactly on an edge can fall either way.
addons/trusscraft/lib/bim/model-rooms.js
lines 142 to 149
CadCraft 0.8.2
export function inPoly(x, y, p) {
let inside = false;
for (let i = 0, j = p.length - 1; i < p.length; j = i++) {
const [xi, yi] = p[i], [xj, yj] = p[j];
if ((yi > y) !== (yj > y) && x < (xj - xi) * (y - yi) / (yj - yi) + xi) inside = !inside;
}
return inside;
}
Points within 1e-6 (absolute) of the one before are dropped. A point is removed as collinear by a test relative to the two edge lengths, and only when the two edges point the same way.
addons/trusscraft/lib/bim/model-rooms.js
lines 150 to 164
CadCraft 0.8.2
/** Drop repeated and collinear points of a loop. */
function clean(p) {
let q = p.filter((v, i) => i === 0 || Math.hypot(v[0] - p[i - 1][0], v[1] - p[i - 1][1]) > 1e-6);
if (q.length > 1 && Math.hypot(q[0][0] - q[q.length - 1][0], q[0][1] - q[q.length - 1][1]) <= 1e-6) q.pop();
let changed = true;
while (changed && q.length > 3) {
changed = false;
for (let i = 0; i < q.length; i++) {
const a = q[(i + q.length - 1) % q.length], b = q[i], c = q[(i + 1) % q.length];
const ab = sub(b, a), bc = sub(c, b);
if (Math.abs(cross(ab, bc)) <= 1e-7 * (Math.hypot(...ab) * Math.hypot(...bc) + 1e-12) && dot(ab, bc) > 0) { q.splice(i, 1); changed = true; break; }
}
}
return q;
}
In detail
Method
Segment splitting by cross products; boundary test by sampling just left and right of each piece; loop walking by the first piece clockwise from the way back; shoelace area and polygon centroid.
Number types
64-bit numbers; plan millimeters.
Tolerances
Parallel edges: |r × s| below 1e-12 × |r| |s|. Collinear: within 1e-6 × |r|. Cut parameters kept inside (1e-6, 1 − 1e-6). Point grid: 0.001 mm. Cut parameters deduplicated at 9 decimals. Room: area above 1 mm². Collinear point removal: 1e-7 relative.
Limits
Points closer than the 0.001 mm grid can fall in different cells. The area and centroid sums use absolute coordinates, so they lose digits for plans far from the origin. A point exactly on an edge can test inside or outside.
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.