route-quality.mjs
670 lines · archify/renderers/shared/route-quality.mjs at a406594
1import { recordDiagnostic } from './diagnostics.mjs';
2import {
3 asArray,
4 isFinitePoint,
5 normalizeRoutePoints,
6 properSegmentIntersection,
7 segmentIntersectsRect,
8} from './geometry.mjs';
10const DEFAULTS = Object.freeze({
11 clearance: 2,
12 minimumDetourRatio: 2.5,
13 minimumExcessLengthPx: 200,
14 minimumEmptyExcursionPx: 96,
15 maximumObstacleCount: 80,
16 sharedCorridorMinimumPx: 32,
17});
19const OUTWARD = Object.freeze({
20 left: [-1, 0],
21 right: [1, 0],
22 top: [0, -1],
23 bottom: [0, 1],
24});
26function rounded(value) {
27 return Math.round(value * 100) / 100;
28}
30function pointKey(point) {
31 return `${point[0]}\u0000${point[1]}`;
32}
34class MinHeap {
35 constructor() {
36 this.entries = [];
37 }
39 push(key, distance) {
40 const entry = { key, distance };
41 this.entries.push(entry);
42 let index = this.entries.length - 1;
43 while (index > 0) {
44 const parent = Math.floor((index - 1) / 2);
45 if (this.entries[parent].distance <= distance) break;
46 this.entries[index] = this.entries[parent];
47 index = parent;
48 }
49 this.entries[index] = entry;
50 }
52 pop() {
53 if (!this.entries.length) return null;
54 const first = this.entries[0];
55 const last = this.entries.pop();
56 if (!this.entries.length) return first;
57 let index = 0;
58 while (true) {
59 const left = index * 2 + 1;
60 const right = left + 1;
61 if (left >= this.entries.length) break;
62 const child = right < this.entries.length
63 && this.entries[right].distance < this.entries[left].distance ? right : left;
64 if (this.entries[child].distance >= last.distance) break;
65 this.entries[index] = this.entries[child];
66 index = child;
67 }
68 this.entries[index] = last;
69 return first;
70 }
71}
73function orthogonalLength(points) {
74 let total = 0;
75 for (let index = 0; index < points.length - 1; index += 1) {
76 const [x1, y1] = points[index];
77 const [x2, y2] = points[index + 1];
78 if (x1 !== x2 && y1 !== y2) return null;
79 total += Math.abs(x2 - x1) + Math.abs(y2 - y1);
80 }
81 return total;
82}
84function inferredSide(points, endpoint) {
85 if (points.length < 2) return null;
86 const start = endpoint === 'source' ? points[0] : points.at(-2);
87 const end = endpoint === 'source' ? points[1] : points.at(-1);
88 const dx = end[0] - start[0];
89 const dy = end[1] - start[1];
90 if (endpoint === 'source') {
91 if (dx > 0 && dy === 0) return 'right';
92 if (dx < 0 && dy === 0) return 'left';
93 if (dy > 0 && dx === 0) return 'bottom';
94 if (dy < 0 && dx === 0) return 'top';
95 } else {
96 if (dx > 0 && dy === 0) return 'left';
97 if (dx < 0 && dy === 0) return 'right';
98 if (dy > 0 && dx === 0) return 'top';
99 if (dy < 0 && dx === 0) return 'bottom';
100 }
101 return null;
102}
104function moveOutward(point, side, distance) {
105 const [dx, dy] = OUTWARD[side] || [0, 0];
106 return [point[0] + dx * distance, point[1] + dy * distance];
107}
109function expandedRect(rect, clearance) {
110 return {
111 id: rect.id,
112 x: rect.x - clearance,
113 y: rect.y - clearance,
114 width: rect.width + clearance * 2,
115 height: rect.height + clearance * 2,
116 };
117}
119function boundsForRects(rects) {
120 const usable = [...rects].filter((rect) => (
121 rect && isFinitePoint(rect.x, rect.y, rect.width, rect.height)
122 && rect.width >= 0 && rect.height >= 0
123 ));
124 if (!usable.length) return null;
125 const left = Math.min(...usable.map((rect) => rect.x));
126 const top = Math.min(...usable.map((rect) => rect.y));
127 const right = Math.max(...usable.map((rect) => rect.x + rect.width));
128 const bottom = Math.max(...usable.map((rect) => rect.y + rect.height));
129 return { left, top, right, bottom, width: right - left, height: bottom - top };
130}
132function boundsForPoints(points) {
133 if (!points.length) return null;
134 const xs = points.map(([x]) => x);
135 const ys = points.map(([, y]) => y);
136 const left = Math.min(...xs);
137 const top = Math.min(...ys);
138 const right = Math.max(...xs);
139 const bottom = Math.max(...ys);
140 return { left, top, right, bottom, width: right - left, height: bottom - top };
141}
143function outsideExcursion(routeBounds, contentBounds) {
144 if (!routeBounds || !contentBounds) return null;
145 const sides = {
146 left: Math.max(0, contentBounds.left - routeBounds.left),
147 top: Math.max(0, contentBounds.top - routeBounds.top),
148 right: Math.max(0, routeBounds.right - contentBounds.right),
149 bottom: Math.max(0, routeBounds.bottom - contentBounds.bottom),
150 };
151 return { ...sides, maximum: Math.max(...Object.values(sides)) };
152}
154function pointDistanceFromRect(point, rect) {
155 const dx = Math.max(rect.x - point[0], 0, point[0] - (rect.x + rect.width));
156 const dy = Math.max(rect.y - point[1], 0, point[1] - (rect.y + rect.height));
157 return dx + dy;
158}
160function emptyControlPointClearance(points, contentRects) {
161 const controls = points.slice(1, -1);
162 const rects = [...contentRects].filter((rect) => (
163 rect && isFinitePoint(rect.x, rect.y, rect.width, rect.height)
164 && rect.width >= 0 && rect.height >= 0
165 ));
166 if (!controls.length || !rects.length) return null;
167 const distances = controls.map((point) => Math.min(
168 ...rects.map((rect) => pointDistanceFromRect(point, rect)),
169 ));
170 const maximum = Math.max(...distances);
171 return { maximum, point: controls[distances.indexOf(maximum)] };
172}
174function pointBlocked(point, obstacles) {
175 return obstacles.some((rect) => (
176 point[0] >= rect.x && point[0] <= rect.x + rect.width
177 && point[1] >= rect.y && point[1] <= rect.y + rect.height
178 ));
179}
181// Prune only against the candidate segment, never the route's initial bounds:
182// a later detour can still encounter any obstacle in the complete inventory.
183// Keep epsilon-near bounds for the existing exact predicates to decide.
184function segmentBlocked(start, end, obstacles) {
185 const minX = Math.min(start[0], end[0]);
186 const maxX = Math.max(start[0], end[0]);
187 const minY = Math.min(start[1], end[1]);
188 const maxY = Math.max(start[1], end[1]);
189 return obstacles.some((rect) => {
190 if (maxX < Math.min(rect.x, rect.x + rect.width) - 0.0001
191 || minX > Math.max(rect.x, rect.x + rect.width) + 0.0001
192 || maxY < Math.min(rect.y, rect.y + rect.height) - 0.0001
193 || minY > Math.max(rect.y, rect.y + rect.height) + 0.0001) return false;
194 return segmentIntersectsRect({ start, end }, rect);
195 });
196}
198function segmentConflictsWithAvoided(start, end, avoidedSegments, minimumOverlapPx, allowCrossings) {
199 const minX = Math.min(start[0], end[0]);
200 const maxX = Math.max(start[0], end[0]);
201 const minY = Math.min(start[1], end[1]);
202 const maxY = Math.max(start[1], end[1]);
203 return avoidedSegments.some((segment) => {
204 // A zero overlap threshold also rejects disjoint segments (0 >= 0).
205 if (minimumOverlapPx > 0 && (maxX < Math.min(segment.start[0], segment.end[0]) - 0.0001
206 || minX > Math.max(segment.start[0], segment.end[0]) + 0.0001
207 || maxY < Math.min(segment.start[1], segment.end[1]) - 0.0001
208 || minY > Math.max(segment.start[1], segment.end[1]) + 0.0001)) return false;
209 return (!allowCrossings && (properSegmentIntersection(start, end, segment.start, segment.end)
210 || orthogonalTouchOnAvoidedInterior(start, end, segment.start, segment.end)))
211 || collinearOverlap(start, end, segment.start, segment.end) >= minimumOverlapPx;
212 });
213}
215function orthogonalTouchOnAvoidedInterior(start, end, avoidedStart, avoidedEnd) {
216 const epsilon = 0.0001;
217 const candidateHorizontal = Math.abs(start[1] - end[1]) <= epsilon;
218 const candidateVertical = Math.abs(start[0] - end[0]) <= epsilon;
219 const avoidedHorizontal = Math.abs(avoidedStart[1] - avoidedEnd[1]) <= epsilon;
220 const avoidedVertical = Math.abs(avoidedStart[0] - avoidedEnd[0]) <= epsilon;
221 if (candidateHorizontal && avoidedVertical) {
222 const x = avoidedStart[0];
223 const y = start[1];
224 return x >= Math.min(start[0], end[0]) - epsilon
225 && x <= Math.max(start[0], end[0]) + epsilon
226 && y > Math.min(avoidedStart[1], avoidedEnd[1]) + epsilon
227 && y < Math.max(avoidedStart[1], avoidedEnd[1]) - epsilon;
228 }
229 if (candidateVertical && avoidedHorizontal) {
230 const x = start[0];
231 const y = avoidedStart[1];
232 return y >= Math.min(start[1], end[1]) - epsilon
233 && y <= Math.max(start[1], end[1]) + epsilon
234 && x > Math.min(avoidedStart[0], avoidedEnd[0]) + epsilon
235 && x < Math.max(avoidedStart[0], avoidedEnd[0]) - epsilon;
236 }
237 return false;
238}
240function pointOnSegmentInterior(point, start, end) {
241 const epsilon = 0.0001;
242 const cross = (end[0] - start[0]) * (point[1] - start[1])
243 - (end[1] - start[1]) * (point[0] - start[0]);
244 if (Math.abs(cross) > epsilon) return false;
245 const dot = (point[0] - start[0]) * (point[0] - end[0])
246 + (point[1] - start[1]) * (point[1] - end[1]);
247 return dot < -epsilon;
248}
250function pointOnAvoidedInterior(point, avoidedSegments) {
251 return avoidedSegments.some((segment) => (
252 pointOnSegmentInterior(point, segment.start, segment.end)
253 ));
254}
256function writeGridMetrics(metrics, patch) {
257 if (!metrics || typeof metrics !== 'object') return;
258 Object.assign(metrics, patch);
259}
261export function shortestOrthogonalGridRoute({
262 start,
263 end,
264 points,
265 obstacles,
266 fromSide,
267 toSide,
268 clearance,
269 maximumObstacleCount,
270 endpointStubPx = clearance + 2,
271 maximumGridNodes = Infinity,
272 avoidedSegments = [],
273 allowAvoidedCrossings = false,
274 minimumAvoidedOverlapPx = 8,
275 routeSeparationPx = 8,
276 minimumSegmentPx = 8,
277 borderSegments = [],
278 bendPenaltyPx = 0,
279 accept = () => true,
280 metrics,
281}) {
282 writeGridMetrics(metrics, {
283 status: 'initializing',
284 maximumGridNodes,
285 obstacleCount: 0,
286 avoidedSegmentCount: 0,
287 coordinateCount: 0,
288 candidateNodeCount: 0,
289 usableNodeCount: 0,
290 graphEdgeCount: 0,
291 visitedNodeCount: 0,
292 attemptCount: 0,
293 });
294 if (!OUTWARD[fromSide] || !OUTWARD[toSide]) {
295 writeGridMetrics(metrics, { status: 'unsupported-endpoint-side' });
296 return null;
297 }
298 const startStub = moveOutward(start, fromSide, endpointStubPx);
299 const endStub = moveOutward(end, toSide, endpointStubPx);
300 // The graph may legally leave the initial endpoint bounds to find a clear
301 // corridor. Keep every bounded obstacle and occupied relationship visible
302 // to that search; filtering them against the initial box lets a detour walk
303 // straight through geometry that only becomes relevant after it leaves the
304 // box. The explicit obstacle/node budgets below keep this deterministic.
305 const expanded = [...obstacles]
306 .filter((rect) => rect && isFinitePoint(rect.x, rect.y, rect.width, rect.height))
307 .map((rect) => expandedRect(rect, clearance));
308 const relevantAvoidedSegments = [...avoidedSegments]
309 .filter((segment) => segment?.start && segment?.end);
310 // Frame borders may be crossed perpendicularly but never borrowed as a
311 // corridor: the composition gate rejects any collinear run along them.
312 const relevantBorderSegments = [...borderSegments]
313 .filter((segment) => segment?.start && segment?.end);
314 writeGridMetrics(metrics, {
315 obstacleCount: expanded.length,
316 avoidedSegmentCount: relevantAvoidedSegments.length,
317 });
318 if (expanded.length > maximumObstacleCount) {
319 writeGridMetrics(metrics, { status: 'obstacle-budget-exceeded' });
320 return null;
321 }
323 const xs = new Set([startStub[0], endStub[0], ...points.map(([x]) => x)]);
324 const ys = new Set([startStub[1], endStub[1], ...points.map(([, y]) => y)]);
325 for (const rect of expanded) {
326 xs.add(rect.x - 1);
327 xs.add(rect.x + rect.width + 1);
328 ys.add(rect.y - 1);
329 ys.add(rect.y + rect.height + 1);
330 }
331 for (const segment of relevantAvoidedSegments) {
332 const [segmentStart, segmentEnd] = [segment.start, segment.end];
333 xs.add(segmentStart[0]);
334 xs.add(segmentEnd[0]);
335 ys.add(segmentStart[1]);
336 ys.add(segmentEnd[1]);
337 if (Math.abs(segmentStart[0] - segmentEnd[0]) <= 0.0001) {
338 xs.add(segmentStart[0] - routeSeparationPx);
339 xs.add(segmentStart[0] + routeSeparationPx);
340 }
341 if (Math.abs(segmentStart[1] - segmentEnd[1]) <= 0.0001) {
342 ys.add(segmentStart[1] - routeSeparationPx);
343 ys.add(segmentStart[1] + routeSeparationPx);
344 }
345 }
346 function addBorderCoordinates(distance) {
347 for (const segment of relevantBorderSegments) {
348 if (Math.abs(segment.start[0] - segment.end[0]) <= 0.0001) {
349 xs.add(segment.start[0] - distance);
350 xs.add(segment.start[0] + distance);
351 }
352 if (Math.abs(segment.start[1] - segment.end[1]) <= 0.0001) {
353 ys.add(segment.start[1] - distance);
354 ys.add(segment.start[1] + distance);
355 }
356 }
357 }
358 addBorderCoordinates(routeSeparationPx);
359 // Grid lines closer than a readable segment would let the search emit a
360 // micro jog between two obstacle edges; keep the endpoint stubs and coalesce
361 // the rest so every turn the route can take is at least one segment long.
362 const coalesce = (values, keep, fillGaps) => {
363 const sorted = values.sort((a, b) => a - b);
364 if (!fillGaps) return sorted.filter((value, index) => (
365 index === 0 || keep.has(value) || value - sorted[index - 1] >= minimumSegmentPx
366 ));
367 // A dense chain of discarded coordinates can erase a usable corridor.
368 // Compare with the last retained line while reserving readable spacing
369 // around the endpoint lines that must be kept.
370 return sorted.reduce((retained, value) => {
371 if (keep.has(value) || ((!retained.length || value - retained.at(-1) >= minimumSegmentPx)
372 && [...keep].every(endpoint => Math.abs(value - endpoint) >= minimumSegmentPx))) retained.push(value);
373 return retained;
374 }, []);
375 };
376 // Keep accepted routes stable. A failed or caller-rejected search can use
377 // the denser coordinate set, within the same original node budget.
378 let remainingGridNodes = maximumGridNodes;
379 for (let attempt = 0; attempt < 2; attempt += 1) {
380 // A pinned endpoint stub may land on a frame border. Nearby candidates
381 // closer than the minimum segment disappear during coalescing. Recovery
382 // adds a full-segment corridor without changing the attempt or node budget.
383 if (attempt > 0 && routeSeparationPx < minimumSegmentPx) addBorderCoordinates(minimumSegmentPx);
384 const orderedX = coalesce([...xs], new Set([startStub[0], endStub[0]]), attempt > 0);
385 const orderedY = coalesce([...ys], new Set([startStub[1], endStub[1]]), attempt > 0);
386 const candidateNodeCount = orderedX.length * orderedY.length;
387 writeGridMetrics(metrics, {
388 coordinateCount: (metrics?.coordinateCount || 0) + orderedX.length + orderedY.length,
389 candidateNodeCount: (metrics?.candidateNodeCount || 0) + candidateNodeCount,
390 attemptCount: attempt + 1,
391 });
392 if (candidateNodeCount > remainingGridNodes) {
393 writeGridMetrics(metrics, { status: 'node-budget-exceeded' });
394 return null;
395 }
396 remainingGridNodes -= candidateNodeCount;
397 const nodes = new Map();
398 for (const x of orderedX) {
399 for (const y of orderedY) {
400 const point = [x, y];
401 if (!pointBlocked(point, expanded)
402 && (allowAvoidedCrossings || !pointOnAvoidedInterior(point, relevantAvoidedSegments))) {
403 nodes.set(pointKey(point), point);
404 }
405 }
406 }
407 writeGridMetrics(metrics, { usableNodeCount: (metrics?.usableNodeCount || 0) + nodes.size });
408 if (!nodes.has(pointKey(startStub)) || !nodes.has(pointKey(endStub))) {
409 writeGridMetrics(metrics, { status: 'endpoint-blocked' });
410 return null;
411 }
413 const adjacency = new Map([...nodes.keys()].map((key) => [key, []]));
414 let graphEdgeCount = 0;
415 const connectLine = (line, axis) => {
416 for (let index = 0; index < line.length - 1; index += 1) {
417 const left = line[index];
418 const right = line[index + 1];
419 if (segmentBlocked(left, right, expanded)) continue;
420 if (segmentConflictsWithAvoided(
421 left,
422 right,
423 relevantAvoidedSegments,
424 minimumAvoidedOverlapPx,
425 allowAvoidedCrossings,
426 )) continue;
427 if (relevantBorderSegments.some((segment) => (
428 collinearOverlap(left, right, segment.start, segment.end) > 0.0001
429 ))) continue;
430 const distance = Math.abs(right[0] - left[0]) + Math.abs(right[1] - left[1]);
431 const leftKey = pointKey(left);
432 const rightKey = pointKey(right);
433 adjacency.get(leftKey).push([rightKey, distance, axis === 'h' ? 'R' : 'D']);
434 adjacency.get(rightKey).push([leftKey, distance, axis === 'h' ? 'L' : 'U']);
435 graphEdgeCount += 1;
436 }
437 };
438 for (const y of orderedY) {
439 connectLine(orderedX.map((x) => nodes.get(pointKey([x, y]))).filter(Boolean), 'h');
440 }
441 for (const x of orderedX) {
442 connectLine(orderedY.map((y) => nodes.get(pointKey([x, y]))).filter(Boolean), 'v');
443 }
444 writeGridMetrics(metrics, { graphEdgeCount: (metrics?.graphEdgeCount || 0) + graphEdgeCount });
446 // The search state carries the incoming direction so a turn can cost extra
447 // and a reversal is never taken: the pure shortest path hugs every obstacle
448 // corner with a staircase of short jogs, while a bend-penalised one takes
449 // the same corridor in a few long strokes. The first stub already leaves
450 // the endpoint along its side and the last one arrives along the end side.
451 const directionOf = ([dx, dy]) => (dx > 0 ? 'R' : dx < 0 ? 'L' : dy > 0 ? 'D' : 'U');
452 const opposite = { R: 'L', L: 'R', D: 'U', U: 'D' };
453 const stateKey = (key, direction) => `${key}|${direction}`;
454 const sourceAxis = directionOf(OUTWARD[fromSide]);
455 const targetAxis = opposite[directionOf(OUTWARD[toSide])];
456 const source = pointKey(startStub);
457 const target = pointKey(endStub);
458 const sourceState = stateKey(source, sourceAxis);
459 const distances = new Map([[sourceState, 0]]);
460 const previous = new Map();
461 const queue = new MinHeap();
462 queue.push(sourceState, 0);
463 let visitedNodeCount = 0;
464 let targetState = null;
465 while (queue.entries.length) {
466 const next = queue.pop();
467 const current = next.key;
468 const currentDistance = next.distance;
469 if (currentDistance !== distances.get(current)) continue;
470 visitedNodeCount += 1;
471 const [currentNode, currentAxis] = current.split('|');
472 if (currentNode === target) {
473 // The end stub is outside the graph: never reverse back onto it.
474 if (currentAxis === opposite[targetAxis]) continue;
475 // Arriving on the wrong axis costs one final turn onto the end stub.
476 const arrival = currentDistance + (currentAxis === targetAxis ? 0 : bendPenaltyPx);
477 if (targetState == null || arrival < targetState.distance) {
478 targetState = { key: current, distance: arrival };
479 }
480 if (currentAxis === targetAxis || bendPenaltyPx === 0) break;
481 continue;
482 }
483 if (targetState && currentDistance >= targetState.distance) break;
484 for (const [neighbor, weight, axis] of adjacency.get(currentNode) || []) {
485 if (axis === opposite[currentAxis]) continue;
486 const candidate = currentDistance + weight + (axis === currentAxis ? 0 : bendPenaltyPx);
487 const neighborState = stateKey(neighbor, axis);
488 if (candidate >= (distances.get(neighborState) ?? Infinity)) continue;
489 distances.set(neighborState, candidate);
490 previous.set(neighborState, current);
491 queue.push(neighborState, candidate);
492 }
493 }
494 writeGridMetrics(metrics, { visitedNodeCount: (metrics?.visitedNodeCount || 0) + visitedNodeCount });
495 if (!targetState) {
496 writeGridMetrics(metrics, { status: 'no-route' });
497 continue;
498 }
499 const reversed = [];
500 for (let key = targetState.key; key; key = previous.get(key)) {
501 reversed.push(nodes.get(key.split('|')[0]));
502 if (key === sourceState) break;
503 }
504 if (pointKey(reversed.at(-1)) !== source) {
505 writeGridMetrics(metrics, { status: 'broken-predecessor-chain' });
506 return null;
507 }
508 const shortestPoints = normalizeRoutePoints([start, ...reversed.reverse(), end]);
509 if (!accept(shortestPoints)) {
510 writeGridMetrics(metrics, { status: 'rejected' });
511 continue;
512 }
513 writeGridMetrics(metrics, { status: 'routed' });
514 return {
515 points: shortestPoints,
516 length: orthogonalLength(shortestPoints),
517 obstacleCount: expanded.length,
518 };
519 }
520 return null;
521}
523function collinearOverlap(leftStart, leftEnd, rightStart, rightEnd) {
524 if (leftStart[0] === leftEnd[0] && rightStart[0] === rightEnd[0]
525 && leftStart[0] === rightStart[0]) {
526 return Math.max(0, Math.min(Math.max(leftStart[1], leftEnd[1]), Math.max(rightStart[1], rightEnd[1]))
527 - Math.max(Math.min(leftStart[1], leftEnd[1]), Math.min(rightStart[1], rightEnd[1])));
528 }
529 if (leftStart[1] === leftEnd[1] && rightStart[1] === rightEnd[1]
530 && leftStart[1] === rightStart[1]) {
531 return Math.max(0, Math.min(Math.max(leftStart[0], leftEnd[0]), Math.max(rightStart[0], rightEnd[0]))
532 - Math.max(Math.min(leftStart[0], leftEnd[0]), Math.min(rightStart[0], rightEnd[0])));
533 }
534 return 0;
535}
537function segmentOutsideContent(start, end, contentBounds) {
538 if (!contentBounds) return false;
539 const midpoint = [(start[0] + end[0]) / 2, (start[1] + end[1]) / 2];
540 return midpoint[0] < contentBounds.left || midpoint[0] > contentBounds.right
541 || midpoint[1] < contentBounds.top || midpoint[1] > contentBounds.bottom;
542}
544function sharesOuterCorridor({ relation, relations, pathFor, points, contentBounds, minimumOverlap }) {
545 for (const other of asArray(relations)) {
546 if (!other || other === relation) continue;
547 const related = relation.from === other.from || relation.from === other.to
548 || relation.to === other.from || relation.to === other.to;
549 if (!related) continue;
550 const otherPoints = normalizeRoutePoints(pathFor(other)?.points || []);
551 for (let left = 0; left < points.length - 1; left += 1) {
552 if (!segmentOutsideContent(points[left], points[left + 1], contentBounds)) continue;
553 for (let right = 0; right < otherPoints.length - 1; right += 1) {
554 if (collinearOverlap(points[left], points[left + 1], otherPoints[right], otherPoints[right + 1]) >= minimumOverlap) {
555 return true;
556 }
557 }
558 }
559 }
560 return false;
561}
563function relationshipSubject(diagramType, relationCollection, relationIndex, relation) {
564 return {
565 diagramType,
566 collection: relationCollection,
567 index: relationIndex,
568 ...(relation.id ? { id: relation.id } : {}),
569 from: relation.from,
570 to: relation.to,
571 };
572}
574/**
575 * Reject conspicuous authored detours without penalizing routes whose length is
576 * explained by opaque-node avoidance or a related shared outer corridor.
577 */
578export function cleanRouteDetourProblems({
579 relations,
580 obstacles,
581 contentRects = obstacles,
582 endpointIds,
583 pathFor,
584 fromSideFor,
585 toSideFor,
586 diagramType,
587 relationCollection,
588 profile,
589 thresholds = {},
590}) {
591 if (profile !== 'showcase') return [];
592 const policy = { ...DEFAULTS, ...thresholds };
593 const obstacleList = [...obstacles];
594 const contentBounds = boundsForRects(contentRects);
595 const problems = [];
596 for (const [relationIndex, relation] of asArray(relations).entries()) {
597 if (!relation || !endpointIds?.has(relation.from) || !endpointIds?.has(relation.to)) continue;
598 if (!Array.isArray(relation.via) || relation.via.length === 0) continue;
599 const points = normalizeRoutePoints(pathFor(relation)?.points || []);
600 if (points.length < 3 || !points.every((point) => Array.isArray(point) && isFinitePoint(...point))) continue;
601 const actualLength = orthogonalLength(points);
602 if (!Number.isFinite(actualLength)) continue;
603 const start = points[0];
604 const end = points.at(-1);
605 const manhattan = Math.abs(end[0] - start[0]) + Math.abs(end[1] - start[1]);
606 if (actualLength < manhattan * policy.minimumDetourRatio
607 || actualLength - manhattan < policy.minimumExcessLengthPx) continue;
608 const routeBounds = boundsForPoints(points);
609 const excursion = outsideExcursion(routeBounds, contentBounds);
610 const emptyClearance = emptyControlPointClearance(points, obstacleList);
611 if (Math.max(excursion?.maximum || 0, emptyClearance?.maximum || 0)
612 < policy.minimumEmptyExcursionPx) continue;
613 if (sharesOuterCorridor({
614 relation,
615 relations,
616 pathFor,
617 points,
618 contentBounds,
619 minimumOverlap: policy.sharedCorridorMinimumPx,
620 })) continue;
622 const fromSide = fromSideFor?.(relation) || inferredSide(points, 'source');
623 const toSide = toSideFor?.(relation) || inferredSide(points, 'target');
624 const shortest = shortestOrthogonalGridRoute({
625 start,
626 end,
627 points,
628 obstacles: obstacleList,
629 fromSide,
630 toSide,
631 clearance: policy.clearance,
632 maximumObstacleCount: policy.maximumObstacleCount,
633 });
634 if (!shortest || !Number.isFinite(shortest.length) || shortest.length <= 0) continue;
635 const detourRatio = actualLength / shortest.length;
636 const excessLength = actualLength - shortest.length;
637 if (detourRatio < policy.minimumDetourRatio || excessLength < policy.minimumExcessLengthPx) continue;
639 const relationId = relation.id ? ` id "${relation.id}"` : '';
640 const message = `[composition/excessive-route-detour] ${diagramType} ${relationCollection}[${relationIndex}]${relationId} "${relation.from}" -> "${relation.to}" travels ${Math.round(actualLength)}px, ${rounded(detourRatio)}x the ${Math.round(shortest.length)}px shortest obstacle-clearing orthogonal route, and reaches ${Math.round(excursion.maximum)}px beyond the content bounds — remove the distant via corridor or move it close to the connected content.`;
641 const supportedFix = 'remove the distant via points and retry automatic routing, or keep the endpoint sides and move the via corridor near the connected nodes while preserving labels and direction';
642 recordDiagnostic({
643 code: 'composition/excessive-route-detour',
644 severity: 'error',
645 message,
646 subject: relationshipSubject(diagramType, relationCollection, relationIndex, relation),
647 evidence: {
648 points,
649 actualLengthPx: rounded(actualLength),
650 shortestLegalPoints: shortest.points,
651 shortestLegalLengthPx: rounded(shortest.length),
652 detourRatio: rounded(detourRatio),
653 excessLengthPx: rounded(excessLength),
654 routeBounds,
655 contentBounds,
656 emptyExcursionPx: excursion,
657 emptyControlPointClearancePx: emptyClearance,
658 obstacleCount: shortest.obstacleCount,
659 thresholds: {
660 minimumDetourRatio: policy.minimumDetourRatio,
661 minimumExcessLengthPx: policy.minimumExcessLengthPx,
662 minimumEmptyExcursionPx: policy.minimumEmptyExcursionPx,
663 },
664 },
665 supportedFixes: [supportedFix],
666 });
667 problems.push(message);
668 }
669 return problems;
670}