Risolutore di schizzi

Cosa fa il risolutore

Il risolutore di schizzi trasforma un insieme di punti, linee, cerchi e archi oltre a vincoli geometrici e dimensionali in coordinate concrete. Vive dentro packages/core/src/cad/sketch.ts (522 righe) e viene esportato da @cadcamfun/core come solveSketch, sketchProfiles e polygonArea. La cronologia parametrica risolve prima le sue espressioni in numeri, quindi richiama il risolutore; i profili risolti alimentano estrusioni, rivoluzioni e tasche.

Modello di dati

I punti sono le incognite. Ogni linea, cerchio e arco si riferisce a punti tramite id, quindi due linee che condividono un'estremità condividono il punto e si muovono insieme. Un cerchio aggiunge un'altra incognita, il suo raggio. Un arco è un centro e due punti sul cerchio, in senso antiorario start a end; il suo raggio è |inizio − centro| e il risolutore aggiunge la propria equazione mantenendo end sullo stesso cerchio.

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>
}

Il vettore sconosciuto è disposto come ogni punto x, y in ordine di entità, quindi quello di ogni cerchio r. Un rettangolo di quattro punti ha 8 incognite; aggiungi un cerchio con il proprio centro e ha 11.

Catalogo dei vincoli

Ogni vincolo contribuisce con equazioni residue che sono zero quando vale. Un vincolo può portare un id; senza uno viene nominato type#index (per esempio vertical#2) nelle relazioni sui conflitti.

Risoluzione: Levenberg-Marquardt

Il risolutore minimizza la somma dei residui quadrati con Levenberg–Marquardt e uno Jacobiano della differenza centrale. Ogni passaggio risolve le equazioni normali smorzate mediante la fattorizzazione di Cholesky; un gradino che abbassa il residuo viene accettato e lo smorzamento diminuisce, un gradino che non abbassa il residuo viene rifiutato e lo smorzamento cresce. Poiché ogni passaggio rappresenta la modifica più piccola che riduce i residui, un punto trascinato trascina il resto dello schizzo come farebbe su un tavolo da disegno.

1. Costruisci la funzione residua di ogni vincolo e registra quale vincolo possiede ciascuna equazione.
2. Start with λ = 1e-3. Solve (JᵀJ + λ·max(1, diag)) Δx = −Jᵀr; if Cholesky fails, multiply λ by 10 and retry.
3. Accept the step if the residual norm drops (λ = max(λ/5, 1e-12)); otherwise λ ×= 10.
4. Fermarsi quando il residuo è inferiore tolerance (1e-9) o dopo maxIterations (200).
5. 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).

Stato e diagnosi

Dopo la soluzione, gradi di libertà = incognite − rango ed equazioni ridondanti = equazioni − rango. Lo stato deriva da questi due numeri e dal fatto che il residuo abbia raggiunto 1e-6.

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"}

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 1000

Dallo schizzo ai profili

Lo slot sopra risolto come over-constrained con gdl 0 e 1 equazione ridondante: creazione top orizzontale è implicito quando c1–a1 e c2–b1 sono verticali e c1, c2 condividono a y. La soluzione riesce ancora; lo stato contrassegna solo il duplicato.

Risoluzione dei problemi