Cuts the lines, arcs and fills of a clipped block reference or linked drawing at the clip polygon, and converts the clip between drawing and block coordinates.
How the precision is kept
Lines are cut by solving two linear equations per clip edge and arcs by a quadratic per clip edge, all in 64-bit numbers. Pieces are kept or dropped by testing their middle point against the polygon with an even-odd ray count. The tolerances are fixed values, not scaled to the size of the drawing.
Open item. Scale the parallel test (cross product below 1e-12) to the lengths of the two segments, so that it behaves the same in a drawing in millimeters and in kilometers.
Calculations under this policy
10 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 division by bᵧ − aᵧ runs only when the two ends are on different sides of the point's height, so it is never a division by zero. The decision is made in ordinary 64-bit arithmetic with no tolerance, so a point exactly on the boundary can fall either way.
xclip.js
lines 20 to 28
CadCraft 0.8.2
/** Even–odd point in polygon. */
export function insidePoly(p, poly) {
let c = false;
for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
const a = poly[i], b = poly[j];
if ((a.y > p.y) !== (b.y > p.y) && p.x < ((b.x - a.x) * (p.y - a.y)) / (b.y - a.y) + a.x) c = !c;
}
return c;
}
Where a line crosses the clip edges
64-bit
The positions along a line segment where it crosses the edges of the clip polygon.
den = d × e; t = ((p − a) × e) ÷ den; u = ((p − a) × d) ÷ den; kept when EPS < t < 1 − EPS and −EPS ≤ u ≤ 1 + EPS
Two cross products divided by a third. An edge is treated as parallel when |den| < 1e-12; den has the unit of length squared and the limit is not scaled, so it means a different angle in a small drawing than in a large one.
xclip.js
lines 30 to 42
CadCraft 0.8.2
/** Where segment a→b crosses the polygon's edges: parameters t in (0, 1). */
function segCrossings(a, b, poly) {
const out = [];
const dx = b.x - a.x, dy = b.y - a.y;
for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
const p = poly[j], q = poly[i], ex = q.x - p.x, ey = q.y - p.y;
const den = dx * ey - dy * ex;
if (Math.abs(den) < EPS) continue;
const tt = ((p.x - a.x) * ey - (p.y - a.y) * ex) / den, u = ((p.x - a.x) * dy - (p.y - a.y) * dx) / den;
if (tt > EPS && tt < 1 - EPS && u >= -EPS && u <= 1 + EPS) out.push(tt);
}
return out;
}
Line cut to the clip
64-bit
The pieces of a line that lie inside the clip polygon.
piece ends = a + (b − a)·t₀ and a + (b − a)·t₁; kept when the middle point is inside
End points are computed from the original end a and the parameter, so an uncut end is reproduced as a + (b − a)·0 = a and a + (b − a)·1, which can differ from b in the last bit. Neighboring pieces closer than 1e-12 in parameter are merged.
xclip.js
lines 44 to 57
CadCraft 0.8.2
/** A line primitive cut to the polygon → the pieces inside. */
export function clipLine(q, poly) {
const a = { x: q.x1, y: q.y1 }, b = { x: q.x2, y: q.y2 };
const ts = [0, ...segCrossings(a, b, poly).sort((x, y) => x - y), 1], out = [];
for (let i = 0; i + 1 < ts.length; i++) {
const t0 = ts[i], t1 = ts[i + 1];
if (t1 - t0 < EPS) continue;
const m = (t0 + t1) / 2;
if (!insidePoly({ x: a.x + (b.x - a.x) * m, y: a.y + (b.y - a.y) * m }, poly)) continue;
const prev = out[out.length - 1];
if (prev && Math.abs(prev.t1 - t0) < EPS) prev.t1 = t1; else out.push({ t0, t1 });
}
return out.map(({ t0, t1 }) => ({ ...q, x1: a.x + (b.x - a.x) * t0, y1: a.y + (b.y - a.y) * t0, x2: a.x + (b.x - a.x) * t1, y2: a.y + (b.y - a.y) * t1 }));
}
Arc cut to the clip
64-bit
The sub-arcs of an arc that lie inside the clip polygon.
A·s² + B·s + C = 0 on each clip edge; s = (−B ± √(B² − 4AC)) ÷ 2A; angle = atan2(y − cy, x − cx) − a₀
The textbook quadratic formula: when B² is much larger than 4AC one of the two roots subtracts nearly equal numbers. An edge with a discriminant below zero is skipped, so a clip edge that only touches the arc within rounding may or may not cut it. The cut angles keep the arc's own center and radius, so each piece is an exact part of the same circle.
xclip.js
lines 59 to 86
CadCraft 0.8.2
/** An arc primitive (counter-clockwise a0 → a1) cut to the polygon → the sub-arcs inside. */
export function clipArc(q, poly) {
let sweep = q.a1 - q.a0;
while (sweep <= 0) sweep += TAU;
const ang = [];
for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
const p = poly[j], r = poly[i], dx = r.x - p.x, dy = r.y - p.y, fx = p.x - q.cx, fy = p.y - q.cy;
const A = dx * dx + dy * dy, B = 2 * (fx * dx + fy * dy), C = fx * fx + fy * fy - q.r * q.r, D = B * B - 4 * A * C;
if (A < EPS || D < 0) continue;
for (const s of [(-B - Math.sqrt(D)) / (2 * A), (-B + Math.sqrt(D)) / (2 * A)]) {
if (s < -EPS || s > 1 + EPS) continue;
let a = Math.atan2(p.y + dy * s - q.cy, p.x + dx * s - q.cx) - q.a0;
while (a < 0) a += TAU;
while (a >= TAU) a -= TAU;
if (a > EPS && a < sweep - EPS) ang.push(a);
}
}
const ts = [0, ...ang.sort((x, y) => x - y), sweep], out = [];
for (let i = 0; i + 1 < ts.length; i++) {
const s0 = ts[i], s1 = ts[i + 1];
if (s1 - s0 < 1e-9) continue;
const m = q.a0 + (s0 + s1) / 2;
if (!insidePoly({ x: q.cx + q.r * Math.cos(m), y: q.cy + q.r * Math.sin(m) }, poly)) continue;
const prev = out[out.length - 1];
if (prev && Math.abs(prev.s1 - s0) < 1e-9) prev.s1 = s1; else out.push({ s0, s1 });
}
return out.map(({ s0, s1 }) => ({ ...q, a0: q.a0 + s0, a1: q.a0 + s1 }));
}
Fill cut to the clip
64-bit
A filled ring cut to a convex clip polygon.
per clip edge: keep points with side ≥ −EPS; crossing = p + (q − p)·((a − p) × e) ÷ ((q − p) × e)
Each new corner is one linear intersection in 64-bit numbers. The side test allows −1e-12 on a cross product with the unit of length squared, not scaled. When the clip polygon is concave the ring is returned whole if any of its points is inside, and dropped otherwise.
xclip.js
lines 100 to 128
CadCraft 0.8.2
/** A fill ring [x, y, …] cut to the polygon (Sutherland–Hodgman; for a concave clip, rings across it are kept whole). */
export function clipRing(l, poly) {
let pts = [];
for (let i = 0; i + 1 < l.length; i += 2) pts.push({ x: l[i], y: l[i + 1] });
if (pts.length > 1 && Math.abs(pts[0].x - pts[pts.length - 1].x) < EPS && Math.abs(pts[0].y - pts[pts.length - 1].y) < EPS) pts.pop();
const ins = pts.filter((p) => insidePoly(p, poly)).length;
if (ins === pts.length && !poly.some((p) => insidePoly(p, pts))) return l;
if (!convex(poly)) return ins ? l : null;
let ccw = 0;
for (let i = 0; i < poly.length; i++) { const a = poly[i], b = poly[(i + 1) % poly.length]; ccw += a.x * b.y - b.x * a.y; }
const side = (p, a, b) => ((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)) * (ccw >= 0 ? 1 : -1) >= -EPS;
for (let i = 0; i < poly.length && pts.length; i++) {
const a = poly[i], b = poly[(i + 1) % poly.length], inp = pts;
pts = [];
for (let k = 0; k < inp.length; k++) {
const p = inp[k], q = inp[(k + 1) % inp.length], pi = side(p, a, b), qi = side(q, a, b);
if (pi) pts.push(p);
if (pi !== qi) {
const dx = q.x - p.x, dy = q.y - p.y, ex = b.x - a.x, ey = b.y - a.y, den = dx * ey - dy * ex;
if (Math.abs(den) > EPS) { const tt = ((a.x - p.x) * ey - (a.y - p.y) * ex) / den; pts.push({ x: p.x + dx * tt, y: p.y + dy * tt }); }
}
}
}
if (pts.length < 3) return null;
const out = [];
for (const p of pts) out.push(p.x, p.y);
out.push(pts[0].x, pts[0].y);
return out;
}
Is the clip polygon convex
64-bit
Decides whether fills can be cut to this clip polygon.
z = (b − a) × (c − b) at every corner; all signs equal → convex
Corners with |z| < 1e-12 are ignored as straight. The limit is absolute on a value with the unit of length squared.
xclip.js
lines 88 to 98
CadCraft 0.8.2
const convex = (poly) => {
let sign = 0;
for (let i = 0; i < poly.length; i++) {
const a = poly[i], b = poly[(i + 1) % poly.length], c = poly[(i + 2) % poly.length];
const z = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
if (Math.abs(z) < EPS) continue;
if (sign && Math.sign(z) !== sign) return false;
sign = Math.sign(z);
}
return true;
};
Clip polygon in drawing coordinates
64-bit
The clip polygon of a reference moved from the block's coordinates into the drawing.
M = m · insert matrix; point = M · p
One 2 × 3 matrix product written out term by term, then one matrix-times-point per corner. No rounding and no tolerance.
xclip.js
lines 143 to 147
CadCraft 0.8.2
/** The clip polygon of a reference in world coordinates (through its insert matrix and any outer transform m). */
export function worldClip(ref, block, m = null) {
const im = insertMatrix(ref, block), M = m ? [m[0] * im[0] + m[2] * im[1], m[1] * im[0] + m[3] * im[1], m[0] * im[2] + m[2] * im[3], m[1] * im[2] + m[3] * im[3], m[0] * im[4] + m[2] * im[5] + m[4], m[1] * im[4] + m[3] * im[5] + m[5]] : im;
return ref.clip.pts.map((p) => mApply(M, p));
}
Clip read from a file
64-bit
Turns the clip boundary stored in a DWG or DXF file into the polygon kept on the reference.
point = I · (T · p), with T the clip transform and I the inverse block transform (3 × 4 each)
Two matrix-times-point steps on the x and y rows only. A two-point boundary becomes a rectangle from the two corners. A matrix that does not have 12 finite numbers is replaced by the identity.
xclip.js
lines 155 to 169
CadCraft 0.8.2
/**
* SPATIAL_FILTER → { pts } in block coordinates: its boundary (2 points = a rectangle) through the clip bound transform
* and the inverse block transform (both 3 × 4, rows). Spec gap: which way those apply is not written down; in every file
* we can make (ezdxf, then the ODA converter) both are the identity and the boundary is in block coordinates.
*/
export function clipFromFilter(o) {
const ps = Array.isArray(o?.points) ? o.points.filter((p) => Number.isFinite(p.x) && Number.isFinite(p.y)) : [];
if (ps.length < 2) return null;
const mat = (a) => (Array.isArray(a) && a.length === 12 && a.every(Number.isFinite) ? a : [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0]);
const T = mat(o.clipTransform), I = mat(o.inverseBlockTransform);
const ap = (m, p) => ({ x: m[0] * p.x + m[1] * p.y + m[3], y: m[4] * p.x + m[5] * p.y + m[7] });
let pts = ps.length === 2 ? [ps[0], { x: ps[1].x, y: ps[0].y }, ps[1], { x: ps[0].x, y: ps[1].y }] : ps;
pts = pts.map((p) => ap(I, ap(T, p)));
return { pts: pts.map((p) => ({ x: p.x, y: p.y })) };
}
Objects cut to the clip when binding
64-bit
The objects of a block cut to the clip polygon: whole when inside, as line and arc pieces when crossing.
An object is kept unchanged when the four corners of its bounding box are inside the polygon and no polygon corner is inside the box. Crossing lines, arcs, circles, polylines and ellipses are replaced by the line and arc pieces from clipLine and clipArc; a polyline or ellipse therefore comes out as the primitives geom.js draws it with.
xclip.js
lines 178 to 208
CadCraft 0.8.2
/**
* A block's objects cut to a clip polygon in the block's coordinates (WL.17, XREF Bind "clipped part only"). Objects wholly
* inside stay as they are; lines, arcs, circles, polylines and ellipses crossing the boundary become their inside pieces
* as lines and arcs (with the object's layer, colour, linetype, lineweight); fills are cut; texts, points, attribute
* definitions, dimensions, leaders and nested blocks crossing the boundary are kept when their insertion point (or centre)
* is inside. → { entities, cut, kept }
*/
export function clipEntities(doc, entities, poly) {
const out = [];
let cut = 0, kept = 0;
const GEOM = ['id', 'type', 'x1', 'y1', 'x2', 'y2', 'cx', 'cy', 'r', 'a0', 'a1', 'pts', 'closed', 'mx', 'my', 'ratio', 't0', 't1', 'w', 'z1', 'z2'];
const props = (e) => { const o = { ...e }; for (const k of GEOM) delete o[k]; return o; }; // layer, colour, linetype, lineweight…
for (const e of entities) {
const b = entityBounds(e, doc.blocks);
const corners = validBounds(b) ? [{ x: b.minX, y: b.minY }, { x: b.maxX, y: b.minY }, { x: b.maxX, y: b.maxY }, { x: b.minX, y: b.maxY }] : [];
const allIn = corners.length && corners.every((p) => insidePoly(p, poly)) && !poly.some((p) => p.x > b.minX && p.x < b.maxX && p.y > b.minY && p.y < b.maxY);
if (allIn) { out.push(e); continue; }
if (['line', 'arc', 'circle', 'poly', 'ellipse'].includes(e.type)) {
const ps = prims(e, null).flatMap((q) => (q.k === 'L' ? clipLine(q, poly) : clipArc(q, poly)));
for (const q of ps) out.push(q.k === 'L' ? { type: 'line', ...props(e), x1: q.x1, y1: q.y1, x2: q.x2, y2: q.y2 } : { type: 'arc', ...props(e), cx: q.cx, cy: q.cy, r: q.r, a0: q.a0, a1: q.a1 });
if (ps.length) cut++;
} else if (e.type === 'hatch') {
const loops = (e.loops || []).map((l) => clipRing(l, poly)).filter(Boolean);
if (loops.length) { out.push({ ...e, loops }); cut++; }
} else {
const at = Number.isFinite(e.x) && Number.isFinite(e.y) ? { x: e.x, y: e.y } : validBounds(b) ? { x: (b.minX + b.maxX) / 2, y: (b.minY + b.maxY) / 2 } : null;
if (at && insidePoly(at, poly)) { out.push(e); kept++; }
}
}
return { entities: out, cut, kept };
}
New clip boundary into block coordinates
64-bit
Stores a boundary picked in the drawing as a polygon in the block's own coordinates.
d = m₀·m₃ − m₁·m₂; inv = adjugate ÷ d; stored point = inv · picked point
The closed-form inverse of the reference's 2 × 3 matrix, with six divisions by the determinant. A reference whose determinant is below 1e-300 in size only loses its old clip. The stored points are not rounded.
Segment and segment by cross products; circle and segment by the quadratic formula; even-odd point in polygon; Sutherland–Hodgman for fills (named in the code comment).
Number types
64-bit numbers; points are {x, y} objects, rings are arrays [x, y, …].
Tolerances
EPS = 1e-12, absolute: on the cross product of two directions (parallel test), on the squared length of a clip edge, on line parameters in 0…1 and on angles in radians. Sub-arcs shorter than 1e-9 rad are dropped. XCLIP skips a reference whose matrix determinant is below 1e-300.
Checked by
bin/test-cadcraft.mjs cuts a line that crosses a square clip with clipLine.
Limits
A fill that crosses a concave clip polygon is kept whole, not cut. Texts and points are kept or dropped by their insertion point only.
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.