joint-label-routing.mjs
165 lines · archify/renderers/dataflow/joint-label-routing.mjs at a406594
1import {
2 automaticPortRhythmBridge, collectAmbiguousCorridors, collectBorderRuns,
3 collectRouteRhythmIssues, frameBorderSegments, normalizeRoutePoints,
4 properSegmentIntersection, rectsOverlap, routeHonorsEndpointSides,
5 segmentIntersectsRect, segmentRectClearanceWithin,
6} from '../shared/geometry.mjs';
7import { shortestOrthogonalGridRoute } from '../shared/route-quality.mjs';
9const segments = points => points.slice(1).map((end, index) => ({ start: points[index], end }));
10const related = (a, b) => [a.from, a.to].some(id => id === b.from || id === b.to);
11const length = points => segments(points).reduce((sum, { start, end }) => sum
12 + Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]), 0);
13const distance = (points, rect, limit = 36) => Math.min(...segments(points)
14 .map(segment => segmentRectClearanceWithin(segment, rect, limit)));
15const masks = (points, rect) => distance(points, rect, 4) + 0.0001 < 4;
16const pinned = flow => flow.via || (flow.route && flow.route !== 'auto')
17 || ['fromSide', 'toSide', 'channelX', 'channelY', 'labelAt', 'labelDx', 'labelDy', 'labelSegment']
18 .some(key => flow[key] !== undefined);
19const crossingCount = (a, b) => segments(a).reduce((sum, s) => sum + segments(b)
20 .filter(t => properSegmentIntersection(s.start, s.end, t.start, t.end)).length, 0);
21// One complete label, its own bridge, and the few routes blocking its slot
22// are a single proposal. Nothing is applied until all the geometry clears.
23// Keep all endpoint coordinates and every other label fixed.
24export function repairLabelRoutes({ labels, routes, nodes, titles, frames, viewBox,
25 placementBottom, sideFor, maximumSearches = 32, metrics = {} }) {
26 if (nodes.length + titles.length + labels.length - 1 > 80) {
27 Object.assign(metrics, { searches: 0, maximumSearches, changedLabels: 0, changedRoutes: 0 });
28 return { labels, routes };
29 }
30 let currentLabels = labels, currentRoutes = routes;
31 let searches = 0;
32 const rectangles = [...nodes, ...titles];
33 const borderSegments = frames.flatMap(frameBorderSegments);
34 const clearRect = (rect, index) => rect.x >= 0 && rect.y >= 0
35 && rect.x + rect.width <= viewBox[0] && rect.y + rect.height <= placementBottom
36 && !rectangles.some(node => rectsOverlap(rect, node, 2))
37 && !currentLabels.some((other, i) => i !== index && rectsOverlap(rect, other, 2));
38 const intrudes = (route, points) => nodes.some(node => segments(points).some((segment, index) => (
39 !((node.id === route.relation.from && index === 0)
40 || (node.id === route.relation.to && index === points.length - 2))
41 && segmentIntersectsRect(segment, node, 2)
42 )));
43 const routeClear = (route, points, nextLabels, nextRoutes, bottom) => {
44 const { fromSide, toSide } = sideFor(route.relation);
45 return routeHonorsEndpointSides(points, fromSide, toSide)
46 && points.every(([x, y]) => x >= 0 && y >= 0 && x <= viewBox[0] && y <= bottom)
47 && !intrudes(route, points)
48 && !collectRouteRhythmIssues({ routedRelations: [{ points }] }).length
49 && !collectBorderRuns({ routedRelations: [{ points }], frames }).some(hit => hit.side !== 'bottom')
50 && !nextLabels.some(rect => rect.relationIndex !== route.relationIndex && masks(points, rect))
51 && nextLabels.filter(rect => rect.relationIndex === route.relationIndex).every(rect => distance(points, rect) <= 36)
52 && nextRoutes.every(other => other.relationIndex === route.relationIndex
53 || !pinned(other.relation) || crossingCount(points, other.points) === 0)
54 && nextRoutes.every(other => other.relationIndex === route.relationIndex
55 || !collectAmbiguousCorridors({ routedRelations: [{ ...route, points }, other],
56 includeSharedEndpoints: () => true }).length
57 || collectAmbiguousCorridors({ routedRelations: [route, currentRoutes.find(r => r.relationIndex === other.relationIndex)],
58 includeSharedEndpoints: () => true }).length > 0);
59 };
60 for (const [labelIndex, label] of currentLabels.entries()) {
61 if (searches >= maximumSearches) break;
62 const own = currentRoutes.find(route => route.relationIndex === label.relationIndex);
63 if (!own || pinned(own.relation)
64 || (!currentRoutes.some(route => route !== own && masks(route.points, label))
65 && !nodes.some(node => rectsOverlap(label, node, -2)))) continue;
66 const { fromSide, toSide } = sideFor(own.relation);
67 const ownOptions = new Map([[JSON.stringify(own.points), own.points]]);
68 for (const endpointStubPx of [24, 16]) automaticPortRhythmBridge(own.points[0], own.points.at(-1), fromSide, toSide, {
69 endpointStubPx, accept: points => { ownOptions.set(JSON.stringify(points), points); return false; },
70 });
71 const xs = new Set([label.x]), ys = new Set([label.y]);
72 for (const points of ownOptions.values()) for (const { start, end } of segments(points)) {
73 for (const x of [start[0], end[0], (start[0] + end[0]) / 2]) xs.add(x - label.width / 2);
74 for (const y of [start[1], end[1], (start[1] + end[1]) / 2]) {
75 ys.add(y - label.height - 4); ys.add(y + 4);
76 }
77 }
78 const neighbours = [...rectangles, ...currentLabels.filter((_, index) => index !== labelIndex)];
79 for (const rect of neighbours) {
80 xs.add(rect.x - label.width - 2); xs.add(rect.x + rect.width + 2);
81 ys.add(rect.y - label.height - 2); ys.add(rect.y + rect.height + 2);
82 }
83 for (const route of currentRoutes) for (const { start, end } of segments(route.points)) {
84 if (start[0] === end[0]) { xs.add(start[0] - label.width - 8); xs.add(start[0] + 8); }
85 if (start[1] === end[1]) { ys.add(start[1] - label.height - 8); ys.add(start[1] + 8); }
86 }
87 const xPoints = [...ownOptions.values()].flatMap(points => points.map(point => point[0]));
88 const yPoints = [...ownOptions.values()].flatMap(points => points.map(point => point[1]));
89 const candidates = [];
90 for (const x of xs) {
91 if (x + label.width < Math.min(...xPoints) - 36 || x > Math.max(...xPoints) + 36) continue;
92 for (const y of ys) {
93 if (y + label.height < Math.min(...yPoints) - 36 || y > Math.max(...yPoints) + 36) continue;
94 const rect = { ...label, x, y, lx: x + label.width / 2, ly: y + (label.ly - label.y) };
95 if (!clearRect(rect, labelIndex)) continue;
96 for (const points of ownOptions.values()) {
97 const ownDistance = distance(points, rect);
98 if (ownDistance < 4 || ownDistance > 36) continue;
99 const nextLabels = currentLabels.map((other, index) => index === labelIndex ? rect : other);
100 if (!routeClear(own, points, nextLabels, currentRoutes, placementBottom)) continue;
101 const blocked = currentRoutes.filter(route => route !== own && masks(route.points, rect));
102 if (blocked.length > 4 || blocked.some(route => pinned(route.relation))) continue;
103 const stableDistance = Math.min(...currentRoutes.filter(route => route !== own && !blocked.includes(route))
104 .map(route => distance(route.points, rect)));
105 if (ownDistance > stableDistance + 0.0001) continue;
106 candidates.push({ rect, points, blocked, ownDistance, move: Math.hypot(x - label.x, y - label.y) });
107 }
108 }
109 }
110 candidates.sort((a, b) => a.blocked.length - b.blocked.length || a.ownDistance - b.ownDistance || a.move - b.move);
111 const chosen = [];
112 // Avoid spending every search on virtually identical neighbouring slots.
113 for (const c of candidates) {
114 if (chosen.some(other => Math.hypot(c.rect.x - other.rect.x, c.rect.y - other.rect.y) < 8
115 && JSON.stringify(c.points) === JSON.stringify(other.points))) continue;
116 chosen.push(c); if (chosen.length >= 16) break;
117 }
118 let accepted = null;
119 for (const candidate of chosen) {
120 if (searches >= maximumSearches) break;
121 const nextLabels = currentLabels.map((other, index) => index === labelIndex ? candidate.rect : other);
122 const nextRoutes = currentRoutes.map(route => route === own ? { ...route, points: candidate.points } : route);
123 // Free the longest occupied corridor first. Each subsequent route sees
124 // the accepted proposal; all unchanged routes remain obstacles.
125 const blocked = [...candidate.blocked].sort((a, b) => length(b.points) - length(a.points));
126 let failed = false;
127 for (const old of blocked) {
128 if (searches >= maximumSearches) { failed = true; break; }
129 searches++;
130 const { fromSide, toSide } = sideFor(old.relation);
131 const obstacles = [
132 ...nodes.map(node => [old.relation.from, old.relation.to].includes(node.id) ? node : {
133 ...node, x: node.x - 12, y: node.y - 12, width: node.width + 24, height: node.height + 24,
134 }), ...titles,
135 ...nextLabels.filter(rect => rect.relationIndex !== old.relationIndex).map(rect => ({
136 ...rect, x: rect.x - 2, y: rect.y - 2, width: rect.width + 4, height: rect.height + 4,
137 })),
138 ];
139 const found = shortestOrthogonalGridRoute({ start: old.points[0], end: old.points.at(-1),
140 points: [old.points[0], old.points.at(-1)], fromSide, toSide, obstacles,
141 clearance: 2, maximumObstacleCount: 80, endpointStubPx: 24, maximumGridNodes: 4096,
142 avoidedSegments: nextRoutes.filter(other => other.relationIndex !== old.relationIndex
143 && !related(old.relation, other.relation)).flatMap(other => segments(other.points)),
144 allowAvoidedCrossings: true, minimumAvoidedOverlapPx: 8, routeSeparationPx: 8,
145 minimumSegmentPx: 16, bendPenaltyPx: 48, borderSegments,
146 accept: points => routeClear(old, points, nextLabels, nextRoutes, placementBottom + label.height),
147 });
148 const points = found && normalizeRoutePoints(found.points);
149 if (!points) { failed = true; break; }
150 nextRoutes[nextRoutes.findIndex(route => route.relationIndex === old.relationIndex)] = { ...old, points };
151 }
152 if (failed) continue;
153 const foreignDistance = Math.min(...nextRoutes.filter(route => route.relationIndex !== own.relationIndex)
154 .map(route => distance(route.points, candidate.rect)));
155 // The original label is invalid. A collision-free repair may need a longer
156 // corridor; never rank that invalid geometry above a valid proposal.
157 if (candidate.ownDistance > foreignDistance + 0.0001) continue;
158 accepted = { labels: nextLabels, routes: nextRoutes }; break;
159 }
160 if (accepted) { currentLabels = accepted.labels; currentRoutes = accepted.routes; }
161 }
162 Object.assign(metrics, { searches, maximumSearches, changedLabels: currentLabels.filter((rect, i) => rect !== labels[i]).length,
163 changedRoutes: currentRoutes.filter((route, i) => route !== routes[i]).length });
164 return { labels: currentLabels, routes: currentRoutes };
165}