automatic-labels.mjs
290 lines · archify/renderers/shared/automatic-labels.mjs at a406594
1import { normalizeRoutePoints, rectsOverlap, segmentRectClearanceWithin } from './geometry.mjs';
2import { createSpatialGrid } from './spatial-grid.mjs';
4// A bounded fallback for an unpinned label whose usual position collides.
5// It never routes an edge, moves a node, expands the canvas, or rewrites input.
6export function placeAutomaticLabels({
7 labels, routes, components, titles, viewBox, placementBottom = viewBox[1], fallbackRing = true, keepFallbackNearRoute = false,
8 gridSweep = false, maxOwnRouteDistance = Infinity,
9}) {
10 const placed = [...labels];
11 const obstacles = [...components, ...titles];
12 const segments = routes.flatMap(({ relationIndex, points }) => {
13 const normalized = normalizeRoutePoints(points);
14 return normalized.slice(1).map((end, index) => ({ relationIndex, start: normalized[index], end }));
15 });
16 const inside = rect => (
17 rect.x >= 0 && rect.y >= 0
18 && rect.x + rect.width <= viewBox[0] && rect.y + rect.height <= viewBox[1]
19 );
20 // The mask test asked every segment about every candidate position. Segments
21 // go into a uniform grid once, and a candidate only asks the cells it covers.
22 const SEGMENT_CELL = 120;
23 const segmentGrid = createSpatialGrid(SEGMENT_CELL);
24 for (const segment of segments) {
25 const [sx, sy] = segment.start;
26 const [ex, ey] = segment.end;
27 segmentGrid.insert({
28 minX: Math.min(sx, ex), maxX: Math.max(sx, ex),
29 minY: Math.min(sy, ey), maxY: Math.max(sy, ey),
30 }, segment);
31 }
32 const segmentsNear = (rect, margin) => segmentGrid.query({
33 minX: rect.x - margin, maxX: rect.x + rect.width + margin,
34 minY: rect.y - margin, maxY: rect.y + rect.height + margin,
35 });
36 const masksRoute = rect => {
37 for (const segment of segmentsNear(rect, 4)) {
38 if (segment.relationIndex === rect.relationIndex) continue;
39 if (segmentRectClearanceWithin(segment, rect, 4) + 0.0001 < 4) return true;
40 }
41 return false;
42 };
43 const overlapsLabel = (rect, index, gap = 0) => placed.some((other, otherIndex) => (
44 otherIndex !== index && rectsOverlap(rect, other, gap)
45 ));
46 const clear = (rect, index) => (
47 inside(rect) && rect.y + rect.height <= placementBottom
48 && !obstacles.some(obstacle => rectsOverlap(rect, obstacle, 2))
49 && !overlapsLabel(rect, index, 2) && !masksRoute(rect)
50 && (!Number.isFinite(maxOwnRouteDistance) || segments.some(segment =>
51 segment.relationIndex === rect.relationIndex
52 && segmentRectClearanceWithin(segment, rect, maxOwnRouteDistance) <= maxOwnRouteDistance))
53 );
54 const rectAt = (label, lx, ly) => ({
55 ...label, lx, ly, x: lx - label.width / 2, y: ly - 10,
56 });
57 // Fixed fractions can miss a narrow free slot. Try the ends of the free
58 // intervals beside an orthogonal segment, using obstacle edges rather
59 // than a finer sampling grid. The ordinary clearance test still decides
60 // whether a candidate is usable; this search never changes geometry.
61 const slidingCandidates = (label, index, { start: a, end: b }) => {
62 const horizontal = Math.abs(a[1] - b[1]) < 0.0001;
63 if (!horizontal && Math.abs(a[0] - b[0]) >= 0.0001) return [];
64 const axis = horizontal ? 'x' : 'y';
65 const size = horizontal ? 'width' : 'height';
66 const across = horizontal ? 'y' : 'x';
67 const crossSize = horizontal ? 'height' : 'width';
68 const low = Math.min(a[horizontal ? 0 : 1], b[horizontal ? 0 : 1]) + 8;
69 const high = Math.max(a[horizontal ? 0 : 1], b[horizontal ? 0 : 1]) - label[size] - 8;
70 if (high < low) return [];
71 const offsets = horizontal
72 ? [a[1] - 20, a[1] + 10, a[1] - 28, a[1] + 18]
73 : [a[0] - label.width - 6, a[0] + 6, a[0] - label.width - 14, a[0] + 14];
74 return offsets.flatMap(offset => {
75 const band = { ...label, [axis]: low, [size]: high - low + label[size], [across]: offset };
76 const blockers = [
77 ...obstacles.map(rect => ({ rect, gap: 2 })),
78 ...placed.filter((_, otherIndex) => otherIndex !== index).map(rect => ({ rect, gap: 2 })),
79 ...segmentsNear(band, 4).filter(segment => segment.relationIndex !== label.relationIndex).map(segment => ({
80 rect: {
81 x: Math.min(segment.start[0], segment.end[0]), y: Math.min(segment.start[1], segment.end[1]),
82 width: Math.abs(segment.end[0] - segment.start[0]), height: Math.abs(segment.end[1] - segment.start[1]),
83 }, gap: 4,
84 })),
85 ];
86 const positions = [Math.max(low, Math.min(high, label[axis])), low, high];
87 for (const { rect, gap } of blockers) {
88 if (offset + label[crossSize] + gap <= rect[across]
89 || rect[across] + rect[crossSize] + gap <= offset) continue;
90 positions.push(rect[axis] - gap - label[size], rect[axis] + rect[size] + gap);
91 }
92 return [...new Set(positions)].filter(position => position >= low && position <= high)
93 .sort((left, right) => Math.abs(left - label[axis]) - Math.abs(right - label[axis]))
94 .map(position => {
95 const rect = { ...label, [axis]: position, [across]: offset };
96 return rectAt(label, rect.x + label.width / 2, rect.y + 10);
97 });
98 });
99 };
100 // An opted-in grid layout runs parallel lines through shared gaps. Rank
101 // every position along all of the label's own segments: beside the line
102 // first, then centred on its own line (the plate interrupts only that
103 // line), then stepping outward past neighbouring parallels.
104 const gridCandidates = (label) => {
105 const fractions = [0.5, 0.25, 0.75, 0.375, 0.625, 0.125, 0.875];
106 const ranked = [];
107 // A close parallel of another relationship on one side (a reciprocal
108 // pair) makes a label on that side read as the neighbour's: prefer the
109 // far side.
110 const parallelOnLowSide = (a, b, axis) => {
111 const across = 1 - axis;
112 const [low, high] = [Math.min(a[axis], b[axis]), Math.max(a[axis], b[axis])];
113 let nearest = null;
114 for (const other of segments) {
115 if (other.relationIndex === label.relationIndex) continue;
116 if (Math.abs(other.start[across] - other.end[across]) > 0.0001) continue;
117 const distance = other.start[across] - a[across];
118 if (Math.abs(distance) < 0.0001 || Math.abs(distance) > 36) continue;
119 const overlap = Math.min(high, Math.max(other.start[axis], other.end[axis]))
120 - Math.max(low, Math.min(other.start[axis], other.end[axis]));
121 if (overlap <= 0) continue;
122 if (nearest === null || Math.abs(distance) < Math.abs(nearest)) nearest = distance;
123 }
124 return nearest !== null && nearest < 0;
125 };
126 for (const { start: a, end: b } of segments.filter(segment => segment.relationIndex === label.relationIndex)) {
127 if (Math.abs(a[1] - b[1]) < 0.0001 && Math.abs(a[0] - b[0]) >= label.width + 16) {
128 const [above, below] = parallelOnLowSide(a, b, 0) ? [1, 0] : [0, 1];
129 for (const fraction of fractions) {
130 const x = a[0] + (b[0] - a[0]) * fraction;
131 if (Math.min(Math.abs(x - a[0]), Math.abs(x - b[0])) < label.width / 2 + 6) continue;
132 ranked.push([above, x, a[1] - 10], [below, x, a[1] + 20], [2, x, a[1] + 3], [3, x, a[1] - 18], [3, x, a[1] + 28]);
133 }
134 } else if (Math.abs(a[0] - b[0]) < 0.0001 && Math.abs(a[1] - b[1]) >= label.height + 16) {
135 const leftFirst = !parallelOnLowSide(a, b, 1);
136 for (const fraction of fractions) {
137 const y = a[1] + (b[1] - a[1]) * fraction;
138 if (Math.min(Math.abs(y - a[1]), Math.abs(y - b[1])) < label.height / 2 + 6) continue;
139 ranked.push([2, a[0], y + 3]);
140 [6, 14, 22, 30, 38, 46, 54].forEach((offset, step) => {
141 const tier = step === 0 ? 0 : step === 1 ? 1 : 2 + step;
142 const left = [tier + (leftFirst ? 0 : 0.5), a[0] - label.width / 2 - offset, y + 3];
143 const right = [tier + (leftFirst ? 0.5 : 0), a[0] + label.width / 2 + offset, y + 3];
144 ranked.push(left, right);
145 });
146 }
147 }
148 }
149 return ranked.map((entry, order) => [...entry, order])
150 .sort((left, right) => left[0] - right[0] || left[3] - right[3])
151 .map(([, lx, ly]) => [lx, ly]);
152 };
154 const pinned = label => ['labelAt', 'labelDx', 'labelDy', 'labelSegment']
155 .some(key => label.relation[key] !== undefined);
156 const needsPlacement = (label, index) => !inside(label)
157 || components.some(component => rectsOverlap(label, component, -2))
158 || titles.some(title => rectsOverlap(label, title))
159 || overlapsLabel(label, index) || masksRoute(label);
160 const placeLabel = (index, rerank) => {
161 const label = placed[index];
162 // Match actual defect thresholds before searching; a valid placement is
163 // not a reason to restyle the diagram. New placements leave extra space.
164 // The grid ranking already starts from the preferred position, so it
165 // also re-ranks labels whose default spot is merely valid.
166 if (!rerank && !needsPlacement(label, index)) return;
167 if (rerank) {
168 // Callers measure the plate one pixel higher than rectAt; test with a
169 // pixel of slack so the chosen position also passes their clearance.
170 const replacement = gridCandidates(label).map(([lx, ly]) => rectAt(label, lx, ly))
171 .find(rect => clear({ ...rect, x: rect.x - 1, y: rect.y - 1, width: rect.width + 2, height: rect.height + 2 }, index));
172 if (replacement) {
173 placed[index] = replacement;
174 return;
175 }
176 }
177 for (const segment of segments.filter(segment => segment.relationIndex === label.relationIndex)) {
178 const [a, b] = [segment.start, segment.end];
179 let candidates = [];
180 // These candidates sit beside the line. They need the same 2px node
181 // clearance checked by clear(), not 8px reserved at each endpoint.
182 // Extra endpoint padding can hide a valid outer slot for a reciprocal
183 // pair and make the planner send its other arrow around both nodes.
184 if (Math.abs(a[1] - b[1]) < 0.0001 && Math.abs(a[0] - b[0]) >= label.width + 4) {
185 candidates = [0.5, 0.25, 0.75, 0.125, 0.875].flatMap(fraction => {
186 const x = a[0] + (b[0] - a[0]) * fraction;
187 if (Math.min(Math.abs(x - a[0]), Math.abs(x - b[0])) < 8) return [];
188 return [
189 [x, a[1] - 10],
190 [x, a[1] + 20],
191 [x, a[1] - 18],
192 [x, a[1] + 28],
193 ];
194 });
195 } else if (Math.abs(a[0] - b[0]) < 0.0001 && Math.abs(a[1] - b[1]) >= label.height + 16) {
196 candidates = [0.5, 0.25, 0.75, 0.125, 0.875].flatMap(fraction => {
197 const y = a[1] + (b[1] - a[1]) * fraction;
198 if (Math.min(Math.abs(y - a[1]), Math.abs(y - b[1])) < 8) return [];
199 return [
200 [a[0] - label.width / 2 - 6, y + 3],
201 [a[0] + label.width / 2 + 6, y + 3],
202 [a[0] - label.width / 2 - 14, y + 3],
203 [a[0] + label.width / 2 + 14, y + 3],
204 ];
205 });
206 }
207 const replacement = candidates.map(([lx, ly]) => rectAt(label, lx, ly))
208 .find(rect => clear(rect, index));
209 if (replacement) {
210 placed[index] = replacement;
211 break;
212 }
213 }
214 if (placed[index] !== label) return;
215 const sliding = segments.filter(segment => segment.relationIndex === label.relationIndex)
216 .flatMap(segment => slidingCandidates(label, index, segment)).find(rect => clear(rect, index));
217 if (sliding) {
218 placed[index] = sliding;
219 return;
220 }
221 if (!fallbackRing) return;
223 // Dense but valid topologies can leave every point directly beside the
224 // relationship occupied by another route. Search a small deterministic
225 // ring around the current anchor and the relationship's segment centres.
226 // A collision-free island above a node is not a readable edge label.
227 // Architecture opts into keeping the mask within two label heights of
228 // its own route; shared callers retain their existing policy. If no nearby
229 // slot fits, retain the collision so validation can request more space.
230 const ownSegments = segments.filter(segment => segment.relationIndex === label.relationIndex);
231 const baseAnchors = [
232 [label.lx, label.ly],
233 ...ownSegments.map(segment => [
234 (segment.start[0] + segment.end[0]) / 2,
235 (segment.start[1] + segment.end[1]) / 2,
236 ]),
237 ];
238 const horizontalStep = label.width / 2 + 12;
239 const ringOffsets = [
240 [0, -28], [0, 38],
241 [-horizontalStep, -28], [horizontalStep, -28],
242 [-horizontalStep, 38], [horizontalStep, 38],
243 [-(label.width + 20), -52], [label.width + 20, -52],
244 [-(label.width + 20), 62], [label.width + 20, 62],
245 [-(label.width + 20), -76], [label.width + 20, -76],
246 [-(label.width + 20), 86], [label.width + 20, 86],
247 ];
248 const fallback = baseAnchors.flatMap(([baseX, baseY]) => (
249 ringOffsets.map(([dx, dy]) => rectAt(label, baseX + dx, baseY + dy))
250 )).find(rect => clear(rect, index) && (!keepFallbackNearRoute || ownSegments.some(segment => (
251 segmentRectClearanceWithin(segment, rect, label.height * 2) <= label.height * 2
252 ))));
253 if (fallback) placed[index] = fallback;
254 };
255 let pending = placed.map((_, index) => index).filter(index => !pinned(placed[index]));
256 // A later label can vacate the only slot available to an earlier one.
257 // Retry only unresolved labels after a move; accepted placements clear all
258 // current labels and fixed geometry, so each success retires one label.
259 // A stalled pass ends the search, with at most one pass per input label.
260 for (let pass = 0; pass < labels.length && pending.length; pass++) {
261 let moved = false;
262 for (const index of pending) {
263 const before = placed[index];
264 placeLabel(index, gridSweep && pass === 0);
265 moved ||= placed[index] !== before;
266 }
267 if (!moved) break;
268 pending = pending.filter(index => needsPlacement(placed[index], index));
269 }
270 return placed;
271}
273// The rect a single unpinned label would occupy given only its own route and
274// the nodes: what the planner reserves before the remaining routes are laid.
275// Only a placement beside the route itself is worth reserving; a label that
276// would already need the fallback ring is left to the final placement pass.
277export function reservedLabelRect({
278 label, points, routes = [], labels = [], components, viewBox = [Infinity, Infinity], placementBottom = Infinity,
279}) {
280 const [rect] = placeAutomaticLabels({
281 labels: [{ ...label, relationIndex: -1 }, ...labels.map(other => ({ ...other, relationIndex: -2 }))],
282 routes: [{ relationIndex: -1, points }, ...routes],
283 components,
284 titles: [],
285 viewBox,
286 placementBottom,
287 fallbackRing: false,
288 });
289 return components.some(component => rectsOverlap(rect, component, -2)) ? null : rect;
290}