Skizzenlöser

Was der Löser tut

Der Skizzenlöser wandelt eine Reihe von Punkten, Linien, Kreisen und Bögen sowie geometrischen und dimensionalen Einschränkungen in konkrete Koordinaten um. Es lebt darin packages/core/src/cad/sketch.ts (522 Zeilen) und wird aus exportiert @cadcamfun/core als solveSketch, sketchProfiles und polygonArea. Der parametrische Verlauf löst seine Ausdrücke zunächst in Zahlen auf und ruft dann den Löser auf; Die gelösten Profile versorgen Extrudate, Rotationen und Taschen.

Datenmodell

Punkte sind die Unbekannten. Jede Linie, jeder Kreis und jeder Bogen bezieht sich anhand der ID auf Punkte, d. h. zwei Linien, die ein gemeinsames Ende haben, teilen sich den Punkt und bewegen sich gemeinsam. Ein Kreis fügt eine weitere Unbekannte hinzu, seinen Radius. Ein Bogen besteht aus einem Mittelpunkt und zwei Punkten auf dem Kreis, die gegen den Uhrzeigersinn verlaufen start bis end; sein Radius ist |start − centre| und der Löser fügt seine eigene Gleichungsführung hinzu end auf demselben Kreis.

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

Der unbekannte Vektor wird als jeder Punkt dargestellt x, y in der Reihenfolge der Entitäten, dann die jedes Kreises r. Ein Rechteck aus vier Punkten hat 8 Unbekannte; Füge einen Kreis mit eigenem Mittelpunkt hinzu und er hat 11.

Einschränkungskatalog

Jede Einschränkung trägt zu Restgleichungen bei, die Null sind, wenn sie gilt. Eine Einschränkung kann eine tragen id; ohne eins wird es benannt type#index (zum Beispiel vertical#2) in Konfliktberichten.

Lösung: Levenberg–Marquardt

Der Löser minimiert die Summe der quadrierten Residuen mit Levenberg-Marquardt und einer zentralen Differenz-Jacobian-Methode. Jeder Schritt löst die gedämpften Normalgleichungen durch Cholesky-Faktorisierung; Ein Schritt, der den Rest verringert, wird akzeptiert und die Dämpfung sinkt, ein Schritt, der dies nicht tut, wird abgelehnt und die Dämpfung nimmt zu. Da es sich bei jedem Schritt um die kleinste Änderung handelt, die die Reste reduziert, zieht ein gezogener Punkt den Rest der Skizze auf die gleiche Weise wie auf einem Zeichenbrett.

1. Erstellen Sie die Restfunktion jeder Einschränkung und notieren Sie, welche Einschränkung jede Gleichung besitzt.
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. Stoppen Sie, wenn der Restwert darunter liegt tolerance (1e-9) oder danach 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).

Status und Diagnose

Nach der Lösung sind Freiheitsgrade = Unbekannte − Rang und redundante Gleichungen = Gleichungen − Rang. Der Status ergibt sich aus diesen beiden Zahlen und daraus, ob das Residuum 1e-6 erreicht hat.

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

Von der Skizze bis zum Profil

Der obige Slot wurde als gelöst over-constrained mit dof 0 und 1 redundante Gleichung: Erstellen top horizontal wird impliziert, sobald c1–a1 und c2–b1 vertikal sind und c1, c2 ein gemeinsames Y haben. Die Lösung gelingt immer noch; Der Status kennzeichnet nur das Duplikat.

Fehlerbehebung