components/system-map/system-map-circles-search.ts

Functions

Imports

It imports components/system-map/system-map-inside.ts. Imported by components/system-map/system-map-circles.ts.

Source

1// How a system's circle is searched for (system-map-circles.ts): the drawing's units, the box
2// and text estimates, the segment tests the search scores with, the rim, the cost of a drawing,
3// the first places and the bent wires. layoutAt in system-map-circles.ts runs the search.
4
5import { type Rect, hitsRect } from "./system-map-inside.ts";
6
7/**
8 * A box in the drawing: a part inside the circle, or on the rim what is outside it or another system.
9 */
10export interface CircleNode {
11  id: string;
12  role: "part" | "outside" | "system";
13  name: string;
14  lines: string[];
15  sub: string;
16  w: number;
17  h: number;
18  store?: boolean;
19  private?: boolean;
20  x: number;
21  y: number;
22}
23
24/** A wire: node indices, CIRCLE for the circle itself. */
25export interface CircleWire {
26  a: number;
27  b: number;
28  from: string;
29  to: string;
30  loose: boolean;
31}
32
33/** A wire's shape: its end points, the points along it, its path, and how far it bows. */
34export interface WireShape {
35  seg: number[];
36  pts: number[][];
37  d: string;
38  bow: number;
39}
40
41/** The circle's own end of a line between two systems as wholes. */
42export const CIRCLE = -1;
43
44// Sizes, in the shell's drawing units (a 390 px phone draws a unit at about 0.94 px).
45export const NAME_SIZE = 11.5;
46export const KIND_SIZE = 9;
47export const RIM_SIZE = 11;
48export const LINE_H = 13;
49export const BOX_PAD_X = 8;
50/** A part's name wider than this wraps onto a second line, at a hyphen or a space. */
51const MAX_LINE = 96;
52export const MIN_BOX_W = 58;
53export const RIM_H = 24;
54export const RIM_PAD_X = 10;
55export const MARGIN = 12;
56/** Every rim box keeps this far outside the circle, and every part this far inside it. */
57const RIM_GAP = 12;
58const IN_PAD = 10;
59/** Two boxes keep this far apart. */
60const BOX_GAP = 10;
61/** Between rows of the rim. */
62const ROW_GAP = 8;
63/** A wire keeps this far from every box but its two ends. */
64const CLEAR = 5;
65export const GRID = 10;
66/** The name at the circle's foot. */
67export const LABEL_SIZE = 10;
68export const LABEL_FOOT = 14;
69
70// What a drawing costs. A fault costs more than any drawing without one, so a fault is kept only
71// when every placement tried has one.
72export const OVERLAP = 1e6;
73const UNDER_BOX = 1e5;
74export const CROSSING = 1e4;
75const FAN = 600;
76const MIN_FAN_DEG = 16;
77/** A part with nothing pulling it drifts to the middle: this much per unit from the centre. */
78const CENTRE_PULL = 0.4;
79/** The share of the circle's area its boxes and their gaps take, at most. */
80const FILL = 0.45;
81/** How many moves the annealing tries on a drawing with a fault. */
82export const ANNEAL_STEPS = 12000;
83/** How many seeds the search runs from, at most. */
84export const SEEDS = 3;
85/** The bends a wire may take: its control point this share of its length to one side. */
86const CURVE_STEPS = 10;
87/** A curve's control point sits at most this share of the wire's length from its middle: gently curved. */
88const MAX_BOW = 0.55;
89
90/** Every number the search is drawn from, so a saved circle is searched again once one changes. */
91export const SEARCH_NUMBERS = [NAME_SIZE, KIND_SIZE, RIM_SIZE, LINE_H, BOX_PAD_X, MAX_LINE, MIN_BOX_W, RIM_H, RIM_PAD_X, MARGIN, RIM_GAP, IN_PAD, BOX_GAP, ROW_GAP, CLEAR, GRID, LABEL_SIZE, LABEL_FOOT, OVERLAP, UNDER_BOX, CROSSING, FAN, MIN_FAN_DEG, CENTRE_PULL, FILL, ANNEAL_STEPS, SEEDS, CURVE_STEPS, MAX_BOW];
92
93export const f1 = (n: number) => Math.round(n * 10) / 10;
94
95/**
96 * A text's width, estimated from its letters: the drawing is made at build time, with no font to
97 * measure, so each class of letter gets its share of an em, a little over the UI face's, so a box
98 * is never too narrow.
99 */
100export function textWidth(s: string, size: number): number {
101  let em = 0;
102  for (const ch of s) {
103    if (/[iljtfr.,:;'|!\s]/.test(ch)) em += 0.33;
104    else if (/[-_()]/.test(ch)) em += 0.4;
105    else if (/[mwMW]/.test(ch)) em += 0.88;
106    else if (/[A-Z]/.test(ch)) em += 0.7;
107    else if (/[0-9]/.test(ch)) em += 0.6;
108    else em += 0.58;
109  }
110  return em * size;
111}
112
113/**
114 * A part's name in one line, or two when it is wider than MAX_LINE: broken after a hyphen or at a
115 * space, where the longer line is shortest.
116 */
117export function wrapName(name: string): string[] {
118  if (textWidth(name, NAME_SIZE) <= MAX_LINE) return [name];
119  let best = [name];
120  let widest = Number.POSITIVE_INFINITY;
121  for (let i = 1; i < name.length - 1; i++) {
122    const ch = name[i];
123    if (ch !== "-" && ch !== " " && ch !== "_") continue;
124    const lines = ch === " " ? [name.slice(0, i), name.slice(i + 1)] : [name.slice(0, i + 1), name.slice(i + 1)];
125    const w = Math.max(...lines.map((l) => textWidth(l, NAME_SIZE)));
126    if (w < widest) {
127      widest = w;
128      best = lines;
129    }
130  }
131  return best;
132}
133
134// ---------------------------------------------------------------------------------------
135// Geometry.
136
137export const rectOf = (n: CircleNode): Rect => ({ x: n.x - n.w / 2, y: n.y - n.h / 2, w: n.w, h: n.h });
138const grow = (r: Rect, g: number): Rect => ({ x: r.x - g, y: r.y - g, w: r.w + 2 * g, h: r.h + 2 * g });
139
140/** Whether segment s ([px, py, qx, qy]) passes through a box grown by g, from the box's own numbers. */
141function hitsBox(s: readonly number[], n: CircleNode, g: number): boolean {
142  const x0 = n.x - n.w / 2 - g;
143  const x1 = n.x + n.w / 2 + g;
144  const y0 = n.y - n.h / 2 - g;
145  const y1 = n.y + n.h / 2 + g;
146  const [px, py, qx, qy] = s as [number, number, number, number];
147  // Both ends on one side of the box: no hit.
148  if ((px <= x0 && qx <= x0) || (px >= x1 && qx >= x1) || (py <= y0 && qy <= y0) || (py >= y1 && qy >= y1)) return false;
149  return hitsRect(px, py, qx, qy, { x: x0, y: y0, w: x1 - x0, h: y1 - y0 });
150}
151
152/** Whether segments s and t, each [ax, ay, bx, by], cross at a point inside both. */
153export function segmentsCross(s: readonly number[], t: readonly number[]): boolean {
154  const [s0, s1, s2, s3] = s as [number, number, number, number];
155  const [t0, t1, t2, t3] = t as [number, number, number, number];
156  if (Math.max(s0, s2) < Math.min(t0, t2) || Math.max(t0, t2) < Math.min(s0, s2) || Math.max(s1, s3) < Math.min(t1, t3) || Math.max(t1, t3) < Math.min(s1, s3)) return false;
157  const rx = s2 - s0;
158  const ry = s3 - s1;
159  const sx = t2 - t0;
160  const sy = t3 - t1;
161  const den = rx * sy - ry * sx;
162  if (Math.abs(den) < 1e-9) return false;
163  const u = ((t0 - s0) * sy - (t1 - s1) * sx) / den;
164  const v = ((t0 - s0) * ry - (t1 - s1) * rx) / den;
165  return u > 1e-6 && u < 1 - 1e-6 && v > 1e-6 && v < 1 - 1e-6;
166}
167
168/** Where the line from a box's centre toward a point leaves the box. */
169function exitPoint(n: CircleNode, tx: number, ty: number): [number, number] {
170  const dx = tx - n.x;
171  const dy = ty - n.y;
172  const t = Math.min(dx ? n.w / 2 / Math.abs(dx) : Number.POSITIVE_INFINITY, dy ? n.h / 2 / Math.abs(dy) : Number.POSITIVE_INFINITY);
173  return t >= 1 ? [n.x, n.y] : [n.x + dx * t, n.y + dy * t];
174}
175
176/**
177 * A wire's segment, from edge to edge: between two boxes along the line joining their centres;
178 * from the circle, at the point facing the box.
179 */
180function segmentOf(w: CircleWire, nodes: readonly CircleNode[], r: number): number[] {
181  const b = nodes[w.b]!;
182  if (w.a === CIRCLE) {
183    const d = Math.hypot(b.x, b.y) || 1;
184    const [qx, qy] = exitPoint(b, 0, 0);
185    return [(b.x / d) * r, (b.y / d) * r, qx, qy];
186  }
187  const a = nodes[w.a]!;
188  const [px, py] = exitPoint(a, b.x, b.y);
189  const [qx, qy] = exitPoint(b, a.x, a.y);
190  return [px, py, qx, qy];
191}
192
193/** A small deterministic generator, so the same data always draws the same way. */
194export function random(seed: number): () => number {
195  let s = seed >>> 0;
196  return () => {
197    s = (s + 0x6d2b79f5) >>> 0;
198    let t = s;
199    t = Math.imul(t ^ (t >>> 15), t | 1);
200    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
201    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
202  };
203}
204
205// ---------------------------------------------------------------------------------------
206// The rim.
207
208/**
209 * Places one half of the rim, left to right, hugging the circle: spread over the half's arc, kept
210 * apart, inside the drawing's width, as close to the circle as each box's width allows. A half too
211 * full for one row takes two, alternating, so each line to the outer row has a gap in the inner
212 * one to pass through. `sign` is -1 above the circle, 1 below.
213 */
214function placeHalf(row: CircleNode[], r: number, halfW: number, sign: 1 | -1): void {
215  const n = row.length;
216  if (!n) return;
217  const at = (i: number) => row[i]!;
218  const avail = 2 * (halfW - MARGIN);
219  const rows = row.reduce((s, b) => s + b.w, 0) + (n - 1) * BOX_GAP <= avail ? 1 : 2;
220  const reach = r + RIM_GAP + 30;
221  const xs = row.map((_, i) => -reach * Math.cos((Math.PI * (i + 0.5)) / n));
222  const x = (i: number) => xs[i]!;
223  const sameRow = (i: number, j: number) => rows === 1 || i % 2 === j % 2;
224  // Apart, left to right; then back inside the right edge, right to left; then inside the left edge.
225  const apart = () => {
226    for (let i = 1; i < n; i++) {
227      for (let j = i - 1; j >= 0 && j >= i - 2; j--) {
228        if (sameRow(i, j)) xs[i] = Math.max(x(i), x(j) + (at(i).w + at(j).w) / 2 + BOX_GAP);
229      }
230    }
231  };
232  apart();
233  const right = halfW - MARGIN;
234  for (let i = n - 1; i >= 0; i--) {
235    xs[i] = Math.min(x(i), right - at(i).w / 2);
236    for (let j = i + 1; j < n && j <= i + 2; j++) {
237      if (sameRow(i, j)) xs[i] = Math.min(x(i), x(j) - (at(i).w + at(j).w) / 2 - BOX_GAP);
238    }
239  }
240  for (let i = 0; i < n; i++) xs[i] = Math.max(x(i), -right + at(i).w / 2);
241  apart();
242  /** How far from the centre line a box at x must sit to keep `d` from the circle's centre. */
243  const hug = (px: number, b: CircleNode, d: number) => {
244    const nx = Math.max(0, Math.abs(px) - b.w / 2);
245    return (nx >= d ? 0 : Math.sqrt(d * d - nx * nx)) + b.h / 2;
246  };
247  const ys = row.map((b, i) => Math.max(b.h / 2 + 4, hug(x(i), b, r + RIM_GAP)));
248  if (rows === 2) {
249    for (let i = 1; i < n; i += 2) {
250      let y = Math.max(ys[i]!, hug(x(i), at(i), r + RIM_GAP + RIM_H + ROW_GAP));
251      for (let j = 0; j < n; j += 2) {
252        if (Math.abs(x(i) - x(j)) < (at(i).w + at(j).w) / 2 + 4) y = Math.max(y, ys[j]! + (at(i).h + at(j).h) / 2 + ROW_GAP);
253      }
254      ys[i] = y;
255    }
256  }
257  row.forEach((b, i) => {
258    b.x = f1(x(i));
259    b.y = f1(sign * ys[i]!);
260  });
261}
262
263/**
264 * The rim in its order: the first `top` of `seq` above the circle, left to right, the rest below
265 * it, right to left, so the order runs once round the circle clockwise.
266 */
267export function placeRim(nodes: CircleNode[], seq: readonly number[], top: number, r: number, halfW: number): void {
268  placeHalf(
269    seq.slice(0, top).map((i) => nodes[i]!),
270    r,
271    halfW,
272    -1,
273  );
274  placeHalf(
275    seq
276      .slice(top)
277      .reverse()
278      .map((i) => nodes[i]!),
279    r,
280    halfW,
281    1,
282  );
283}
284
285// ---------------------------------------------------------------------------------------
286// The cost of a drawing.
287
288const shares = (u: CircleWire, v: CircleWire) => u.a === v.a || u.a === v.b || u.b === v.a || u.b === v.b;
289
290export function coster(nodes: CircleNode[], wires: readonly CircleWire[], r: number, label: Rect | null) {
291  const n = nodes.length;
292  /** Each node's wires. */
293  const incident: number[][] = nodes.map(() => []);
294  wires.forEach((w, k) => {
295    if (w.a !== CIRCLE) incident[w.a]!.push(k);
296    incident[w.b]!.push(k);
297  });
298  const segs: number[][] = wires.map((w) => segmentOf(w, nodes, r));
299  const zone = label ? grow(label, 3) : null;
300
301  /** Two boxes too close. */
302  const overlap = (i: number, j: number) => {
303    const a = nodes[i]!;
304    const b = nodes[j]!;
305    return Math.abs(a.x - b.x) < (a.w + b.w) / 2 + BOX_GAP && Math.abs(a.y - b.y) < (a.h + b.h) / 2 + BOX_GAP / 2 ? OVERLAP : 0;
306  };
307  /** A wire's own cost: its length, and every box or the name it runs under. */
308  const own = (k: number) => {
309    const w = wires[k]!;
310    const s = segs[k]!;
311    let c = Math.hypot(s[2]! - s[0]!, s[3]! - s[1]!);
312    for (let m = 0; m < n; m++) {
313      if (m === w.a || m === w.b) continue;
314      if (hitsBox(s, nodes[m]!, CLEAR)) c += UNDER_BOX;
315    }
316    if (zone && hitsRect(s[0]!, s[1]!, s[2]!, s[3]!, zone)) c += UNDER_BOX;
317    return c;
318  };
319  /** Two wires that cross, or leave one box so close together they read as one. */
320  const pair = (k: number, o: number) => {
321    const u = wires[k]!;
322    const v = wires[o]!;
323    if (!shares(u, v)) return segmentsCross(segs[k]!, segs[o]!) ? CROSSING : 0;
324    // From the box they share, the angle between them.
325    const at = u.a === v.a || u.a === v.b ? u.a : u.b;
326    if (at === CIRCLE) return 0;
327    const far = (w: CircleWire, s: number[]) => (w.a === at ? [s[2]!, s[3]!] : [s[0]!, s[1]!]) as [number, number];
328    const [ux, uy] = far(u, segs[k]!);
329    const [vx, vy] = far(v, segs[o]!);
330    const c = nodes[at]!;
331    let ang = Math.abs(Math.atan2(uy - c.y, ux - c.x) - Math.atan2(vy - c.y, vx - c.x)) * (180 / Math.PI);
332    ang = Math.min(ang, 360 - ang);
333    return ang < MIN_FAN_DEG ? FAN : 0;
334  };
335  const pull = (i: number) => (nodes[i]!.role === "part" ? CENTRE_PULL * Math.hypot(nodes[i]!.x, nodes[i]!.y) : 0);
336  const total = () => {
337    let c = 0;
338    for (let i = 0; i < n; i++) c += pull(i);
339    for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) c += overlap(i, j);
340    for (let k = 0; k < wires.length; k++) {
341      c += own(k);
342      for (let o = k + 1; o < wires.length; o++) c += pair(k, o);
343    }
344    return c;
345  };
346  /** Everything a move of node i can change. */
347  const partial = (i: number) => {
348    let c = pull(i);
349    for (let j = 0; j < n; j++) if (j !== i) c += overlap(i, j);
350    const mine = incident[i]!;
351    const mineSet = new Set(mine);
352    for (const k of mine) {
353      c += own(k);
354      for (let o = 0; o < wires.length; o++) {
355        if (o === k || (mineSet.has(o) && o < k)) continue;
356        c += pair(k, o);
357      }
358    }
359    // Other wires running under this box.
360    for (let k = 0; k < wires.length; k++) {
361      if (mineSet.has(k)) continue;
362      if (hitsBox(segs[k]!, nodes[i]!, CLEAR)) c += UNDER_BOX;
363    }
364    return c;
365  };
366  const refresh = (i: number) => {
367    for (const k of incident[i]!) segs[k] = segmentOf(wires[k]!, nodes, r);
368  };
369  const refreshAll = () => {
370    for (let k = 0; k < wires.length; k++) segs[k] = segmentOf(wires[k]!, nodes, r);
371  };
372  return { total, partial, refresh, refreshAll, segs };
373}
374
375// ---------------------------------------------------------------------------------------
376// The search.
377
378/**
379 * The circle's radius for its parts: room for each box and its share of the gaps, at under half
380 * the circle's area. A circle too wide for the shell widens the drawing, which then draws a little
381 * smaller.
382 */
383export function radiusFor(parts: readonly CircleNode[]): number {
384  if (!parts.length) return 104;
385  const area = parts.reduce((s, b) => s + (b.w + BOX_GAP) * (b.h + BOX_GAP), 0);
386  return Math.max(parts.length > 2 ? 118 : 96, Math.sqrt(area / (FILL * Math.PI)) + IN_PAD);
387}
388
389/** Every place a part may sit: on the grid, wholly inside the circle and clear of its name. */
390export function slotsFor(b: CircleNode, r: number, label: Rect | null): Array<[number, number]> {
391  const out: Array<[number, number]> = [];
392  const lim = r - IN_PAD;
393  for (let y = -Math.floor(lim / GRID) * GRID; y <= lim; y += GRID) {
394    for (let x = -Math.floor(lim / GRID) * GRID; x <= lim; x += GRID) {
395      const hx = Math.abs(x) + b.w / 2;
396      const hy = Math.abs(y) + b.h / 2;
397      if (hx * hx + hy * hy > lim * lim) continue;
398      if (label && Math.abs(x - (label.x + label.w / 2)) < (b.w + label.w) / 2 + 4 && Math.abs(y - (label.y + label.h / 2)) < (b.h + label.h) / 2 + 4) continue;
399      out.push([x, y]);
400    }
401  }
402  return out;
403}
404
405/**
406 * The rim's first order: what wires to the same part side by side, the parts in the order the
407 * data gives them, then the systems reached only as wholes.
408 */
409export function firstOrder(nodes: readonly CircleNode[], wires: readonly CircleWire[], rim: readonly number[]): number[] {
410  const anchor = new Map(rim.map((i) => [i, Number.POSITIVE_INFINITY]));
411  for (const w of wires) {
412    for (const [me, other] of [
413      [w.a, w.b],
414      [w.b, w.a],
415    ] as const) {
416      if (anchor.has(me) && other !== CIRCLE && nodes[other]!.role === "part") anchor.set(me, Math.min(anchor.get(me)!, other));
417    }
418  }
419  return [...rim].sort((p, q) => anchor.get(p)! - anchor.get(q)! || p - q);
420}
421
422/**
423 * The parts' first places. The part most wires run to sits in the middle. Each other part with a
424 * wire to the rim sits toward what it wires to there; a part that wires only to the middle one (a
425 * store under its Worker) goes into the widest gap left between the middle one's spokes, so its own
426 * spoke is short and none passes it.
427 */
428export function firstPlaces(nodes: CircleNode[], wires: readonly CircleWire[], parts: readonly number[], slots: ReadonlyArray<ReadonlyArray<[number, number]>>, r: number, rand: () => number): void {
429  const near = (i: number) => wires.flatMap((w) => (w.a === i ? [w.b] : w.b === i ? [w.a] : [])).filter((o) => o !== CIRCLE);
430  const degree = new Map(parts.map((i) => [i, near(i).length]));
431  const order = [...parts].sort((p, q) => degree.get(q)! - degree.get(p)! || p - q);
432  const hub = order.length && degree.get(order[0]!)! >= 3 ? order[0]! : -1;
433  const leaf = (i: number) => near(i).every((o) => o === hub);
434  const placed = new Set<number>();
435  /** The angles already taken round the middle. */
436  const taken: number[] = hub >= 0 ? near(hub).filter((o) => nodes[o]!.role !== "part").map((o) => Math.atan2(nodes[o]!.y, nodes[o]!.x)) : [];
437  const put = (i: number, gx: number, gy: number) => {
438    const me = nodes[i]!;
439    const list = slots[parts.indexOf(i)]!;
440    let best: [number, number] | null = null;
441    let bestD = Number.POSITIVE_INFINITY;
442    for (const [x, y] of list) {
443      const clash = [...placed].some((j) => Math.abs(nodes[j]!.x - x) < (nodes[j]!.w + me.w) / 2 + BOX_GAP && Math.abs(nodes[j]!.y - y) < (nodes[j]!.h + me.h) / 2 + BOX_GAP / 2);
444      if (clash) continue;
445      const d = Math.hypot(x - gx, y - gy);
446      if (d < bestD) {
447        bestD = d;
448        best = [x, y];
449      }
450    }
451    const [x, y] = best ?? list[Math.floor(rand() * list.length)] ?? [0, 0];
452    me.x = x;
453    me.y = y;
454    placed.add(i);
455  };
456  if (hub >= 0) put(hub, 0, 0);
457  // Parts with wires of their own first, toward what they wire to; then the leaves, into the gaps.
458  const rest = order.filter((i) => i !== hub);
459  for (const i of [...rest.filter((i) => !leaf(i)), ...rest.filter(leaf)]) {
460    let ang: number;
461    if (!leaf(i)) {
462      let tx = 0;
463      let ty = 0;
464      for (const o of near(i)) {
465        if (o === hub || (nodes[o]!.role === "part" && !placed.has(o))) continue;
466        tx += nodes[o]!.x;
467        ty += nodes[o]!.y;
468      }
469      ang = tx || ty ? Math.atan2(ty, tx) : rand() * 2 * Math.PI;
470    } else if (taken.length) {
471      const sorted = [...taken].sort((p, q) => p - q);
472      let gap = -1;
473      ang = 0;
474      for (const [k, t] of sorted.entries()) {
475        const next = k + 1 < sorted.length ? sorted[k + 1]! : sorted[0]! + 2 * Math.PI;
476        if (next - t > gap) {
477          gap = next - t;
478          ang = t + gap / 2;
479        }
480      }
481    } else ang = rand() * 2 * Math.PI;
482    taken.push(Math.atan2(Math.sin(ang), Math.cos(ang)));
483    const reach = hub >= 0 ? 0.62 * r : 1000;
484    put(i, Math.cos(ang) * reach, Math.sin(ang) * reach);
485  }
486}
487
488/**
489 * A wire's shape: straight, or a quadratic curve through the control point, leaving each box
490 * toward it. As points along it, for the checks, and as a path.
491 */
492function shapeOf(w: CircleWire, nodes: readonly CircleNode[], r: number, control: [number, number] | null): { pts: number[][]; d: string; bow: number } {
493  if (w.a === CIRCLE || !control) {
494    const [ax, ay, bx, by] = segmentOf(w, nodes, r).map(f1) as [number, number, number, number];
495    return { pts: [[ax, ay], [bx, by]], d: `M${ax},${ay} L${bx},${by}`, bow: 0 };
496  }
497  const a = nodes[w.a]!;
498  const b = nodes[w.b]!;
499  const [cx, cy] = control;
500  const [px, py] = exitPoint(a, cx, cy);
501  const [qx, qy] = exitPoint(b, cx, cy);
502  const pts: number[][] = [];
503  for (let k = 0; k <= CURVE_STEPS; k++) {
504    const t = k / CURVE_STEPS;
505    const u = 1 - t;
506    pts.push([f1(u * u * px + 2 * u * t * cx + t * t * qx), f1(u * u * py + 2 * u * t * cy + t * t * qy)]);
507  }
508  const len = Math.hypot(b.x - a.x, b.y - a.y) || 1;
509  const bow = Math.hypot(cx - (a.x + b.x) / 2, cy - (a.y + b.y) / 2) / len;
510  return { pts, d: `M${f1(px)},${f1(py)} Q${f1(cx)},${f1(cy)} ${f1(qx)},${f1(qy)}`, bow };
511}
512
513/**
514 * Each wire straight where it can be, and gently curved where a straight line would run under a
515 * box or cross another wire: every wire with a fault tries curves through control points over the
516 * drawing, keeping the one with the fewest faults, then the least bowed. A wire between two parts
517 * stays inside the circle.
518 */
519export function bendWires(nodes: readonly CircleNode[], wires: readonly CircleWire[], r: number, label: Rect | null): WireShape[] {
520  const shapes = wires.map((w) => shapeOf(w, nodes, r, null));
521  const zone = label ? grow(label, 3) : null;
522  /** Faults, a box or the name ten times a crossing. */
523  const faults = (k: number, pts: readonly number[][]) => {
524    const w = wires[k]!;
525    let n = 0;
526    for (let s = 1; s < pts.length; s++) {
527      const seg = [...pts[s - 1]!, ...pts[s]!];
528      for (let m = 0; m < nodes.length; m++) if (m !== w.a && m !== w.b && hitsBox(seg, nodes[m]!, CLEAR)) n += 10;
529      if (zone && hitsRect(seg[0]!, seg[1]!, seg[2]!, seg[3]!, zone)) n += 10;
530      for (let o = 0; o < wires.length; o++) {
531        if (o === k || shares(w, wires[o]!)) continue;
532        const other = shapes[o]!.pts;
533        for (let t = 1; t < other.length; t++) if (segmentsCross(seg, [...other[t - 1]!, ...other[t]!])) n += 1;
534      }
535    }
536    return n;
537  };
538  const inside = (pts: readonly number[][]) => pts.every(([x, y]) => Math.hypot(x!, y!) <= r - 2);
539  for (let round = 0; round < 3; round++) {
540    let changed = false;
541    for (let k = 0; k < wires.length; k++) {
542      const w = wires[k]!;
543      if (w.a === CIRCLE) continue;
544      const now = faults(k, shapes[k]!.pts);
545      if (now === 0 && shapes[k]!.bow === 0) continue;
546      const a = nodes[w.a]!;
547      const b = nodes[w.b]!;
548      const len = Math.hypot(b.x - a.x, b.y - a.y) || 1;
549      const both = a.role === "part" && b.role === "part";
550      let best = shapes[k]!;
551      let bestScore = now * 1000 + best.bow * 100;
552      const straight = shapeOf(w, nodes, r, null);
553      const s0 = faults(k, straight.pts) * 1000;
554      if (s0 < bestScore - 1e-6) {
555        best = straight;
556        bestScore = s0;
557      }
558      const step = Math.max(6, len / 12);
559      const mx = (a.x + b.x) / 2;
560      const my = (a.y + b.y) / 2;
561      for (let dx = -MAX_BOW * len; dx <= MAX_BOW * len; dx += step) {
562        for (let dy = -MAX_BOW * len; dy <= MAX_BOW * len; dy += step) {
563          if (Math.hypot(dx, dy) > MAX_BOW * len) continue;
564          const s = shapeOf(w, nodes, r, [mx + dx, my + dy]);
565          if (both && !inside(s.pts)) continue;
566          const score = faults(k, s.pts) * 1000 + s.bow * 100;
567          if (score < bestScore - 1e-6) {
568            best = s;
569            bestScore = score;
570          }
571        }
572      }
573      if (best !== shapes[k]) {
574        shapes[k] = best;
575        changed = true;
576      }
577    }
578    if (!changed) break;
579  }
580  return shapes.map((s) => ({ seg: [...s.pts[0]!, ...s.pts[s.pts.length - 1]!], pts: s.pts, d: s.d, bow: s.bow }));
581}
582
583/** The search's own code and numbers, so a saved circle is searched again once what drew it changes. */
584export const SEARCH_CODE = [textWidth, wrapName, rectOf, grow, hitsRect, hitsBox, segmentsCross, exitPoint, segmentOf, random, placeHalf, placeRim, shares, coster, radiusFor, slotsFor, firstOrder, firstPlaces, shapeOf, bendWires]
585  .map(String)
586  .concat(SEARCH_NUMBERS.map(String))
587  .join("\0");