Решатель эскизов

Что делает решатель

Решатель эскизов преобразует набор точек, линий, окружностей и дуг, а также геометрические и размерные ограничения в конкретные координаты. Оно живет в packages/core/src/cad/sketch.ts (строки 522) и экспортируется из @cadcamfun/core как solveSketch, sketchProfiles и polygonArea. Параметрическая история сначала преобразует свои выражения в числа, а затем вызывает решатель; решенные профили подачи выдавливают, вращают и делают карманы.

Модель данных

Точки – это неизвестные. Каждая линия, круг и дуга относятся к точкам по идентификатору, поэтому две линии, имеющие общий конец, разделяют точку и движутся вместе. К окружности добавляется еще одно неизвестное — ее радиус. Дуга — это центр и две точки окружности, направленные против часовой стрелки от start до end; его радиус |start − center| и решатель добавляет свое собственное уравнение, сохраняя end в том же кругу.

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

Неизвестный вектор представлен как координаты каждой точки. x, y в порядке объектов, затем каждый круг r. Прямоугольник из четырех точек имеет 8 неизвестных; добавьте круг со своим центром, и у него будет 11.

Каталог ограничений

Каждое ограничение вносит вклад в остаточные уравнения, которые равны нулю, когда оно выполняется. Ограничение может нести id; без него это называется type#index (например vertical#2) в отчетах о конфликтах.

Решение: Левенберг – Марквардт.

Решатель минимизирует сумму квадратов остатков с помощью Левенберга – Марквардта и якобиана центральной разности. На каждом этапе затухающие нормальные уравнения решаются с помощью факторизации Холецкого; шаг, снижающий невязку, принимается, и затухание падает, шаг, который не уменьшается, отклоняется, и затухание растет. Поскольку каждый шаг представляет собой наименьшее изменение, уменьшающее остатки, перетаскиваемая точка перетаскивает остальную часть эскиза так, как это было бы на чертежной доске.

1. Постройте функцию невязки каждого ограничения и запишите, какому ограничению принадлежит каждое уравнение.
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. Остановитесь, когда остаток станет ниже tolerance (1e-9) или после 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).

Статус и диагноз

После решения степени свободы = неизвестные — ранг и избыточные уравнения = уравнения — ранг. Статус следует из этих двух чисел и от того, достиг ли остаток 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

От эскиза к профилям

Слот выше решен как over-constrained с dof 0 и 1 избыточным уравнением: создание top горизонтальный подразумевается, если c1–a1 и c2–b1 вертикальны и c1, c2 имеют общий y. Решение все еще удается; статус только отмечает дубликат.

Поиск неисправностей