Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 | 36x 6x 30x 267x 18x 18x 15x 15x 15x 149x 83x 18x 4x 4x 4x 4x 4x 4x 20x 4x 16x 5x 4x 4x 3x 4x 15x 15x 15x 15x 15x 15x 5x 5x 5x 10x 15x 3x 3x 3x 12x 15x 3x 3x 3x 3x 1x 1x 2x 3x 3x 1x 1x 2x 3x 3x 13x 13x 13x 13x 119x 26x 93x 2x 13x 17x 4x 13x 13x 11x 2x 2x 140x 140x 140x 1250x 184x 164x 164x 164x 147x 144x 3x 3x 17x 17x 164x 164x 20x 5x 15x 15x 5x 5x 5x 5x 5x 5x | import type { Bounds, Point } from '../types';
interface ObstacleCheckContext {
ignore: Bounds;
obstacles?: Bounds[];
}
function hasObstacleBelow(pt: Point, endY: number, ctx: ObstacleCheckContext): boolean {
if (!ctx.obstacles) {
return false;
}
// A proper y-interval overlap test, not `b.y >= pt.y`: a one-sided
// comparison misses an obstacle whose top edge sits above `pt` but whose
// body still overlaps the [pt.y, endY) drop/climb span -- which happens
// whenever `pt`'s own node already overlaps that obstacle (a regression this fixes).
return ctx.obstacles.some(
(b) =>
b !== ctx.ignore && pt.x > b.x && pt.x < b.x + b.width && b.y < endY && b.y + b.height > pt.y
);
}
function computeChannelY(sourceBounds: Bounds, targetBounds: Bounds, allBounds?: Bounds[]): number {
let maxBottomY = Math.max(
sourceBounds.y + sourceBounds.height,
targetBounds.y + targetBounds.height
);
if (allBounds) {
const minX = Math.min(sourceBounds.x, targetBounds.x);
const maxX = Math.max(sourceBounds.x + sourceBounds.width, targetBounds.x + targetBounds.width);
for (const b of allBounds) {
if (b.x + b.width >= minX && b.x <= maxX) {
maxBottomY = Math.max(maxBottomY, b.y + b.height);
}
}
}
return maxBottomY + 40;
}
interface FeedbackRouteContext {
channelY: number;
allBounds?: Bounds[];
}
function getClearTargetStepX(tgt: Bounds, channelY: number, obstacles: Bounds[]): number {
let stepX = tgt.x - 20;
const tgtLeftY = Math.round(tgt.y + tgt.height / 2);
const minY = Math.min(tgtLeftY, channelY);
const maxY = Math.max(tgtLeftY, channelY);
let minObstacleX = Infinity;
for (const b of obstacles) {
if (b === tgt) {
continue;
}
if (stepX > b.x && stepX < b.x + b.width) {
if (Math.max(minY, b.y) < Math.min(maxY, b.y + b.height)) {
minObstacleX = Math.min(minObstacleX, b.x);
}
}
}
if (minObstacleX < Infinity) {
stepX = minObstacleX - 30;
}
return stepX;
}
function computeFeedbackWaypoints(src: Bounds, tgt: Bounds, ctx: FeedbackRouteContext): Point[] {
const srcBottom: Point = {
x: Math.round(src.x + src.width / 2),
y: src.y + src.height,
};
const tgtBottom: Point = {
x: Math.round(tgt.x + tgt.width / 2),
y: tgt.y + tgt.height,
};
const srcBlocked = hasObstacleBelow(srcBottom, ctx.channelY, {
ignore: src,
obstacles: ctx.allBounds,
});
const tgtBlocked = hasObstacleBelow(tgtBottom, ctx.channelY, {
ignore: tgt,
obstacles: ctx.allBounds,
});
const waypoints: Point[] = [];
if (srcBlocked) {
const srcRight: Point = { x: src.x + src.width, y: Math.round(src.y + src.height / 2) };
const srcStepX = src.x + src.width + 20;
waypoints.push(srcRight, { x: srcStepX, y: srcRight.y }, { x: srcStepX, y: ctx.channelY });
} else {
waypoints.push(srcBottom, { x: srcBottom.x, y: ctx.channelY });
}
if (tgtBlocked) {
const tgtLeft: Point = { x: tgt.x, y: Math.round(tgt.y + tgt.height / 2) };
const tgtStepX = getClearTargetStepX(tgt, ctx.channelY, ctx.allBounds!);
waypoints.push({ x: tgtStepX, y: ctx.channelY }, { x: tgtStepX, y: tgtLeft.y }, tgtLeft);
} else {
waypoints.push({ x: tgtBottom.x, y: ctx.channelY }, tgtBottom);
}
return waypoints;
}
interface CollinearDetourContext {
sourceBounds: Bounds;
targetBounds: Bounds;
channelY: number;
allBounds?: Bounds[];
}
/**
* Detours a currently-blocked but genuinely forward, currently-collinear
* edge into a channel below everything and back up, the same shape of
* route `computeFeedbackWaypoints` builds for a true loop-back -- but
* anchored at the source's right edge and the target's left edge instead
* of their bottom-centers, so a forward edge still visually leaves from
* the right and arrives from the left even while detouring (a regression this fixes).
* Falling back to bottom-center anchors here would make an ordinary
* forward edge read as a loop-back whenever it needs to dodge an obstacle.
*/
function computeCollinearDetourWaypoints(
srcExit: Point,
tgtEntry: Point,
ctx: CollinearDetourContext
): Point[] {
const { sourceBounds, targetBounds, channelY, allBounds } = ctx;
const waypoints: Point[] = [srcExit];
const srcBlocked = hasObstacleBelow(srcExit, channelY, {
ignore: sourceBounds,
obstacles: allBounds,
});
if (srcBlocked) {
const srcStepX = srcExit.x + 20;
waypoints.push({ x: srcStepX, y: srcExit.y }, { x: srcStepX, y: channelY });
} else {
waypoints.push({ x: srcExit.x, y: channelY });
}
const tgtBlocked = hasObstacleBelow(tgtEntry, channelY, {
ignore: targetBounds,
obstacles: allBounds,
});
if (tgtBlocked) {
const tgtStepX = getClearTargetStepX(targetBounds, channelY, allBounds!);
waypoints.push({ x: tgtStepX, y: channelY }, { x: tgtStepX, y: tgtEntry.y });
} else {
waypoints.push({ x: tgtEntry.x, y: channelY });
}
waypoints.push(tgtEntry);
return waypoints;
}
interface ForwardStepBlockerContext {
yStart: number;
yEnd: number;
obstacles: Bounds[];
ignore: Bounds[];
}
/**
* The S-bend's vertical leg sits at `stepX` and must not pass through an
* unrelated shape that now happens to sit between source and target (e.g. a
* sibling gateway branch kept collinear with the gateway by issue #88's
* fix). Finds the leftmost obstacle straddling `stepX` within the leg's
* y-span, if any.
*/
function findForwardStepBlockerX(stepX: number, ctx: ForwardStepBlockerContext): number {
const minY = Math.min(ctx.yStart, ctx.yEnd);
const maxY = Math.max(ctx.yStart, ctx.yEnd);
let blockingX = Infinity;
for (const b of ctx.obstacles) {
if (ctx.ignore.includes(b)) {
continue;
}
if (
stepX > b.x &&
stepX < b.x + b.width &&
Math.max(minY, b.y) < Math.min(maxY, b.y + b.height)
) {
blockingX = Math.min(blockingX, b.x);
}
}
return blockingX;
}
interface ClearForwardStepContext {
srcExit: Point;
tgtEntry: Point;
obstacles: Bounds[] | undefined;
ignore: Bounds[];
}
function findClearForwardStepX(stepX: number, ctx: ClearForwardStepContext): number {
if (!ctx.obstacles || ctx.obstacles.length === 0) {
return stepX;
}
const blockingX = findForwardStepBlockerX(stepX, {
yStart: ctx.srcExit.y,
yEnd: ctx.tgtEntry.y,
obstacles: ctx.obstacles,
ignore: ctx.ignore,
});
if (blockingX === Infinity) {
return stepX;
}
const candidate = blockingX - 20;
return candidate > ctx.srcExit.x ? candidate : stepX;
}
interface CollinearSpan {
xStart: number;
xEnd: number;
ignore: Bounds[];
}
/**
* Whether some obstacle sits directly on a straight collinear run between
* two x positions at height `y` -- e.g. a chain of same-track nodes a
* multi-rank bypass edge jumps over.
*/
function isCollinearPathBlocked(y: number, span: CollinearSpan, obstacles: Bounds[]): boolean {
const minX = Math.min(span.xStart, span.xEnd);
const maxX = Math.max(span.xStart, span.xEnd);
return obstacles.some(
(b) =>
!span.ignore.includes(b) &&
y > b.y &&
y < b.y + b.height &&
Math.max(minX, b.x) < Math.min(maxX, b.x + b.width)
);
}
export function routeOrthogonalEdge(
sourceBounds: Bounds,
targetBounds: Bounds,
allBounds?: Bounds[]
): Point[] {
// If target is to the right of source (forward flow)
if (sourceBounds.x + sourceBounds.width <= targetBounds.x) {
const srcExit: Point = {
x: sourceBounds.x + sourceBounds.width,
y: Math.round(sourceBounds.y + sourceBounds.height / 2),
};
const tgtEntry: Point = {
x: targetBounds.x,
y: Math.round(targetBounds.y + targetBounds.height / 2),
};
// Straight collinear connection (0 bends), unless something now sits
// between source and target on that same track -- a multi-rank edge
// bypassing a chain of same-track nodes (e.g. a sibling branch kept
// collinear with its gateway by issue #88) can no longer assume the
// row is clear, since corridor routing is currently unwired (#81).
if (srcExit.y === tgtEntry.y) {
if (
!allBounds ||
!isCollinearPathBlocked(
srcExit.y,
{ xStart: srcExit.x, xEnd: tgtEntry.x, ignore: [sourceBounds, targetBounds] },
allBounds
)
) {
return [srcExit, tgtEntry];
}
// Drop into a channel below everything -- and, critically, check
// both the drop and the return leg for obstacles first, the same
// way a true feedback/loop-back edge does. An earlier version built
// this route by hand with no such check, so it could plow straight
// through some unrelated shape on the way back up.
const channelY = computeChannelY(sourceBounds, targetBounds, allBounds);
return computeCollinearDetourWaypoints(srcExit, tgtEntry, {
sourceBounds,
targetBounds,
channelY,
allBounds,
});
}
// Forward S-bend (Manhattan step with 2 bends)
const gap = tgtEntry.x - srcExit.x;
const stepX = gap > 100 ? tgtEntry.x - 30 : Math.round((srcExit.x + tgtEntry.x) / 2);
const clearStepX = findClearForwardStepX(stepX, {
srcExit,
tgtEntry,
obstacles: allBounds,
ignore: [sourceBounds, targetBounds],
});
return [srcExit, { x: clearStepX, y: srcExit.y }, { x: clearStepX, y: tgtEntry.y }, tgtEntry];
}
// Forward wrapped edge (target is on a lower row and behind source)
if (sourceBounds.y + sourceBounds.height + 20 <= targetBounds.y) {
return routeForwardWrappedEdge(sourceBounds, targetBounds);
}
// Feedback loop (target is at or behind source)
const channelY = computeChannelY(sourceBounds, targetBounds, allBounds);
return computeFeedbackWaypoints(sourceBounds, targetBounds, { channelY, allBounds });
}
function routeForwardWrappedEdge(src: Bounds, tgt: Bounds): Point[] {
const srcRight: Point = {
x: src.x + src.width,
y: Math.round(src.y + src.height / 2),
};
const tgtLeft: Point = {
x: tgt.x,
y: Math.round(tgt.y + tgt.height / 2),
};
const midY = Math.round((src.y + src.height + tgt.y) / 2);
const stepSrcX = srcRight.x + 20;
const stepTgtX = tgtLeft.x - 20;
return [
srcRight,
{ x: stepSrcX, y: srcRight.y },
{ x: stepSrcX, y: midY },
{ x: stepTgtX, y: midY },
{ x: stepTgtX, y: tgtLeft.y },
tgtLeft,
];
}
|