Files
alan b381290f34 feat(app): add deterministic orthogonal graph edge routing
Pure-Dart P2c slice: interval-aware ports and corridors, label-aware lane spacing, measured label placement with fallback shelf, skipped diagnostics and routing bounds. 20 focused tests plus existing suite and web build pass.
2026-10-21 16:51:38 +01:00

176 lines
5.3 KiB
Dart

import 'dart:math' as math;
import '../layout/layout_models.dart';
/// Geometry helpers for deterministic orthogonal routing.
///
/// Everything here is plain numbers: no Flutter types, no drawing and no
/// assumed metrics. The helpers are internal to the routing library.
/// Reserves horizontal or vertical tracks without collinear overlap.
///
/// A track is a position on [axis] plus the interval it spans on the other
/// axis. Two tracks only conflict when both their positions and their spans
/// overlap, so a long cross lane and a short stub may share a coordinate when
/// their runs do not meet.
class AxisTrackAllocator {
AxisTrackAllocator(this.step);
final double step;
final List<_Track> _placed = <_Track>[];
/// The nearest free position to [desired], or null when none is found.
double? allocate({
required double desired,
required double min,
required double max,
required double spanLo,
required double spanHi,
}) {
if (max < min) return null;
final start = desired.clamp(min, max);
var spacing = step;
while (spacing > 0.0001) {
for (var attempt = 0; attempt <= 512; attempt += 1) {
final candidates = attempt == 0
? <double>[start]
: <double>[start + attempt * spacing, start - attempt * spacing];
for (final candidate in candidates) {
if (candidate < min || candidate > max) continue;
if (_isFree(candidate, spanLo, spanHi, spacing)) {
_placed.add(_Track(candidate, spanLo, spanHi));
return candidate;
}
}
}
spacing /= 2;
}
return null;
}
bool _isFree(double position, double spanLo, double spanHi, double spacing) {
for (final track in _placed) {
if ((track.position - position).abs() >= spacing) continue;
final overlaps = track.lo <= spanHi && spanLo <= track.hi;
if (overlaps) return false;
}
return true;
}
}
class _Track {
const _Track(this.position, this.lo, this.hi);
final double position;
final double lo;
final double hi;
}
/// The x band available for vertical corridors in each column gap.
///
/// Gap `g` sits before rank `g`; gap `rankCount` is the free space right of the
/// last column. Left/right bounds come from the placed boxes themselves, so a
/// corridor never crosses a column, including heterogeneous node widths.
class ColumnGaps {
ColumnGaps({
required List<GraphNodeBox> nodes,
required this.rankCount,
required this.layoutWidth,
}) : _left = List<double>.filled(rankCount + 1, 0),
_right = List<double>.filled(rankCount + 1, layoutWidth) {
final rankRight = List<double>.filled(rankCount, 0);
final rankLeft = List<double>.filled(rankCount, layoutWidth);
for (final node in nodes) {
if (node.rank < 0 || node.rank >= rankCount) continue;
rankRight[node.rank] = math.max(rankRight[node.rank], node.right);
rankLeft[node.rank] = math.min(rankLeft[node.rank], node.x);
}
var left = 0.0;
for (var rank = 0; rank < rankCount; rank += 1) {
_left[rank] = left;
left = math.max(left, rankRight[rank]);
}
_left[rankCount] = left;
var right = layoutWidth;
_right[rankCount] = right;
for (var rank = rankCount - 1; rank >= 0; rank -= 1) {
right = math.min(right, rankLeft[rank]);
_right[rank] = right;
}
}
final int rankCount;
final double layoutWidth;
final List<double> _left;
final List<double> _right;
/// The usable band in gap [index], inset by at most [clearance].
///
/// The rightmost gap is open-ended because a loop may expand the canvas;
/// every other gap is bounded by the neighbouring columns.
GapBand band(int index, double clearance) {
final gap = index.clamp(0, rankCount);
final left = _left[gap];
final right = _right[gap];
if (gap == rankCount) {
return GapBand(lo: left + clearance, hi: double.infinity, open: true);
}
if (gap == 0) {
return GapBand(
lo: double.negativeInfinity,
hi: right - clearance,
open: true,
);
}
final width = math.max(0.0, right - left);
final inset = math.min(clearance, width / 4);
return GapBand(lo: left + inset, hi: right - inset, open: false);
}
}
/// One usable corridor band.
class GapBand {
const GapBand({required this.lo, required this.hi, required this.open});
final double lo;
final double hi;
final bool open;
}
/// The inset a port keeps from a node corner.
double portInset(GraphNodeBox node, double portSpacing) =>
math.min(portSpacing / 2, node.height / 2);
/// True when an axis-aligned box overlaps [node], optionally inflated by [gap].
bool boxIntersectsNode({
required double x,
required double y,
required double width,
required double height,
required GraphNodeBox node,
double gap = 0,
}) {
return x < node.right + gap &&
x + width > node.x - gap &&
y < node.bottom + gap &&
y + height > node.y - gap;
}
/// True when two label-sized boxes overlap, optionally inflated by [gap].
bool boxesOverlap({
required double ax,
required double ay,
required double aw,
required double ah,
required double bx,
required double by,
required double bw,
required double bh,
double gap = 0,
}) {
return ax < bx + bw + gap &&
ax + aw + gap > bx &&
ay < by + bh + gap &&
ay + ah + gap > by;
}