Documentation
Sketch solver
Constrained 2D sketches solved by Levenberg–Marquardt, with degrees of freedom, free points and named conflicts.
What the solver does
The sketch solver turns a set of points, lines, circles and arcs plus geometric and dimensional constraints into concrete coordinates. It lives in packages/core/src/cad/sketch.ts (522 lines) and is exported from @cadcamfun/core as solveSketch, sketchProfiles and polygonArea. The parametric history resolves its expressions to numbers first, then calls the solver; the solved profiles feed extrudes, revolves and pockets.
| Input | Output |
|---|---|
| entities: points, lines, circles, arcs | the same entities with solved coordinates and radii |
| constraints: 24 kinds, optionally named | status, degrees of freedom, free points, redundant equations, conflicts |
| options: maxIterations (200), tolerance (1e-9) | iterations used and the largest residual left |
Data model
Points are the unknowns. Every line, circle and arc refers to points by id, so two lines that share an end share the point and move together. A circle adds one more unknown, its radius. An arc is a centre and two points on the circle, counter-clockwise from start to end; its radius is |start − centre| and the solver adds its own equation keeping end on the same circle.
export interface SketchPoint { id: string; kind: "point"; x: number; y: number }
export interface SketchLine { id: string; kind: "line"; p1: PointId; p2: PointId }
export interface SketchCircle { id: string; kind: "circle"; center: PointId; radius: number }
/** Counter-clockwise from `start` to `end` about `center`. */
export interface SketchArc { id: string; kind: "arc"; center: PointId; start: PointId; end: PointId }
export interface Sketch {
readonly entities: ReadonlyArray<SketchEntity>
readonly constraints: ReadonlyArray<Constraint>
}The unknown vector is laid out as every point's x, y in entity order, then every circle's r. A rectangle of four points has 8 unknowns; add a circle with its own centre and it has 11.
Constraint catalogue
Each constraint contributes residual equations that are zero when it holds. A constraint can carry an id; without one it is named type#index (for example vertical#2) in conflict reports.
| Type | Fields | Meaning | Equations |
|---|---|---|---|
fixed | point, x?, y? | pins a point (either coordinate optional) | 1–2 |
coincident | a, b | two points are one | 2 |
horizontal / vertical | line | a line is level or plumb | 1 |
horizontalPoints / verticalPoints | a, b | two points share y / x | 1 |
distance | a, b, value | point-to-point distance | 1 |
distanceX / distanceY | a, b, value | signed offset along one axis | 1 |
length | line, value | line length | 1 |
parallel / perpendicular | a, b | between two lines | 1 |
equalLength | a, b | two lines | 1 |
equalRadius | a, b | two circles or arcs | 1 |
radius / diameter | circle, value | size of a circle or arc | 1 |
angle | a, b, value | from line a to line b, counter-clockwise, radians | 1 |
pointOnLine / pointOnCircle | point, line | circle | incidence | 1 |
midpoint | point, line | point at the middle of a line | 2 |
symmetric | a, b, line | mirror pair about a line | 2 |
tangentLineCircle | line, circle | line touches circle | 1 |
tangentCircles | a, b, internal? | external r1 + r2 or internal |r1 − r2| | 1 |
concentric | a, b | centres coincide | 2 |
Solving: Levenberg–Marquardt
The solver minimises the sum of squared residuals with Levenberg–Marquardt and a central-difference Jacobian. Each step solves the damped normal equations by Cholesky factorisation; a step that lowers the residual is accepted and the damping drops, a step that does not is rejected and the damping grows. Because every step is the smallest change that reduces the residuals, a dragged point drags the rest of the sketch the way it would on a drawing board.
- Build the residual function of every constraint, and record which constraint owns each equation.
- Start with λ = 1e-3. Solve (JᵀJ + λ·max(1, diag)) Δx = −Jᵀr; if Cholesky fails, multiply λ by 10 and retry.
- Accept the step if the residual norm drops (λ = max(λ/5, 1e-12)); otherwise λ ×= 10.
- Stop when the residual is below
tolerance(1e-9) or aftermaxIterations(200). - Analyse the Jacobian at the solution: rank by Gaussian elimination with full pivoting (tolerance 1e-7), null-space basis, free unknowns (component above 1e-6).
| Constant | Value | Where |
|---|---|---|
| maxIterations default | 200 | SolveOptions |
| tolerance default | 1e-9 | SolveOptions |
| initial damping λ | 1e-3 | solveSketch |
| damping floor | 1e-12 | solveSketch |
| solved if residual ≤ | 1e-6 | status |
| rank tolerance | 1e-7 | nullSpace |
| free-unknown threshold | 1e-6 | free points |
| conflict threshold (per equation) | 1e-6 | conflicts |
Status and diagnosis
After solving, degrees of freedom = unknowns − rank and redundant equations = equations − rank. The status follows from those two numbers and from whether the residual reached 1e-6.
| Status | Condition | What to do |
|---|---|---|
fully-constrained | solved, dof 0, no redundancy | nothing |
under-constrained | solved, dof > 0 | add dimensions for the ids in free |
over-constrained | solved, redundant > 0 | remove a duplicate constraint (harmless but noisy) |
conflicting | not solved, redundant > 0 | fix the constraint in conflicts[0] |
failed | not solved, no redundancy | start nearer the intended shape or raise maxIterations |
These results come from running the solver on a rectangle drawn slightly askew: a(0,0) b(38,2) c(41,27) d(−1,24), with a fixed at the origin and the four lines horizontal/vertical.
// + length(l1) = 40
{"status":"under-constrained","dof":1,"free":["c","d"],"iterations":3,"redundant":0}
// + length(l2) = 25
{"status":"fully-constrained","dof":0,"iterations":3,"residual":7.95e-12,
"points":[["a",0,0],["b",40,0],["c",40,25],["d",0,25]]}
// + length(l3) = 40 (implied by the others)
{"status":"over-constrained","dof":0,"redundant":1}
// + length(l3) = 30 named "bad"
{"status":"conflicting","redundant":1,
"conflicts":["bad","vertical#2","length#5","vertical#4"],
"message":"The constraints cannot all hold; the worst miss is bad"}Least change, not least surprise
With height still free, moving c to (55, 31) and solving gave c = (40, 27.5) and d = (0, 27.5): the free height settled at the mean of the dragged c.y (31) and the old d.y (24), because Levenberg–Marquardt makes the smallest change that satisfies the constraints.
API
export const solveSketch: (sketch: Sketch, options?: SolveOptions) => SolveResult
export const sketchProfiles: (sketch: Sketch, tolerance?: number /* 0.01 */) =>
{ readonly loops: Vec2[][]; readonly open: Vec2[][] }
export const polygonArea: (ring: ReadonlyArray<Vec2>) => number // positive counter-clockwise
export class SketchError extends Error {}
export interface SolveResult {
sketch: Sketch; status: SolveStatus; dof: number; iterations: number
residual: number // largest absolute residual left
free: string[] // points and circles that can still move
conflicts: string[] // worst first, only when not solved
redundant: number
message?: string
}import { solveSketch, sketchProfiles, polygonArea } from "@cadcamfun/core"
const P = (id: string, x: number, y: number) => ({ id, kind: "point" as const, x, y })
const L = (id: string, p1: string, p2: string) => ({ id, kind: "line" as const, p1, p2 })
const result = solveSketch({
entities: [P("a", 0, 0), P("b", 38, 2), P("c", 41, 27), P("d", -1, 24),
L("l1", "a", "b"), L("l2", "b", "c"), L("l3", "c", "d"), L("l4", "d", "a"),
P("o", 20, 12), { id: "h", kind: "circle", center: "o", radius: 4 }],
constraints: [
{ type: "fixed", point: "a", x: 0, y: 0 },
{ type: "horizontal", line: "l1" }, { type: "vertical", line: "l2" },
{ type: "horizontal", line: "l3" }, { type: "vertical", line: "l4" },
{ type: "length", line: "l1", value: 40 }, { type: "length", line: "l2", value: 25 },
{ type: "distanceX", a: "a", b: "o", value: 20 }, { type: "distanceY", a: "a", b: "o", value: 12.5 },
{ type: "diameter", circle: "h", value: 10 },
],
})
result.status // "fully-constrained", dof 0
const { loops } = sketchProfiles(result.sketch)
loops.map((l) => [l.length, polygonArea(l)])
// [[50, 78.333], [4, 1000]] circle: 50 points; rectangle: 4 points, area 1000From sketch to profiles
sketchProfiles chains lines and arcs end to end through their shared point ids into closed loops, and returns every circle as a loop of its own. An arc becomes points spaced so the chord stays within tolerance of the true arc (n = ⌈sweep / (2·acos(1 − tol/r))⌉, at least 2); a full circle gets at least 8 points. A chain that does not close is returned in open instead of being dropped.
The slot above solved as over-constrained with dof 0 and 1 redundant equation: making top horizontal is implied once c1–a1 and c2–b1 are vertical and c1, c2 share a y. The solve still succeeds; the status only flags the duplicate.
Troubleshooting
| Symptom | Cause | Fix |
|---|---|---|
SketchError: Duplicate entity id | two entities share an id | ids are unique across points, lines, circles and arcs |
SketchError: Unknown unknown | a constraint names a point or circle that is not there | check the ids in the constraint |
conflicting with a long conflicts list | one wrong dimension pulls several equations off zero | fix the first entry; the rest are usually collateral |
failed | the start is far from any solution | draw closer to the intended shape; raise maxIterations |
profile missing from loops | a chain does not close: it is in open | make end points shared ids, or add a coincident constraint |
| circle has too few points | tolerance too coarse for a small radius | pass a smaller tolerance to sketchProfiles |