Solveur d'esquisse

Ce que fait le solveur

Le solveur d'esquisse transforme un ensemble de points, de lignes, de cercles et d'arcs ainsi que des contraintes géométriques et dimensionnelles en coordonnées concrètes. Il vit dans packages/core/src/cad/sketch.ts (522 lignes) et est exporté depuis @cadcamfun/core comme solveSketch, sketchProfiles et polygonArea. L'historique paramétrique résout d'abord ses expressions en nombres, puis appelle le solveur ; les profils résolus alimentent les extrusions, les révolutions et les poches.

Modèle de données

Les points sont les inconnues. Chaque ligne, cercle et arc fait référence à des points par identifiant, donc deux lignes qui partagent une extrémité partagent le point et se déplacent ensemble. Un cercle ajoute une inconnue supplémentaire, son rayon. Un arc est un centre et deux points sur le cercle, dans le sens inverse des aiguilles d'une montre à partir de start à end; son rayon est |start − centre| et le solveur ajoute sa propre équation en gardant end sur le même cercle.

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

Le vecteur inconnu est présenté comme celui de chaque point x, y dans l'ordre des entités, alors chaque cercle r. Un rectangle de quatre points a 8 inconnues ; ajoutez un cercle avec son propre centre et il a 11.

Catalogue de contraintes

Chaque contrainte apporte des équations résiduelles qui sont nulles lorsqu'elle est vérifiée. Une contrainte peut porter un id; sans un, il s'appelle type#index (par exemple vertical#2) dans les rapports de conflits.

Résolution : Levenberg – Marquardt

Le solveur minimise la somme des carrés des résidus avec Levenberg – Marquardt et un Jacobien de différence centrale. Chaque étape résout les équations normales amorties par factorisation de Cholesky ; un pas qui abaisse le résidu est accepté et l'amortissement diminue, un pas qui ne diminue pas est rejeté et l'amortissement augmente. Chaque étape étant le plus petit changement réduisant les résidus, un point déplacé entraîne le reste de l'esquisse comme il le ferait sur une planche à dessin.

1. Construisez la fonction résiduelle de chaque contrainte et enregistrez quelle contrainte possède chaque équation.
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. Arrêtez-vous lorsque le résidu est inférieur tolerance (1e-9) ou après 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).

Statut et diagnostic

Après résolution, degrés de liberté = inconnues − rang et équations redondantes = équations − rang. Le statut découle de ces deux nombres et du fait que le résidu ait atteint 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

De l'esquisse aux profils

L'emplacement ci-dessus résolu comme over-constrained avec ddl 0 et 1 équation redondante : faire top horizontal est implicite une fois que c1–a1 et c2–b1 sont verticaux et c1, c2 partagent un y. La résolution réussit toujours ; le statut signale uniquement le doublon.

Dépannage