Computational geometry · interactive
Four pieces of 2D geometry that every CAD-like editor needs, and the specific way each one goes wrong. Everything on this page is draggable — the numbers are computed live, not illustrated.
Written from building the geometry under pattern and design software, where being wrong by a millimetre is not a rounding error, it is a ruined piece of fabric.
Almost every operation downstream — which side is "outside", which way an offset grows, whether a boolean subtracts or adds — depends on which way round the polygon is wound. The shoelace formula gives you that, as the sign of twice the enclosed area:
function signedArea(pts) {
let s = 0;
for (let i = 0; i < pts.length; i++) {
const a = pts[i], b = pts[(i + 1) % pts.length];
s += a.x * b.y - b.x * a.y;
}
return s / 2;
}The trapPositive does not mean counter-clockwise. It means counter-clockwise in maths axes, with y pointing up. A canvas, an SVG and most screen coordinate systems point y down, which flips the sign of every polygon you will ever handle. Libraries disagree about this, so a shape that is "CCW" in one is "CW" in the next.
The fix is not to memorise a convention. It is to never assume one: read the orientation from the polygon itself at the top of every operation that cares, and normalise. Two lines, and a whole family of sign bugs stops existing.
Fire a ray from the point in any direction and count how many times it crosses the boundary. Odd is inside, even is outside. It does not care whether the polygon is convex, concave or wound the wrong way, which is what makes it the default.
Put the probe inside the notch. It is within the bounding box, it looks surrounded, and the count still comes out even — which is the whole reason you do not test bounding boxes and call it hit testing.
The trapA point exactly on the boundary is neither reliably in nor reliably out, and no amount of care in the implementation fixes that — it is inherent to the test. The usual half-open comparison (a.y > p.y !== b.y > p.y) keeps a vertex from being counted twice, but it does not make the boundary answer meaningful. If your users can click an edge, test edge proximity separately, with a tolerance, and decide the boundary case deliberately.
Snapping, hit testing, clearance checks and offset verification all reduce to one question: how far is this point from the shape? The tempting shortcut is to measure to the nearest vertex, because vertices are what you have in an array.
Park the probe beside the middle of a long edge. The true distance is small; the nearest vertex can be several times further. On a long straight seam that error is unbounded — it grows with the length of the edge.
The correct version projects onto each segment and clamps the parameter to [0, 1], which is what makes it a segment rather than an infinite line:
function distanceToSegment(p, a, b) {
const abx = b.x - a.x, aby = b.y - a.y;
const l2 = abx * abx + aby * aby;
// a zero-length segment is a point, not a division by zero
if (l2 === 0) return Math.hypot(p.x - a.x, p.y - a.y);
let t = ((p.x - a.x) * abx + (p.y - a.y) * aby) / l2;
t = t < 0 ? 0 : t > 1 ? 1 : t; // the clamp is the whole trick
return Math.hypot(p.x - (a.x + abx * t), p.y - (a.y + aby * t));
}The faint circle in the figure is that distance drawn as a radius. It should touch the outline and never cross it — a cheap visual assertion, and the kind of thing worth putting in a test.
Three points are collinear when the cross product of their differences is zero. In floating point it is never zero, so every real implementation compares against an epsilon — and that epsilon quietly decides whether a corner exists.
The trapComparing the raw cross product against an epsilon is the common version, and it is wrong: the cross product scales with the length of the segments, so the same epsilon is strict on a short edge and permissive on a long one. Divide by the base length first, and your epsilon becomes an actual distance — something you can state in millimetres and defend to whoever is cutting the material.
Which value is right is a domain question, not a numerical one. Too strict and a smooth curve keeps hundreds of redundant points and every downstream operation slows down. Too loose and a real, shallow corner disappears — and on a garment piece a vanished corner is a seam that does not match its neighbour.
Offsetting — seam allowance, tool radius, clearance — is where all four of the above land at once, and it deserves more room than a section. The short version: moving each vertex along its angle bisector, which is the first thing anyone writes, puts the corner at d / sin(θ/2) from the original instead of d. On a star offset by 40 units, the worst point lands 121.8 units out. It still looks like an offset.
The long version, with a demo you can drag and a library that ships the function proving its own output: polygon-offset, and the interactive playground.
If you want to see these ideas carrying real weight, there is a 3D configurator whose output a factory could cut and a nesting playground that prices each manufacturing constraint in metres.