routing.mjs
1469 lines · archify/renderers/architecture/routing.mjs at a406594
1// Internal architecture router shared by rendering and geometry inspection.
2// Create a new router when measured boxes or connections change: port spreading
3// is computed once and route results are cached for this scene.
5import {
6 segmentIntersectsRect,
7 anchor,
8 automaticPortSpread,
9 alignAutomaticFacingPorts,
10 portHasCornerClearance,
11 automaticPortRhythmBridge,
12 defaultFromSide,
13 defaultToSide,
14 chosenSide,
15 properSegmentIntersection,
16 routeHonorsEndpointSides,
17 normalizeRoutePoints,
18 rectsOverlap,
19 roundedPath,
20 collectBorderRuns,
21 collectRouteRhythmIssues,
22 frameBorderSegments,
23} from '../shared/geometry.mjs';
24import { shortestOrthogonalGridRoute } from '../shared/route-quality.mjs';
26/**
27 * Router bound to one set of measured component boxes.
28 *
29 * @param {Map<string, {x,y,width,height,cx,cy}>} components measured boxes by id
30 * @param {Array<object>} connections the connection list to spread ports across
31 * @param {object} [options]
32 * @param {Array<{x,y,width,height,radius?}>} [options.frames] structural frames
33 * (boundaries) whose borders an automatic route may cross but never follow
34 * @param {number} [options.interiorSegmentPx] showcase floor for interior segments
35 * @param {number} [options.microSegmentPx] floor for any segment
36 * @param {(conn: object, points: number[][], context: {routes: number[][][], labels: object[]}) => object|null} [options.labelRectFor]
37 * default label rect of a routed relationship given the routes and label
38 * rects resolved so far; later automatic routes keep clear of it so a dense
39 * fan-out does not leave the label nowhere to go
40 * @param {(conn: object, endpoint: 'source'|'target') => string|undefined} [options.sideFor]
41 * endpoint side of a relationship whose author did not pin one, for a type
42 * that reads its layout on a different axis than architecture's row fan-out;
43 * an endpoint this hook leaves undefined keeps the shared inference
44 * @param {number} [options.maxPortSpacing] widest spacing the automatic port
45 * spread may use on a shared side; a type whose endpoint glyphs are taller
46 * than the default raises this so two symbols never draw over each other
47 * @param {(context: {conn: object, from: object, to: object, start: number[], end: number[], fromSide: string, toSide: string}) => number[][][]} [options.preferredCandidates]
48 * candidate families tried before the shared ones, so a type-owned corridor
49 * (a bundled trunk, a dedicated lane) wins over the generic midpoint
50 * @param {boolean} [options.crossingFreeGridFirst = false] before the obstacle
51 * grid search that may cross earlier routes, try one that treats every
52 * unrelated resolved route as a wall. A type whose showcase gate rejects any
53 * proper crossing (erd) opts in so a later relationship takes a clear detour
54 * instead of the shorter crossing the gate would refuse.
55 * @param {number} [options.componentGapPx = 0] when positive, the obstacle
56 * grid first keeps a route this far from every component it merely passes
57 * (its own endpoints stay at the 2-unit clearance) and falls back to the
58 * tight search only when no spaced route is accepted, so a detour does not
59 * run along a neighbouring box edge 3 units away from its border.
60 * @param {number} [options.minimumTerminalSegmentPx = 0] shortest first and
61 * last segment any automatic route may have, applied even with
62 * compositionFloors off: a type that rounds its corners when drawing needs
63 * the end segment to outlast the corner radius plus the micro-segment floor.
64 * @param {boolean} [options.compositionFloors = true] hold every automatic
65 * route to the rhythm floors the showcase gate enforces, so the planner never
66 * accepts a route the gate will reject. A type that draws a route differently
67 * from its logical points (the erd renderer removes the bundled trunk stretch
68 * from each branch and draws the bus as one path) turns this off: the floors
69 * describe a route drawn exactly as planned, and that type answers for the
70 * drawn result at its own gate instead.
71 * @param {number} [options.readabilityBottomMargin = 0] extra vertical room for
72 * the bounded readability sweep on an intrinsic-height canvas. Width and
73 * authored geometry stay fixed; fixed canvases leave this at zero.
74 */
75export function createRouter(components, connections = [], {
76 frames = [],
77 interiorSegmentPx = 16,
78 microSegmentPx = 8,
79 labelRectFor = null,
80 distinctAutomaticPorts = false,
81 preferReadableRoutes = false,
82 sideFor = null,
83 maxPortSpacing = null,
84 preferredCandidates = null,
85 compositionFloors = true,
86 crossingFreeGridFirst = false,
87 componentGapPx = 0,
88 minimumTerminalSegmentPx = 0,
89 readabilityBottomMargin = 0,
90} = {}) {
91 const frameBorders = frames.flatMap((frame) => frameBorderSegments(frame));
92 const LABEL_CLEARANCE = 4;
93 // Labels of already-routed relationships, reserved while planning the rest.
94 let reservedLabels = [];
95 let honourReservedLabels = true;
96 let allowGridSearch = true;
98 function routeClearsReservedLabels(conn, points) {
99 if (!honourReservedLabels) return true;
100 for (const entry of reservedLabels) {
101 if (entry.conn === conn) continue;
102 for (let index = 0; index < points.length - 1; index += 1) {
103 if (segmentIntersectsRect({ start: points[index], end: points[index + 1] }, entry.rect, LABEL_CLEARANCE)) {
104 return false;
105 }
106 }
107 }
108 return true;
109 }
111 // The grid search adds its own 2px component clearance; pre-expand so a
112 // reserved label keeps the same 4px clearance the placement pass demands.
113 function reservedLabelObstacles(gridClearance) {
114 if (!honourReservedLabels) return [];
115 const grow = LABEL_CLEARANCE - gridClearance;
116 return reservedLabels.map(({ rect }) => ({
117 x: rect.x - grow,
118 y: rect.y - grow,
119 width: rect.width + grow * 2,
120 height: rect.height + grow * 2,
121 }));
122 }
124 // Automatic routes are held to the same composition floors the showcase
125 // gate enforces afterwards. Accepting a route here that the gate rejects
126 // only hands the author a hand-routing repair the planner could have made.
127 function routeMeetsCompositionFloors(points) {
128 if (minimumTerminalSegmentPx > 0 && points.length > 2) {
129 const span = (a, b) => Math.abs(b[0] - a[0]) + Math.abs(b[1] - a[1]);
130 if (span(points[0], points[1]) < minimumTerminalSegmentPx
131 || span(points.at(-2), points.at(-1)) < minimumTerminalSegmentPx) return false;
132 }
133 if (compositionFloors
134 && collectRouteRhythmIssues({ routedRelations: [{ points }], interiorSegmentPx, microSegmentPx }).length) {
135 return false;
136 }
137 return !frames.length || collectBorderRuns({ routedRelations: [{ points }], frames }).length === 0;
138 }
139 const planningMetrics = {
140 routeCount: 0,
141 explicitRouteCount: 0,
142 automaticRouteCount: 0,
143 gridSearchCount: 0,
144 gridRoutedCount: 0,
145 gridCandidateNodeCount: 0,
146 gridUsableNodeCount: 0,
147 gridEdgeCount: 0,
148 gridVisitedNodeCount: 0,
149 avoidedSegmentCount: 0,
150 conflictFallbackCount: 0,
151 maximumGridSearchCount: 64,
152 gridBudgetExhaustedCount: 0,
153 crossoverRoutedCount: 0,
154 readabilityCandidateCount: 0,
155 readabilityImprovedCount: 0,
156 labelRelocationCandidateCount: 0,
157 labelRelocationImprovedCount: 0,
158 reciprocalCandidateCount: 0,
159 reciprocalImprovedCount: 0,
160 gridAttempts: [],
161 };
163 // ---- Connection routing ------------------------------------------------------
164 const gridComponentGaps = componentGapPx > 0 ? [componentGapPx, 0] : [0];
165 // The spaced search is a readability preference, so its route must also be
166 // clean as drawn: full rhythm floors (even for a type that turns them off)
167 // and terminal segments long enough for a rounded corner and an end marker.
168 function spacedRouteIsClean(points, gap) {
169 if (gap === 0) return true;
170 const terminal = (a, b) => Math.abs(b[0] - a[0]) + Math.abs(b[1] - a[1]);
171 return terminal(points[0], points[1]) >= 16 && terminal(points.at(-2), points.at(-1)) >= 16
172 && collectRouteRhythmIssues({ routedRelations: [{ points }], interiorSegmentPx, microSegmentPx }).length === 0;
173 }
174 function gridComponentObstacles(conn, gap) {
175 return [...components.values()].map((component) => (gap === 0 || component.id === conn.from || component.id === conn.to
176 ? component
177 : { ...component, x: component.x - gap, y: component.y - gap, width: component.width + gap * 2, height: component.height + gap * 2 }));
178 }
180 function routeClearsComponents(conn, points, clearance = 2) {
181 const endpointIds = new Set([conn.from, conn.to]);
182 for (const component of components.values()) {
183 if (endpointIds.has(component.id)) continue;
184 for (let index = 0; index < points.length - 1; index += 1) {
185 if (segmentIntersectsRect({ start: points[index], end: points[index + 1] }, component, clearance)) {
186 return false;
187 }
188 }
189 }
190 return routeClearsReservedLabels(conn, points);
191 }
193 function routeClearsEndpointComponents(points, from, to) {
194 const lastSegment = points.length - 2;
195 for (let index = 0; index <= lastSegment; index += 1) {
196 const segment = { start: points[index], end: points[index + 1] };
197 if (index > 0 && segmentIntersectsRect(segment, from)) return false;
198 if (index < lastSegment && segmentIntersectsRect(segment, to)) return false;
199 }
200 return true;
201 }
203 function relationshipsShareEndpoint(left, right) {
204 return left.from === right.from
205 || left.from === right.to
206 || left.to === right.from
207 || left.to === right.to;
208 }
210 function collinearOverlapLength(leftStart, leftEnd, rightStart, rightEnd) {
211 const epsilon = 0.0001;
212 if (Math.abs(leftStart[0] - leftEnd[0]) <= epsilon
213 && Math.abs(rightStart[0] - rightEnd[0]) <= epsilon
214 && Math.abs(leftStart[0] - rightStart[0]) <= epsilon) {
215 return Math.max(0,
216 Math.min(Math.max(leftStart[1], leftEnd[1]), Math.max(rightStart[1], rightEnd[1]))
217 - Math.max(Math.min(leftStart[1], leftEnd[1]), Math.min(rightStart[1], rightEnd[1])));
218 }
219 if (Math.abs(leftStart[1] - leftEnd[1]) <= epsilon
220 && Math.abs(rightStart[1] - rightEnd[1]) <= epsilon
221 && Math.abs(leftStart[1] - rightStart[1]) <= epsilon) {
222 return Math.max(0,
223 Math.min(Math.max(leftStart[0], leftEnd[0]), Math.max(rightStart[0], rightEnd[0]))
224 - Math.max(Math.min(leftStart[0], leftEnd[0]), Math.min(rightStart[0], rightEnd[0])));
225 }
226 return 0;
227 }
229 function orthogonalTouchOnResolvedInterior(start, end, resolvedStart, resolvedEnd) {
230 const epsilon = 0.0001;
231 const candidateHorizontal = Math.abs(start[1] - end[1]) <= epsilon;
232 const candidateVertical = Math.abs(start[0] - end[0]) <= epsilon;
233 const resolvedHorizontal = Math.abs(resolvedStart[1] - resolvedEnd[1]) <= epsilon;
234 const resolvedVertical = Math.abs(resolvedStart[0] - resolvedEnd[0]) <= epsilon;
235 if (candidateHorizontal && resolvedVertical) {
236 const x = resolvedStart[0];
237 const y = start[1];
238 return x >= Math.min(start[0], end[0]) - epsilon
239 && x <= Math.max(start[0], end[0]) + epsilon
240 && y > Math.min(resolvedStart[1], resolvedEnd[1]) + epsilon
241 && y < Math.max(resolvedStart[1], resolvedEnd[1]) - epsilon;
242 }
243 if (candidateVertical && resolvedHorizontal) {
244 const x = start[0];
245 const y = resolvedStart[1];
246 return y >= Math.min(start[1], end[1]) - epsilon
247 && y <= Math.max(start[1], end[1]) + epsilon
248 && x > Math.min(resolvedStart[0], resolvedEnd[0]) + epsilon
249 && x < Math.max(resolvedStart[0], resolvedEnd[0]) - epsilon;
250 }
251 return false;
252 }
254 function unrelatedResolvedRoutes(conn, resolvedRoutes) {
255 return resolvedRoutes.filter((entry) => !relationshipsShareEndpoint(conn, entry.conn));
256 }
258 function routeConflictsWithResolved(conn, points, resolvedRoutes) {
259 const unrelated = unrelatedResolvedRoutes(conn, resolvedRoutes);
260 for (const entry of unrelated) {
261 for (let left = 0; left < points.length - 1; left += 1) {
262 for (let right = 0; right < entry.points.length - 1; right += 1) {
263 if (properSegmentIntersection(
264 points[left],
265 points[left + 1],
266 entry.points[right],
267 entry.points[right + 1],
268 )) return true;
269 if (orthogonalTouchOnResolvedInterior(
270 points[left],
271 points[left + 1],
272 entry.points[right],
273 entry.points[right + 1],
274 )) return true;
275 if (collinearOverlapLength(
276 points[left],
277 points[left + 1],
278 entry.points[right],
279 entry.points[right + 1],
280 ) >= 8) return true;
281 }
282 }
283 }
284 return false;
285 }
287 function routeOverlapsResolved(conn, points, resolvedRoutes) {
288 // A common destination does not make two independently labelled routes a
289 // bus. Keep their corridors distinct too; explicit routes bypass planning.
290 for (const entry of resolvedRoutes) {
291 if (relationshipsShareEndpoint(conn, entry.conn)
292 && (!distinctAutomaticPorts || hasAuthoredRouteGeometry(entry.conn) || entry.conn.labelAt || conn.labelAt)) continue;
293 for (let left = 0; left < points.length - 1; left += 1) {
294 for (let right = 0; right < entry.points.length - 1; right += 1) {
295 if (collinearOverlapLength(
296 points[left],
297 points[left + 1],
298 entry.points[right],
299 entry.points[right + 1],
300 ) >= 8) return true;
301 }
302 }
303 }
304 return false;
305 }
307 const OUTWARD_SIDE_VECTOR = {
308 left: [-1, 0],
309 right: [1, 0],
310 top: [0, -1],
311 bottom: [0, 1],
312 };
314 function outwardStub(point, side, distance = 24) {
315 const [dx, dy] = OUTWARD_SIDE_VECTOR[side] || [0, 0];
316 return [point[0] + dx * distance, point[1] + dy * distance];
317 }
319 function collinearBacktrack(a, b, c) {
320 const first = [b[0] - a[0], b[1] - a[1]];
321 const second = [c[0] - b[0], c[1] - b[1]];
322 const cross = first[0] * second[1] - first[1] * second[0];
323 const dot = first[0] * second[0] + first[1] * second[1];
324 return Math.abs(cross) <= 0.0001 && dot < -0.0001;
325 }
327 function sideAwareBridgeCandidates(start, end, fromSide, toSide) {
328 const startStub = outwardStub(start, fromSide);
329 const endStub = outwardStub(end, toSide);
330 const rawCandidates = [];
331 const minimumBridge = 16;
332 const verticalSides = new Set(['top', 'bottom']);
333 const horizontalSides = new Set(['left', 'right']);
335 // Port spreading can leave parallel-side anchors only a few pixels apart.
336 // Route through a bounded outside channel so we keep both endpoint normals
337 // without introducing a tiny, noisy connector between the two stubs.
338 if (verticalSides.has(fromSide) && verticalSides.has(toSide)
339 && Math.abs(start[0] - end[0]) < minimumBridge) {
340 for (const channelX of [
341 Math.max(start[0], end[0]) + minimumBridge,
342 Math.min(start[0], end[0]) - minimumBridge,
343 ]) {
344 rawCandidates.push([
345 startStub,
346 [channelX, startStub[1]],
347 [channelX, endStub[1]],
348 endStub,
349 ]);
350 }
351 }
352 if (horizontalSides.has(fromSide) && horizontalSides.has(toSide)
353 && Math.abs(start[1] - end[1]) < minimumBridge) {
354 for (const channelY of [
355 Math.max(start[1], end[1]) + minimumBridge,
356 Math.min(start[1], end[1]) - minimumBridge,
357 ]) {
358 rawCandidates.push([
359 startStub,
360 [startStub[0], channelY],
361 [endStub[0], channelY],
362 endStub,
363 ]);
364 }
365 }
367 rawCandidates.push(
368 [startStub, [endStub[0], startStub[1]], endStub],
369 [startStub, [startStub[0], endStub[1]], endStub],
370 );
371 return rawCandidates.map((candidate) => normalizeRoutePoints([start, ...candidate, end]))
372 .filter((points) => points.length >= 2)
373 .filter((points) => !collinearBacktrack(points[0], points[1], points[2] || points[1]))
374 .filter((points) => !collinearBacktrack(points.at(-3) || points.at(-2), points.at(-2), points.at(-1)))
375 .filter((points) => routeHonorsEndpointSides(points, fromSide, toSide))
376 .sort((a, b) => a.length - b.length)
377 .map((points) => points.slice(1, -1));
378 }
380 const AUTOMATIC_PORT_CORNER_GUTTER = 16;
382 function alignFacingPorts(conn, from, to, start, end, fromSide, toSide, ports) {
383 return alignAutomaticFacingPorts(conn, from, to, start, end, fromSide, toSide, ports, {
384 accept: points => routeClearsEndpointComponents(points, from, to) && routeClearsComponents(conn, points),
385 });
386 }
388 // A reciprocal pair is repaired jointly after planning, so crossings that
389 // involve it are not final yet; keep the established first choice there.
390 const reciprocal = (conn) => connections.some((other) => other.from === conn.to && other.to === conn.from);
391 function siblingCrossings(conn, points, resolvedRoutes) {
392 if (reciprocal(conn)) return 0;
393 return crossingCount(conn, points, resolvedRoutes.filter((entry) => !reciprocal(entry.conn)));
394 }
396 function routeVia(conn, from, to, start, end, fromSide, toSide, resolvedRoutes = []) {
397 if (conn.via) return conn.via;
398 switch (conn.route || 'auto') {
399 case 'straight':
400 return [];
401 case 'orthogonal-h': {
402 const midX = (start[0] + end[0]) / 2;
403 return [[midX, start[1]], [midX, end[1]]];
404 }
405 case 'orthogonal-v': {
406 const midY = (start[1] + end[1]) / 2;
407 return [[start[0], midY], [end[0], midY]];
408 }
409 case 'auto':
410 default: {
411 // A caller may own the corridor for relationships that would otherwise
412 // share one channel. Preferred candidates are tried before the shared
413 // families, so a declared trunk or lane wins over the generic midpoint;
414 // a candidate that violates the endpoint contract or an obstacle is
415 // skipped and the historical order below still applies.
416 if (preferredCandidates) {
417 for (const candidate of preferredCandidates({ conn, from, to, start, end, fromSide, toSide }) || []) {
418 const points = [start, ...candidate, end];
419 if (routeHonorsEndpointSides(points, fromSide, toSide)
420 && routeClearsEndpointComponents(points, from, to)
421 && routeClearsComponents(conn, points)
422 && routeMeetsCompositionFloors(points)
423 && !routeConflictsWithResolved(conn, points, resolvedRoutes)) return candidate;
424 }
425 }
427 // Direct line unless the anchors are clearly orthogonal-friendly.
428 const deltaX = Math.abs(start[0] - end[0]);
429 const deltaY = Math.abs(start[1] - end[1]);
430 if (deltaX < 4 || deltaY < 4) {
431 const direct = [start, end];
432 if (routeHonorsEndpointSides(direct, fromSide, toSide)
433 && routeClearsEndpointComponents(direct, from, to)
434 && routeClearsComponents(conn, direct)
435 && routeMeetsCompositionFloors(direct)
436 && !routeConflictsWithResolved(conn, direct, resolvedRoutes)) return [];
437 }
439 const rhythmBridge = automaticPortRhythmBridge(start, end, fromSide, toSide, {
440 accept: (points) => (
441 routeClearsEndpointComponents(points, from, to)
442 && routeClearsComponents(conn, points)
443 && routeMeetsCompositionFloors(points)
444 && !routeConflictsWithResolved(conn, points, resolvedRoutes)
445 ),
446 });
447 if (rhythmBridge) return rhythmBridge.slice(1, -1);
449 // Automatic port spreading can leave otherwise aligned endpoints only a
450 // few pixels apart. A midpoint route would split that tiny difference
451 // into two unreadable endpoint stubs, so take a bounded outside channel
452 // when both anchors sit on parallel component sides.
453 const minimumStub = 8;
454 const fromVerticalSide = start[1] === from.y || start[1] === from.y + from.height;
455 const toVerticalSide = end[1] === to.y || end[1] === to.y + to.height;
456 if (fromVerticalSide && toVerticalSide && deltaX < minimumStub * 2) {
457 const outsideChannels = [
458 Math.max(start[0], end[0]) + minimumStub * 2,
459 Math.min(start[0], end[0]) - minimumStub * 2,
460 ];
461 for (const channelX of outsideChannels) {
462 const candidate = [[channelX, start[1]], [channelX, end[1]]];
463 const points = [start, ...candidate, end];
464 if (routeHonorsEndpointSides(points, fromSide, toSide)
465 && routeClearsComponents(conn, points)
466 && routeMeetsCompositionFloors(points)
467 && !routeConflictsWithResolved(conn, points, resolvedRoutes)) return candidate;
468 }
469 }
471 const fromHorizontalSide = start[0] === from.x || start[0] === from.x + from.width;
472 const toHorizontalSide = end[0] === to.x || end[0] === to.x + to.width;
473 if (fromHorizontalSide && toHorizontalSide && deltaY < minimumStub * 2) {
474 const outsideChannels = [
475 Math.max(start[1], end[1]) + minimumStub * 2,
476 Math.min(start[1], end[1]) - minimumStub * 2,
477 ];
478 for (const channelY of outsideChannels) {
479 const candidate = [[start[0], channelY], [end[0], channelY]];
480 const points = [start, ...candidate, end];
481 if (routeHonorsEndpointSides(points, fromSide, toSide)
482 && routeClearsComponents(conn, points)
483 && routeMeetsCompositionFloors(points)
484 && !routeConflictsWithResolved(conn, points, resolvedRoutes)) return candidate;
485 }
486 }
488 const midX = (start[0] + end[0]) / 2;
489 const horizontalFirst = [[midX, start[1]], [midX, end[1]]];
490 const midY = (start[1] + end[1]) / 2;
491 const verticalFirst = [[start[0], midY], [end[0], midY]];
492 const candidates = [horizontalFirst, verticalFirst];
493 const sideSafe = candidates.filter((candidate) => (
494 routeHonorsEndpointSides([start, ...candidate, end], fromSide, toSide)
495 ));
496 const sideAware = sideAwareBridgeCandidates(start, end, fromSide, toSide);
497 const nearParallelPorts = (
498 ((fromSide === 'top' || fromSide === 'bottom')
499 && (toSide === 'top' || toSide === 'bottom')
500 && deltaX < minimumStub * 2)
501 || ((fromSide === 'left' || fromSide === 'right')
502 && (toSide === 'left' || toSide === 'right')
503 && deltaY < minimumStub * 2)
504 );
505 const ordered = [
506 ...(nearParallelPorts ? sideAware : sideSafe),
507 ...(nearParallelPorts ? sideSafe : sideAware),
508 ];
509 let firstFeasible = null;
510 for (const candidate of ordered) {
511 const points = [start, ...candidate, end];
512 if (!(routeClearsEndpointComponents(points, from, to)
513 && routeClearsComponents(conn, points)
514 && routeMeetsCompositionFloors(points)
515 && !routeConflictsWithResolved(conn, points, resolvedRoutes)
516 && (!distinctAutomaticPorts || (!routeOverlapsResolved(conn, points, resolvedRoutes)
517 && !siblingCrossings(conn, points, resolvedRoutes))))) continue;
518 if (!conn.label || !labelRectFor || labelRectFor(conn, points, {
519 routes: resolvedRoutes.map((entry) => entry.points),
520 labels: reservedLabels.map((entry) => entry.rect),
521 })) return candidate;
522 firstFeasible ||= candidate;
523 }
524 if (firstFeasible) return firstFeasible;
525 // Siblings fanning out from one side all want the same midpoint
526 // channel. Step outward through the corridor to a free parallel
527 // channel before searching.
528 if (distinctAutomaticPorts) {
529 const channels = (from, to, mid) => {
530 const [low, high] = [Math.min(from, to) + 24, Math.max(from, to) - 24];
531 const values = [];
532 for (let offset = 16; mid - offset >= low || mid + offset <= high; offset += 16) {
533 values.push(...[mid + offset, mid - offset].filter((value) => value >= low && value <= high));
534 }
535 return values;
536 };
537 for (const candidate of [
538 ...channels(start[0], end[0], midX).map((x) => [[x, start[1]], [x, end[1]]]),
539 ...channels(start[1], end[1], midY).map((y) => [[start[0], y], [end[0], y]]),
540 ]) {
541 const points = [start, ...candidate, end];
542 if (routeHonorsEndpointSides(points, fromSide, toSide)
543 && routeClearsEndpointComponents(points, from, to)
544 && routeClearsComponents(conn, points)
545 && routeMeetsCompositionFloors(points)
546 && !routeConflictsWithResolved(conn, points, resolvedRoutes)
547 && !routeOverlapsResolved(conn, points, resolvedRoutes)
548 && !siblingCrossings(conn, points, resolvedRoutes)) return candidate;
549 }
550 }
552 // Two-bend doglegs are deliberately cheap, but a real architecture can
553 // place adjacent components on both of those corridors. Search a
554 // bounded obstacle grid before falling back to a route that the Clean
555 // Flow gate already knows violates the inferred endpoint directions.
556 // This keeps ordinary multi-bend avoidance renderer-owned instead of
557 // forcing the author to hand-place via points.
558 // Alternative endpoint pairs are cheap probes, not another grid-search
559 // budget. A legal short bridge often beats the first grid detour.
560 if (!allowGridSearch) return sideSafe[0] || sideAware[0] || horizontalFirst;
561 if (planningMetrics.gridSearchCount >= planningMetrics.maximumGridSearchCount) {
562 planningMetrics.gridBudgetExhaustedCount += 1;
563 planningMetrics.conflictFallbackCount += 1;
564 return sideSafe[0] || sideAware[0] || horizontalFirst;
565 }
566 // First-draft architecture graphs are not always planar at their
567 // authored node positions. The renderer gives automatic crossings a
568 // visible halo, so the grid owns opaque-node avoidance and rejects
569 // ambiguous shared corridors without forcing the model to hand-route
570 // a sprawling perimeter detour. Cheap candidates above still prefer a
571 // genuinely crossing-free path whenever one is available.
572 if (crossingFreeGridFirst) {
573 const unrelatedSegments = unrelatedResolvedRoutes(conn, resolvedRoutes)
574 .flatMap((entry) => entry.points.slice(1).map((end, index) => ({ start: entry.points[index], end })));
575 for (const gap of unrelatedSegments.length ? gridComponentGaps : []) {
576 planningMetrics.gridSearchCount += 1;
577 const strict = shortestOrthogonalGridRoute({
578 start,
579 end,
580 points: [start, end],
581 obstacles: [...gridComponentObstacles(conn, gap), ...reservedLabelObstacles(2)],
582 fromSide,
583 toSide,
584 clearance: 2,
585 maximumObstacleCount: 80,
586 endpointStubPx: 24,
587 maximumGridNodes: 4096,
588 avoidedSegments: unrelatedSegments,
589 allowAvoidedCrossings: false,
590 minimumAvoidedOverlapPx: 8,
591 routeSeparationPx: 8,
592 minimumSegmentPx: interiorSegmentPx,
593 borderSegments: frameBorders,
594 bendPenaltyPx: 48,
595 });
596 if (strict
597 && routeClearsEndpointComponents(strict.points, from, to)
598 && routeClearsComponents(conn, strict.points)
599 && !routeConflictsWithResolved(conn, strict.points, resolvedRoutes)
600 && !routeOverlapsResolved(conn, strict.points, resolvedRoutes)
601 && routeMeetsCompositionFloors(strict.points)
602 && spacedRouteIsClean(strict.points, gap)) {
603 planningMetrics.gridRoutedCount += 1;
604 return strict.points.slice(1, -1);
605 }
606 }
607 }
608 const avoidedSegments = resolvedRoutes
609 .filter((entry) => distinctAutomaticPorts && relationshipsShareEndpoint(conn, entry.conn)
610 && !hasAuthoredRouteGeometry(entry.conn) && !entry.conn.labelAt && !conn.labelAt)
611 .flatMap((entry) => entry.points.slice(1).map((end, index) => ({
612 start: entry.points[index], end,
613 })));
614 for (const gap of gridComponentGaps) {
615 const gridMetrics = {};
616 planningMetrics.gridSearchCount += 1;
617 planningMetrics.avoidedSegmentCount += avoidedSegments.length;
618 const searched = shortestOrthogonalGridRoute({
619 start,
620 end,
621 points: [start, end],
622 obstacles: [...gridComponentObstacles(conn, gap), ...reservedLabelObstacles(2)],
623 fromSide,
624 toSide,
625 clearance: 2,
626 maximumObstacleCount: 80,
627 endpointStubPx: 24,
628 maximumGridNodes: 4096,
629 avoidedSegments,
630 allowAvoidedCrossings: true,
631 minimumAvoidedOverlapPx: 8,
632 routeSeparationPx: 8,
633 minimumSegmentPx: interiorSegmentPx,
634 borderSegments: frameBorders,
635 bendPenaltyPx: 48,
636 metrics: gridMetrics,
637 });
638 planningMetrics.gridCandidateNodeCount += gridMetrics.candidateNodeCount || 0;
639 planningMetrics.gridUsableNodeCount += gridMetrics.usableNodeCount || 0;
640 planningMetrics.gridEdgeCount += gridMetrics.graphEdgeCount || 0;
641 planningMetrics.gridVisitedNodeCount += gridMetrics.visitedNodeCount || 0;
642 const clearsEndpoints = searched
643 ? routeClearsEndpointComponents(searched.points, from, to) : false;
644 const clearsComponents = searched
645 ? routeClearsComponents(conn, searched.points) : false;
646 const clearsRelationships = searched
647 ? !routeConflictsWithResolved(conn, searched.points, resolvedRoutes) : false;
648 const clearsSharedCorridors = searched
649 ? !routeOverlapsResolved(conn, searched.points, resolvedRoutes) : false;
650 const meetsFloors = searched
651 ? routeMeetsCompositionFloors(searched.points) && spacedRouteIsClean(searched.points, gap) : false;
652 const accepted = Boolean(
653 searched && clearsEndpoints && clearsComponents && clearsSharedCorridors && meetsFloors,
654 );
655 planningMetrics.gridAttempts.push({
656 relationship: conn.id || `${conn.from}->${conn.to}`,
657 fromSide,
658 toSide,
659 inputAvoidedSegmentCount: avoidedSegments.length,
660 ...gridMetrics,
661 accepted,
662 ...(!accepted && searched ? {
663 rejectedBy: [
664 ...(!clearsEndpoints ? ['endpoint-components'] : []),
665 ...(!clearsComponents ? ['components'] : []),
666 ...(!clearsSharedCorridors ? ['shared-corridor'] : []),
667 ...(!meetsFloors ? ['composition-floors'] : []),
668 ],
669 candidatePoints: searched.points,
670 } : {}),
671 });
672 if (accepted) {
673 planningMetrics.gridRoutedCount += 1;
674 if (!clearsRelationships) planningMetrics.crossoverRoutedCount += 1;
675 return searched.points.slice(1, -1);
676 }
677 }
679 // Both bounded doglegs are blocked. Keep the best endpoint-safe route
680 // when one exists so the universal Clean Flow gate reports the actual
681 // obstacle; otherwise preserve the historical deterministic fallback
682 // and let the endpoint-direction gate explain the side mismatch.
683 planningMetrics.conflictFallbackCount += 1;
684 return sideSafe[0] || sideAware[0] || horizontalFirst;
685 }
686 }
687 }
689 // A node's neighbours laid out as one row below (or above) it read as a
690 // fan-out: reach them all through the same vertical side. Center-based
691 // inference alone sends the outer ones sideways around their siblings.
692 const neighbourRects = new Map();
693 for (const conn of connections) {
694 const from = components.get(conn.from);
695 const to = components.get(conn.to);
696 if (!from || !to || from === to) continue;
697 for (const [node, other] of [[from, to], [to, from]]) {
698 neighbourRects.set(node.id, [...(neighbourRects.get(node.id) || []), other]);
699 }
700 }
701 function rowFanOutSides(from, to) {
702 if (!preferReadableRoutes) return null;
703 const verticalSides = (node, other) => {
704 const below = other.y >= node.y + node.height;
705 if (!below && other.y + other.height > node.y) return null;
706 if (['top', 'bottom'].includes(defaultFromSide(node, other))) return null;
707 const rowSibling = (neighbourRects.get(node.id) || []).some((sibling) => sibling !== other
708 && Math.abs(sibling.cy - other.cy) < 1
709 && defaultFromSide(node, sibling) === (below ? 'bottom' : 'top'));
710 // Only when a node of that row blocks a sideways route to one of the
711 // neighbours on this side; otherwise side exits stay clear and keep the
712 // vertical side free. Decide per side so a row never mixes both styles.
713 const blocked = (target) => {
714 const [gapStart, gapEnd] = target.cx < node.cx
715 ? [target.x + target.width, node.x] : [node.x + node.width, target.x];
716 return [...components.values()].some((rect) => rect !== node && rect !== target
717 && rect.y < target.y + target.height && rect.y + rect.height > target.y
718 && rect.x < gapEnd && rect.x + rect.width > gapStart);
719 };
720 const sameSide = (neighbourRects.get(node.id) || []).filter((sibling) => Math.abs(sibling.cy - other.cy) < 1
721 && defaultFromSide(node, sibling) === defaultFromSide(node, other));
722 return rowSibling && sameSide.some(blocked) ? (below ? 'bottom' : 'top') : null;
723 };
724 const opposite = { top: 'bottom', bottom: 'top' };
725 const fromSide = verticalSides(from, to);
726 if (fromSide) return { fromSide, toSide: opposite[fromSide] };
727 const toSide = verticalSides(to, from);
728 return toSide ? { fromSide: opposite[toSide], toSide } : null;
729 }
731 const pathCache = new Map();
732 const selectedSides = new Map();
733 const stroke = (relation) => relation.width || (relation.variant === 'emphasis' ? 1.8 : 1.5);
734 const markerSpacing = (left, right) => 3.5 * (stroke(left) + stroke(right));
735 const portSpacing = (left, right) => Math.max(14, markerSpacing(left, right) + 3.5);
736 function fanOutSide(conn, endpoint) {
737 const fanOut = rowFanOutSides(components.get(conn.from), components.get(conn.to));
738 return endpoint === 'source' ? fanOut?.fromSide : fanOut?.toSide;
739 }
740 // A caller may own the endpoint side of a relationship; whatever it leaves
741 // unresolved keeps architecture's row fan-out inference.
742 function inferredSide(conn, endpoint) {
743 return sideFor?.(conn, endpoint) || fanOutSide(conn, endpoint);
744 }
745 const automaticPorts = automaticPortSpread(connections, components, {
746 sideFor: inferredSide,
747 ...(maxPortSpacing === null ? {} : { maxSpacing: maxPortSpacing }),
748 // Preserve the established initial placement for ordinary markers; only
749 // widen groups whose arrowheads cannot fit the legacy 14px slots.
750 ...(distinctAutomaticPorts ? { spacingFor: (left, right) =>
751 markerSpacing(left, right) > 14 ? portSpacing(left, right) : 14 } : {}),
752 });
753 const incidentEndpoints = new Map();
754 for (const conn of connections) {
755 if (!components.has(conn.from) || !components.has(conn.to)) continue;
756 for (const [field, sideField] of [['from', 'fromSide'], ['to', 'toSide']]) {
757 const entries = incidentEndpoints.get(conn[field]) || [];
758 entries.push({ conn, field, sideField });
759 incidentEndpoints.set(conn[field], entries);
760 }
761 }
762 function inferredConnectionSides(conn) {
763 const from = components.get(conn.from);
764 const to = components.get(conn.to);
765 return {
766 fromSide: chosenSide(conn.fromSide, inferredSide(conn, 'source') || defaultFromSide(from, to)),
767 toSide: chosenSide(conn.toSide, inferredSide(conn, 'target') || defaultToSide(from, to)),
768 };
769 }
771 function connectionSides(conn) {
772 if (!routesPlanned && !routesPlanning) planRoutes();
773 return selectedSides.get(conn) || inferredConnectionSides(conn);
774 }
776 // The same side inference without the planning pass. A caller that must group
777 // relationships before any route exists (the erd renderer assigns a shared
778 // trunk per fan-in) reads its sides here: connectionSides() plans routes, and
779 // planning asks the grouping what the trunks are.
780 function inferredSides(conn) {
781 return inferredConnectionSides(conn);
782 }
784 function connectionEndpointSide(conn, endpoint) {
785 const field = endpoint === 'source' ? 'fromSide' : 'toSide';
786 if (conn[field] && conn[field] !== 'auto') return conn[field];
787 return connectionSides(conn)[field];
788 }
790 function hasAuthoredRouteGeometry(conn) {
791 return Boolean(
792 conn?.via
793 || (conn?.route && conn.route !== 'auto')
794 || conn?.channelX !== undefined
795 || conn?.channelY !== undefined
796 );
797 }
799 function hasAuthoredLabelPlacement(conn) {
800 return ['labelAt', 'labelDx', 'labelDy', 'labelSegment']
801 .some((field) => conn?.[field] !== undefined);
802 }
804 // A route can change sides after the initial port spread. Reserve slots on
805 // the final side as well: falling back to its midpoint can put an arrow
806 // between two existing slots, or directly on another incoming arrow.
807 function automaticEndpoint(conn, endpoint, rect, side, inferredSide) {
808 const initial = side === inferredSide ? automaticPorts.get(conn)?.[endpoint] : null;
809 const preferred = initial || anchor(rect, side);
810 if (hasAuthoredRouteGeometry(conn) || conn.labelAt) return { point: preferred, spread: Boolean(initial) };
811 const axis = side === 'left' || side === 'right' ? 1 : 0;
812 const occupied = [];
813 for (const { conn: other, field, sideField } of incidentEndpoints.get(rect.id) || []) {
814 if (other === conn || hasAuthoredRouteGeometry(other) || other.labelAt) continue;
815 const routed = pathCache.get(other);
816 const sides = selectedSides.get(other) || inferredConnectionSides(other);
817 if (sides[sideField] !== side) continue;
818 const point = routed
819 ? (field === 'from' ? routed.points[0] : routed.points.at(-1))
820 : automaticPorts.get(other)?.[field] || anchor(rect, side);
821 occupied.push({ value: point[axis], spacing: portSpacing(conn, other) });
822 }
823 if (!occupied.length) return { point: preferred, spread: Boolean(initial) };
824 // On an alternate side, equally close slots should approach the other
825 // node rather than pass its neighbours just because a coordinate is lower.
826 // Keep the established spread order on the inferred side unchanged.
827 const counterpart = components.get(endpoint === 'from' ? conn.to : conn.from);
828 const toward = side === inferredSide ? preferred[axis] : (axis === 1 ? counterpart.cy : counterpart.cx);
829 const candidates = [preferred[axis], ...occupied.flatMap(({ value, spacing }) => [value - spacing, value + spacing])]
830 .sort((a, b) => Math.abs(a - preferred[axis]) - Math.abs(b - preferred[axis])
831 || Math.abs(a - toward) - Math.abs(b - toward) || a - b);
832 for (const value of candidates) {
833 const point = [...preferred];
834 point[axis] = value;
835 if (portHasCornerClearance(rect, side, point)
836 && occupied.every((other) => Math.abs(value - other.value) >= other.spacing - 0.0001)) {
837 return { point, spread: true };
838 }
839 }
840 return { point: preferred, spread: true, crowded: true };
841 }
843 function connectionGeometry(conn, sides = inferredConnectionSides(conn)) {
844 const from = components.get(conn.from);
845 const to = components.get(conn.to);
846 const inferred = inferredConnectionSides(conn);
847 const { fromSide, toSide } = sides;
848 const legacyPorts = fromSide === inferred.fromSide && toSide === inferred.toSide ? automaticPorts.get(conn) : null;
849 const source = distinctAutomaticPorts
850 ? automaticEndpoint(conn, 'from', from, fromSide, inferred.fromSide)
851 : { point: legacyPorts?.from || anchor(from, fromSide), spread: Boolean(legacyPorts?.from) };
852 const target = distinctAutomaticPorts
853 ? automaticEndpoint(conn, 'to', to, toSide, inferred.toSide)
854 : { point: legacyPorts?.to || anchor(to, toSide), spread: Boolean(legacyPorts?.to) };
855 const ports = { from: source.spread, to: target.spread };
856 const { start, end } = alignFacingPorts(
857 conn,
858 from,
859 to,
860 source.point,
861 target.point,
862 fromSide,
863 toSide,
864 ports,
865 );
866 return { from, to, start, end, fromSide, toSide, crowded: source.crowded || target.crowded };
867 }
869 function routedForGeometry(conn, resolvedRoutes, geometry) {
870 const { from, to, start, end, fromSide, toSide } = geometry;
871 const authoredPoints = [
872 start,
873 ...routeVia(conn, from, to, start, end, fromSide, toSide, resolvedRoutes),
874 end,
875 ];
876 // Explicit waypoints are author-owned geometry. Keep even a collinear
877 // waypoint: it can intentionally split a route at a semantic touch point,
878 // and preserving it is part of the backwards-compatible authoring contract.
879 // Automatic routes remain normalized so the renderer does not emit noisy
880 // duplicate turns or zero-length segments.
881 const points = hasAuthoredRouteGeometry(conn)
882 ? authoredPoints
883 : normalizeRoutePoints(authoredPoints);
884 return { d: roundedPath(points, 8), points };
885 }
887 function cachePath(conn, routed, sides) {
888 pathCache.set(conn, routed);
889 selectedSides.set(conn, { fromSide: sides.fromSide, toSide: sides.toSide });
890 return routed;
891 }
893 const SIDE_ORDER = ['right', 'bottom', 'left', 'top'];
894 function candidateSidePairs(conn) {
895 const inferred = inferredConnectionSides(conn);
896 const authoredFrom = conn.fromSide && conn.fromSide !== 'auto' ? conn.fromSide : null;
897 const authoredTo = conn.toSide && conn.toSide !== 'auto' ? conn.toSide : null;
898 const fromOptions = authoredFrom
899 ? [authoredFrom]
900 : [inferred.fromSide, ...SIDE_ORDER.filter((side) => side !== inferred.fromSide)];
901 const toOptions = authoredTo
902 ? [authoredTo]
903 : [inferred.toSide, ...SIDE_ORDER.filter((side) => side !== inferred.toSide)];
904 return fromOptions.flatMap((fromSide) => toOptions.map((toSide) => ({
905 fromSide,
906 toSide,
907 deviationCount: Number(fromSide !== inferred.fromSide) + Number(toSide !== inferred.toSide),
908 }))).sort((left, right) => {
909 if (left.deviationCount !== right.deviationCount) {
910 return left.deviationCount - right.deviationCount;
911 }
912 const leftGeometry = connectionGeometry(conn, left);
913 const rightGeometry = connectionGeometry(conn, right);
914 const leftDistance = Math.abs(leftGeometry.end[0] - leftGeometry.start[0])
915 + Math.abs(leftGeometry.end[1] - leftGeometry.start[1]);
916 const rightDistance = Math.abs(rightGeometry.end[0] - rightGeometry.start[0])
917 + Math.abs(rightGeometry.end[1] - rightGeometry.start[1]);
918 return leftDistance - rightDistance;
919 });
920 }
922 function routeIsClear(conn, routed, geometry, resolvedRoutes) {
923 return !geometry.crowded && routed.points.length >= 2
924 && routeHonorsEndpointSides(routed.points, geometry.fromSide, geometry.toSide)
925 && routeClearsEndpointComponents(routed.points, geometry.from, geometry.to)
926 && routeClearsComponents(conn, routed.points)
927 && routeMeetsCompositionFloors(routed.points)
928 && !routeOverlapsResolved(conn, routed.points, resolvedRoutes);
929 }
931 function crossingCount(conn, points, resolvedRoutes) {
932 let count = 0;
933 for (const entry of resolvedRoutes) {
934 if (relationshipsShareEndpoint(conn, entry.conn)
935 && (!distinctAutomaticPorts || hasAuthoredRouteGeometry(entry.conn) || entry.conn.labelAt || conn.labelAt)) continue;
936 let crosses = false;
937 for (let index = 1; index < points.length && !crosses; index += 1) {
938 for (let otherIndex = 1; otherIndex < entry.points.length; otherIndex += 1) {
939 if (properSegmentIntersection(points[index - 1], points[index], entry.points[otherIndex - 1], entry.points[otherIndex])) {
940 crosses = true;
941 break;
942 }
943 }
944 }
945 if (crosses) count += 1;
946 }
947 return count;
948 }
950 function readabilityCost(conn, routed, resolvedRoutes) {
951 const points = routed.points;
952 const length = points.slice(1).reduce((total, point, index) => total
953 + Math.abs(point[0] - points[index][0]) + Math.abs(point[1] - points[index][1]), 0);
954 // A crossover is a reading cost even with a halo. Keep it finite: avoiding
955 // one crossing must not justify an arbitrarily long perimeter excursion.
956 return length + Math.max(0, points.length - 2) * 48 + crossingCount(conn, points, resolvedRoutes) * 160;
957 }
959 function computePath(conn, resolvedRoutes) {
960 if (hasAuthoredRouteGeometry(conn)) {
961 const sides = inferredConnectionSides(conn);
962 return cachePath(conn, routedForGeometry(
963 conn,
964 resolvedRoutes,
965 connectionGeometry(conn, sides),
966 ), sides);
967 }
969 let firstFallback = null;
970 const clearRoute = () => {
971 let firstClear = null;
972 for (const sides of candidateSidePairs(conn)) {
973 const geometry = connectionGeometry(conn, sides);
974 const routed = routedForGeometry(conn, resolvedRoutes, geometry);
975 if (!firstFallback) firstFallback = { routed, sides };
976 if (routeIsClear(conn, routed, geometry, resolvedRoutes)) {
977 firstClear = { routed, sides };
978 break;
979 }
980 }
981 return firstClear;
982 };
983 const routeLength = ({ routed }) => routed.points.slice(1)
984 .reduce((total, point, index) => total + Math.abs(point[0] - routed.points[index][0]) + Math.abs(point[1] - routed.points[index][1]), 0);
986 // Reserved labels are a preference, not an obstacle. A route that has no
987 // corridor around them, or that would have to detour far around them,
988 // takes the plain route instead and the label placement pass moves the
989 // label; only a modest extra length is worth keeping a label in place.
990 honourReservedLabels = true;
991 let chosen = clearRoute();
992 if (reservedLabels.length) {
993 honourReservedLabels = false;
994 if (!chosen) chosen = clearRoute();
995 else {
996 const direct = Math.abs(chosen.routed.points.at(-1)[0] - chosen.routed.points[0][0])
997 + Math.abs(chosen.routed.points.at(-1)[1] - chosen.routed.points[0][1]);
998 if (routeLength(chosen) > direct * 1.25 + 64) {
999 const plain = clearRoute();
1000 if (plain && routeLength(plain) * 1.25 + 64 < routeLength(chosen)) chosen = plain;
1001 }
1002 }
1003 honourReservedLabels = true;
1004 }
1005 if (chosen) return cachePath(conn, chosen.routed, chosen.sides);
1006 return cachePath(conn, firstFallback.routed, firstFallback.sides);
1007 }
1009 let routesPlanned = false;
1010 let routesPlanning = false;
1011 function planRoutes() {
1012 if (routesPlanned || routesPlanning) return;
1013 routesPlanning = true;
1014 const indexed = connections
1015 .map((conn, index) => ({ conn, index }))
1016 .filter(({ conn }) => components.has(conn.from) && components.has(conn.to));
1017 const explicit = indexed.filter(({ conn }) => hasAuthoredRouteGeometry(conn));
1018 const automatic = indexed.filter(({ conn }) => !hasAuthoredRouteGeometry(conn))
1019 .sort((left, right) => {
1020 const leftFrom = components.get(left.conn.from);
1021 const leftTo = components.get(left.conn.to);
1022 const rightFrom = components.get(right.conn.from);
1023 const rightTo = components.get(right.conn.to);
1024 const leftDistance = Math.abs(leftTo.cx - leftFrom.cx) + Math.abs(leftTo.cy - leftFrom.cy);
1025 const rightDistance = Math.abs(rightTo.cx - rightFrom.cx) + Math.abs(rightTo.cy - rightFrom.cy);
1026 return leftDistance - rightDistance || left.index - right.index;
1027 });
1028 const resolvedRoutes = [];
1029 reservedLabels = [];
1030 for (const { conn } of [...explicit, ...automatic]) {
1031 const routed = computePath(conn, resolvedRoutes);
1032 resolvedRoutes.push({ conn, points: routed.points });
1033 const rect = labelRectFor?.(conn, routed.points, {
1034 routes: resolvedRoutes.map((entry) => entry.points),
1035 labels: reservedLabels.map((entry) => entry.rect),
1036 });
1037 if (rect) reservedLabels.push({ conn, rect });
1038 }
1039 // Improve against the complete set of routes, not only earlier edges.
1040 // A greedy side change during the initial pass can steal a later edge's
1041 // corridor. This bounded sweep only changes one route at a time, keeping
1042 // every other route and label as an obstacle/reference.
1043 if (preferReadableRoutes) {
1044 const scenePoints = resolvedRoutes.flatMap((entry) => entry.points);
1045 for (const rect of [...components.values(), ...frames, ...reservedLabels.map((entry) => entry.rect)]) {
1046 scenePoints.push([rect.x, rect.y], [rect.x + rect.width, rect.y + rect.height]);
1047 }
1048 const bounds = {
1049 left: Math.min(...scenePoints.map(([x]) => x)), right: Math.max(...scenePoints.map(([x]) => x)),
1050 top: Math.min(...scenePoints.map(([, y]) => y)),
1051 bottom: Math.max(...scenePoints.map(([, y]) => y)),
1052 };
1053 const withinScene = ([x, y]) => x >= bounds.left && x <= bounds.right && y >= bounds.top && y <= bounds.bottom;
1054 const jointlyImproved = new Set();
1055 const endpointSlotsClear = (candidateRoutes, others, sidesOf) => {
1056 const entries = [...others, ...candidateRoutes];
1057 for (const candidate of candidateRoutes) {
1058 const sides = sidesOf(candidate.conn);
1059 for (const [componentId, side, point] of [
1060 [candidate.conn.from, sides.fromSide, candidate.points[0]],
1061 [candidate.conn.to, sides.toSide, candidate.points.at(-1)],
1062 ]) {
1063 const coordinate = side === 'left' || side === 'right' ? 1 : 0;
1064 for (const other of entries) {
1065 if (other.conn === candidate.conn) continue;
1066 const otherSides = sidesOf(other.conn);
1067 for (const [otherId, otherSide, otherPoint] of [
1068 [other.conn.from, otherSides.fromSide, other.points[0]],
1069 [other.conn.to, otherSides.toSide, other.points.at(-1)],
1070 ]) {
1071 if (componentId === otherId && side === otherSide
1072 && Math.abs(point[coordinate] - otherPoint[coordinate])
1073 < portSpacing(candidate.conn, other.conn) - 0.0001) return false;
1074 }
1075 }
1076 }
1077 }
1078 return true;
1079 };
1080 const labelClears = (rect, owner, entries, labels) => {
1081 if (!rect) return !owner.label;
1082 if (!withinScene([rect.x, rect.y])
1083 || !withinScene([rect.x + rect.width, rect.y + rect.height])
1084 || labels.some((other) => rectsOverlap(rect, other.rect, 2))) return false;
1085 return entries.every((entry) => entry.conn === owner || entry.points.slice(1).every((end, index) =>
1086 !segmentIntersectsRect({ start: entry.points[index], end }, rect, LABEL_CLEARANCE)));
1087 };
1088 function improveReciprocalPairs() {
1089 // A one-route sweep cannot repair reciprocal facing edges whose initial
1090 // spread groups differ. Try both direct lanes together after final side
1091 // geometry is known, leaving every other route and authored port in place.
1092 const paired = new Set();
1093 for (const first of resolvedRoutes) {
1094 const conn = first.conn;
1095 if (paired.has(conn) || typeOwned.has(conn) || hasAuthoredRouteGeometry(conn) || hasAuthoredLabelPlacement(conn)
1096 || (conn.fromSide && conn.fromSide !== 'auto')
1097 || (conn.toSide && conn.toSide !== 'auto')) continue;
1098 const second = resolvedRoutes.find((entry) => entry !== first
1099 && entry.conn.from === conn.to && entry.conn.to === conn.from && !typeOwned.has(entry.conn)
1100 && !hasAuthoredRouteGeometry(entry.conn) && !hasAuthoredLabelPlacement(entry.conn)
1101 && (!entry.conn.fromSide || entry.conn.fromSide === 'auto')
1102 && (!entry.conn.toSide || entry.conn.toSide === 'auto'));
1103 if (!second) continue;
1104 paired.add(conn);
1105 paired.add(second.conn);
1106 const firstSides = inferredConnectionSides(conn);
1107 const secondSides = inferredConnectionSides(second.conn);
1108 const horizontal = firstSides.fromSide === 'right' && firstSides.toSide === 'left'
1109 && secondSides.fromSide === 'left' && secondSides.toSide === 'right';
1110 const horizontalReverse = firstSides.fromSide === 'left' && firstSides.toSide === 'right'
1111 && secondSides.fromSide === 'right' && secondSides.toSide === 'left';
1112 const vertical = firstSides.fromSide === 'bottom' && firstSides.toSide === 'top'
1113 && secondSides.fromSide === 'top' && secondSides.toSide === 'bottom';
1114 const verticalReverse = firstSides.fromSide === 'top' && firstSides.toSide === 'bottom'
1115 && secondSides.fromSide === 'bottom' && secondSides.toSide === 'top';
1116 if (!horizontal && !horizontalReverse && !vertical && !verticalReverse) continue;
1117 if (first.points.length <= 2 && second.points.length <= 2) continue;
1118 const axis = horizontal || horizontalReverse ? 1 : 0;
1119 const others = resolvedRoutes.filter((entry) => entry !== first && entry !== second);
1120 const firstGeometry = connectionGeometry(conn, firstSides);
1121 const secondGeometry = connectionGeometry(second.conn, secondSides);
1122 if (firstGeometry.crowded || secondGeometry.crowded) continue;
1123 const previousLabels = reservedLabels;
1124 let improved = false;
1125 reservedLabels = reservedLabels.filter((entry) => entry.conn !== conn && entry.conn !== second.conn);
1126 try {
1127 const lanes = (geometry) => [...new Set([geometry.start[axis], geometry.end[axis]])];
1128 const direct = (geometry, lane) => {
1129 const start = [...geometry.start];
1130 const end = [...geometry.end];
1131 start[axis] = lane;
1132 end[axis] = lane;
1133 return { points: [start, end], d: roundedPath([start, end], 8) };
1134 };
1135 const pairSides = (candidate) => (candidate === conn ? firstSides
1136 : candidate === second.conn ? secondSides : selectedSides.get(candidate));
1137 let best = null;
1138 let bestCost = readabilityCost(conn, first, [...others, second])
1139 + readabilityCost(second.conn, second, [...others, first]);
1140 for (const firstLane of lanes(firstGeometry)) {
1141 for (const secondLane of lanes(secondGeometry)) {
1142 planningMetrics.reciprocalCandidateCount += 1;
1143 const firstRoute = { conn, ...direct(firstGeometry, firstLane) };
1144 const secondRoute = { conn: second.conn, ...direct(secondGeometry, secondLane) };
1145 const candidates = [firstRoute, secondRoute];
1146 if (!candidates.every((entry) => entry.points.every(withinScene))) continue;
1147 if (!endpointSlotsClear(candidates, others, pairSides)) continue;
1148 if (!candidates.every((entry, index) => {
1149 const geometry = entry.conn === conn ? firstGeometry : secondGeometry;
1150 if (!portHasCornerClearance(geometry.from, geometry.fromSide, entry.points[0])
1151 || !portHasCornerClearance(geometry.to, geometry.toSide, entry.points.at(-1))) return false;
1152 return routeIsClear(entry.conn, entry, geometry, [...others, candidates[1 - index]]);
1153 })) continue;
1154 const firstRect = labelRectFor?.(conn, firstRoute.points, {
1155 routes: [...others.map((entry) => entry.points), ...candidates.map((entry) => entry.points)],
1156 labels: reservedLabels.map((entry) => entry.rect),
1157 });
1158 if (!labelClears(firstRect, conn, [...others, secondRoute], reservedLabels)) continue;
1159 const secondRect = labelRectFor?.(second.conn, secondRoute.points, {
1160 routes: [...others.map((entry) => entry.points), ...candidates.map((entry) => entry.points)],
1161 labels: [...reservedLabels.map((entry) => entry.rect), ...(firstRect ? [firstRect] : [])],
1162 });
1163 if (!labelClears(secondRect, second.conn, [...others, firstRoute], [
1164 ...reservedLabels, ...(firstRect ? [{ conn, rect: firstRect }] : []),
1165 ])) continue;
1166 const cost = readabilityCost(conn, firstRoute, [...others, secondRoute])
1167 + readabilityCost(second.conn, secondRoute, [...others, firstRoute]);
1168 if (cost < bestCost) {
1169 best = { firstRoute, secondRoute, firstRect, secondRect };
1170 bestCost = cost;
1171 }
1172 }
1173 }
1174 if (!best) continue;
1175 cachePath(conn, best.firstRoute, firstSides);
1176 cachePath(second.conn, best.secondRoute, secondSides);
1177 first.points = best.firstRoute.points;
1178 second.points = best.secondRoute.points;
1179 planningMetrics.reciprocalImprovedCount += 1;
1180 jointlyImproved.add(conn);
1181 jointlyImproved.add(second.conn);
1182 improved = true;
1183 reservedLabels = [
1184 ...reservedLabels,
1185 ...(best.firstRect ? [{ conn, rect: best.firstRect }] : []),
1186 ...(best.secondRect ? [{ conn: second.conn, rect: best.secondRect }] : []),
1187 ];
1188 } finally {
1189 if (!improved) reservedLabels = previousLabels;
1190 }
1191 }
1192 }
1193 // A type-owned corridor (an erd bundled trunk or dedicated lane) is the
1194 // route its renderer draws around; the generic sweep must not trade it
1195 // for a shorter lane and leave the bus without its branch.
1196 const followsPreferredCorridor = (entry) => {
1197 if (!preferredCandidates) return false;
1198 const sides = selectedSides.get(entry.conn);
1199 if (!sides) return false;
1200 const interior = JSON.stringify(entry.points.slice(1, -1));
1201 return (preferredCandidates({
1202 conn: entry.conn,
1203 from: components.get(entry.conn.from),
1204 to: components.get(entry.conn.to),
1205 start: entry.points[0],
1206 end: entry.points.at(-1),
1207 fromSide: sides.fromSide,
1208 toSide: sides.toSide,
1209 }) || []).some((candidate) => JSON.stringify(candidate) === interior);
1210 };
1211 const typeOwned = new Set(resolvedRoutes.filter(followsPreferredCorridor).map((entry) => entry.conn));
1212 function relocatedLabelsFor(conn, routed, others) {
1213 // A provisional label may occupy an otherwise clear corridor. Move at
1214 // most one automatic label, on its existing route, and accept the pair
1215 // only when both labels fit without borrowing other labels' space.
1216 const displaced = reservedLabels.filter((label) => label.conn !== conn && routed.points.slice(1).some((end, index) =>
1217 segmentIntersectsRect({ start: routed.points[index], end }, label.rect, LABEL_CLEARANCE)));
1218 if (displaced.length !== 1) return null;
1219 const owner = displaced[0].conn;
1220 if (typeOwned.has(owner) || hasAuthoredRouteGeometry(owner) || hasAuthoredLabelPlacement(owner)) return null;
1221 const labels = reservedLabels.filter((label) => label.conn !== conn && label.conn !== owner);
1222 const routes = [...others, { conn, points: routed.points }];
1223 const moved = routes.find((entry) => entry.conn === owner);
1224 for (const entry of [moved, { conn, points: routed.points }]) {
1225 const rect = labelRectFor?.(entry.conn, entry.points, {
1226 routes: routes.map((route) => route.points),
1227 labels: labels.map((label) => label.rect),
1228 });
1229 if (!labelClears(rect, entry.conn, routes, labels)
1230 || (rect && [...components.values()].some((component) => rectsOverlap(rect, component, -2)))) return null;
1231 if (rect) labels.push({ conn: entry.conn, rect });
1232 }
1233 return labels;
1234 }
1235 function improveComplexRoutes(onlyCrossings = false) {
1236 for (const entry of resolvedRoutes) {
1237 const { conn } = entry;
1238 if (jointlyImproved.has(conn) || typeOwned.has(conn) || hasAuthoredRouteGeometry(conn) || hasAuthoredLabelPlacement(conn)) continue;
1239 const others = resolvedRoutes.filter((other) => other !== entry);
1240 // Preserve uncomplicated routes and their established inferred sides.
1241 // Spend the comparison budget where the complete scene has a reading
1242 // cost: a crossover, more than two bends, or no room for its label.
1243 const crossingsBefore = crossingCount(conn, entry.points, others);
1244 const currentLabel = labelRectFor?.(conn, entry.points, {
1245 routes: others.map(other => other.points),
1246 labels: reservedLabels.filter(label => label.conn !== conn).map(label => label.rect),
1247 });
1248 const labelBlocked = Boolean(conn.label && labelRectFor && !currentLabel);
1249 if (!labelBlocked && crossingsBefore === 0 && (onlyCrossings || entry.points.length <= 4)) continue;
1250 let best = null;
1251 let bestCost = labelBlocked ? Infinity : readabilityCost(conn, { points: entry.points }, others);
1252 for (const sides of candidateSidePairs(conn)) {
1253 const geometry = connectionGeometry(conn, sides);
1254 const routed = routedForGeometry(conn, others, geometry);
1255 planningMetrics.readabilityCandidateCount += 1;
1256 if (!routed.points.every(withinScene) || !routeIsClear(conn, routed, geometry, others)) continue;
1257 if (onlyCrossings && crossingCount(conn, routed.points, others) >= crossingsBefore) continue;
1258 const cost = readabilityCost(conn, routed, others);
1259 if (cost < bestCost) {
1260 const rect = labelRectFor?.(conn, routed.points, {
1261 routes: [...others.map((other) => other.points), routed.points],
1262 labels: reservedLabels.filter((label) => label.conn !== conn).map((label) => label.rect),
1263 });
1264 // Include the reserved label in this pass's bounds. In
1265 // particular, a shorter route must not widen and shrink the graph.
1266 if (labelRectFor && !labelClears(rect, conn, others, reservedLabels.filter(label => label.conn !== conn))) continue;
1267 if (onlyCrossings && (!endpointSlotsClear([{ conn, points: routed.points }], others,
1268 candidate => candidate === conn ? sides : selectedSides.get(candidate))
1269 || (rect && [...components.values()].some(component => rectsOverlap(rect, component, -2))))) continue;
1270 best = { routed, sides, rect };
1271 bestCost = cost;
1272 }
1273 }
1274 if (!best) continue;
1275 cachePath(conn, best.routed, best.sides);
1276 entry.points = best.routed.points;
1277 planningMetrics.readabilityImprovedCount += 1;
1278 reservedLabels = reservedLabels.filter((label) => label.conn !== conn);
1279 if (best.rect) reservedLabels.push({ conn, rect: best.rect });
1280 }
1281 }
1282 allowGridSearch = false;
1283 try {
1284 improveReciprocalPairs();
1285 improveComplexRoutes();
1286 // A bent route between nodes that overlap across the gap separating
1287 // them can run straight through facing sides inside that overlap.
1288 // Authored sides must already face; every other route, slot and label
1289 // stays fixed, and the straight lane must pass the same checks.
1290 for (const entry of resolvedRoutes) {
1291 const { conn } = entry;
1292 if (entry.points.length < 4 || jointlyImproved.has(conn) || typeOwned.has(conn)
1293 || hasAuthoredRouteGeometry(conn) || hasAuthoredLabelPlacement(conn)) continue;
1294 const from = components.get(conn.from);
1295 const to = components.get(conn.to);
1296 const facing = from.x + from.width <= to.x ? { fromSide: 'right', toSide: 'left' }
1297 : to.x + to.width <= from.x ? { fromSide: 'left', toSide: 'right' }
1298 : from.y + from.height <= to.y ? { fromSide: 'bottom', toSide: 'top' }
1299 : to.y + to.height <= from.y ? { fromSide: 'top', toSide: 'bottom' } : null;
1300 if (!facing) continue;
1301 const axis = facing.fromSide === 'right' || facing.fromSide === 'left' ? 1 : 0;
1302 const [origin, size] = axis === 1 ? ['y', 'height'] : ['x', 'width'];
1303 const low = Math.max(from[origin], to[origin]) + AUTOMATIC_PORT_CORNER_GUTTER;
1304 const high = Math.min(from[origin] + from[size], to[origin] + to[size]) - AUTOMATIC_PORT_CORNER_GUTTER;
1305 if (high < low
1306 || (conn.fromSide && conn.fromSide !== 'auto' && conn.fromSide !== facing.fromSide)
1307 || (conn.toSide && conn.toSide !== 'auto' && conn.toSide !== facing.toSide)) continue;
1308 const sides = facing;
1309 const geometry = connectionGeometry(conn, sides);
1310 const start = geometry.start;
1311 const end = geometry.end;
1312 const clamp = (value) => Math.min(high, Math.max(low, value));
1313 const others = resolvedRoutes.filter((other) => other !== entry);
1314 const otherLabels = reservedLabels.filter((label) => label.conn !== conn);
1315 const crossingsBefore = crossingCount(conn, entry.points, others);
1316 const sidesOf = (candidate) => (candidate === conn ? sides : selectedSides.get(candidate));
1317 for (const lane of new Set([start[axis], end[axis], (start[axis] + end[axis]) / 2, (low + high) / 2].map(clamp))) {
1318 const points = [[...start], [...end]];
1319 points[0][axis] = lane;
1320 points[1][axis] = lane;
1321 const routed = { conn, points, d: roundedPath(points, 8) };
1322 if (!points.every(withinScene)
1323 || !endpointSlotsClear([routed], others, sidesOf)
1324 || !routeIsClear(conn, routed, geometry, others)
1325 || crossingCount(conn, points, others) > crossingsBefore) continue;
1326 const rect = labelRectFor?.(conn, points, {
1327 routes: [...others.map((other) => other.points), points],
1328 labels: otherLabels.map((label) => label.rect),
1329 });
1330 if (!labelClears(rect, conn, others, otherLabels)) continue;
1331 cachePath(conn, { points, d: routed.d }, sides);
1332 entry.points = points;
1333 planningMetrics.readabilityImprovedCount += 1;
1334 reservedLabels = [...otherLabels, ...(rect ? [{ conn, rect }] : [])];
1335 break;
1336 }
1337 }
1338 // Finish the established route/straightening plan first. Moving a
1339 // label earlier could prevent a later edge from taking its straight
1340 // corridor, even though the local candidate was cheaper.
1341 for (const entry of resolvedRoutes) {
1342 const { conn } = entry;
1343 if (jointlyImproved.has(conn) || typeOwned.has(conn) || hasAuthoredRouteGeometry(conn) || hasAuthoredLabelPlacement(conn)) continue;
1344 const others = resolvedRoutes.filter((other) => other !== entry);
1345 if (entry.points.length <= 4 && crossingCount(conn, entry.points, others) === 0) continue;
1346 let best = null;
1347 let bestCost = readabilityCost(conn, entry, others);
1348 if (labelRectFor && reservedLabels.some((label) => label.conn !== conn)) {
1349 // One additional side sweep, with no grid search or cascading
1350 // relayout. Temporary reservations can be ignored only after a
1351 // replacement placement is verified against the complete scene.
1352 for (const sides of candidateSidePairs(conn)) {
1353 const geometry = connectionGeometry(conn, sides);
1354 let routed;
1355 let clear;
1356 honourReservedLabels = false;
1357 try {
1358 routed = routedForGeometry(conn, others, geometry);
1359 clear = routeIsClear(conn, routed, geometry, others);
1360 } finally {
1361 honourReservedLabels = true;
1362 }
1363 planningMetrics.labelRelocationCandidateCount += 1;
1364 const cost = readabilityCost(conn, routed, others);
1365 if (cost >= bestCost || !clear || !routed.points.every(withinScene)
1366 || crossingCount(conn, routed.points, others) > crossingCount(conn, entry.points, others)
1367 || !endpointSlotsClear([{ conn, points: routed.points }], others,
1368 (candidate) => candidate === conn ? sides : selectedSides.get(candidate))) continue;
1369 const labels = relocatedLabelsFor(conn, routed, others);
1370 if (!labels) continue;
1371 best = { routed, sides, labels };
1372 bestCost = cost;
1373 }
1374 }
1375 if (!best) continue;
1376 cachePath(conn, best.routed, best.sides);
1377 entry.points = best.routed.points;
1378 reservedLabels = best.labels;
1379 planningMetrics.labelRelocationImprovedCount += 1;
1380 }
1381 // A side's midpoint may be blocked even when a corner port has a
1382 // clear one-bend route. Probe bent automatic routes, keeping
1383 // all other paths/labels fixed and the existing corner inset intact.
1384 // Eight perpendicular side pairs, at most three slots per endpoint:
1385 // 72 cheap candidates per route, without another grid search.
1386 for (const entry of resolvedRoutes) {
1387 const { conn } = entry;
1388 if (entry.points.length < 4 || jointlyImproved.has(conn) || typeOwned.has(conn)
1389 || hasAuthoredRouteGeometry(conn) || hasAuthoredLabelPlacement(conn)) continue;
1390 const others = resolvedRoutes.filter((other) => other !== entry);
1391 const labels = reservedLabels.filter((label) => label.conn !== conn);
1392 const crossingsBefore = crossingCount(conn, entry.points, others);
1393 let best = null;
1394 let bestCost = readabilityCost(conn, entry, others);
1395 const slots = (rect, side, preferred) => {
1396 const horizontal = side === 'left' || side === 'right';
1397 const axis = horizontal ? 1 : 0;
1398 const origin = horizontal ? rect.y : rect.x;
1399 const size = horizontal ? rect.height : rect.width;
1400 const inset = Math.min(AUTOMATIC_PORT_CORNER_GUTTER, size / 2);
1401 return [...new Set([preferred[axis], origin + inset, origin + size - inset])].map((value) => {
1402 const point = [...preferred];
1403 point[axis] = value;
1404 return point;
1405 }).filter((point) => portHasCornerClearance(rect, side, point));
1406 };
1407 for (const sides of candidateSidePairs(conn)) {
1408 const horizontal = (side) => side === 'left' || side === 'right';
1409 if (horizontal(sides.fromSide) === horizontal(sides.toSide)) continue;
1410 const geometry = connectionGeometry(conn, sides);
1411 for (const start of slots(geometry.from, sides.fromSide, geometry.start)) {
1412 for (const end of slots(geometry.to, sides.toSide, geometry.end)) {
1413 const corner = horizontal(sides.fromSide) ? [end[0], start[1]] : [start[0], end[1]];
1414 const points = normalizeRoutePoints([start, corner, end]);
1415 const routed = { points, d: roundedPath(points, 8) };
1416 const cost = readabilityCost(conn, routed, others);
1417 if (cost >= bestCost || points.length !== 3 || !points.every(withinScene)
1418 || !endpointSlotsClear([{ conn, points }], others,
1419 (candidate) => candidate === conn ? sides : selectedSides.get(candidate))
1420 || !routeIsClear(conn, routed, { ...geometry, start, end, crowded: false }, others)
1421 || crossingCount(conn, points, others) > crossingsBefore) continue;
1422 const rect = labelRectFor?.(conn, points, {
1423 routes: [...others.map((other) => other.points), points],
1424 labels: labels.map((label) => label.rect),
1425 });
1426 if (!labelClears(rect, conn, others, labels)
1427 || (rect && [...components.values()].some((component) => rectsOverlap(rect, component, -2)))) continue;
1428 best = { routed, sides, rect };
1429 bestCost = cost;
1430 }
1431 }
1432 }
1433 if (!best) continue;
1434 cachePath(conn, best.routed, best.sides);
1435 entry.points = best.routed.points;
1436 reservedLabels = [...labels, ...(best.rect ? [{ conn, rect: best.rect }] : [])];
1437 planningMetrics.readabilityImprovedCount += 1;
1438 }
1439 // Complete the original bounded plan first. Only a remaining crossing
1440 // can justify using an extra lower corridor; an already clear scene
1441 // must not grow merely because its labels could move into that space.
1442 if (readabilityBottomMargin > 0) {
1443 bounds.bottom += readabilityBottomMargin;
1444 improveComplexRoutes(true);
1445 }
1446 } finally {
1447 allowGridSearch = true;
1448 }
1449 }
1450 planningMetrics.routeCount = resolvedRoutes.length;
1451 planningMetrics.explicitRouteCount = explicit.length;
1452 planningMetrics.automaticRouteCount = automatic.length;
1453 routesPlanning = false;
1454 routesPlanned = true;
1455 }
1457 function pathFor(conn) {
1458 planRoutes();
1459 if (pathCache.has(conn)) return pathCache.get(conn);
1460 return computePath(conn, []);
1461 }
1463 function routingMetrics() {
1464 planRoutes();
1465 return { ...planningMetrics };
1466 }
1468 return { ports: automaticPorts, pathFor, connectionSides, inferredSides, connectionEndpointSide, routingMetrics };
1469}