fb1935a62d
The linear layout used by the definition and run graphs placed each outcome label at the middle of its widest run with no collision check, and the run graph measured only the label text while rendering an order badge in front of it, so taken labels ran into the next node. Labels now try positions along their own route (horizontal runs above and below, sliding along, then vertical runs) and take the first whose box stays 4px clear of every node and earlier label, preferring spots off other wires. If a label finds no spot, the layout widens its column gaps and lanes and runs again; a last-resort shelf below the drawing never overlaps. The run graph measures the exact badge+label widget it renders, keyed by edge id.
261 lines
7.6 KiB
Dart
261 lines
7.6 KiB
Dart
import 'dart:math' as math;
|
|
|
|
import '../routing/route_models.dart';
|
|
import 'layout_models.dart';
|
|
|
|
/// The space every placed edge label keeps from every node box and from every
|
|
/// other label, in logical pixels.
|
|
const double edgeLabelClearance = 4;
|
|
|
|
/// The labels for one set of routes, and the edges that found no spot on
|
|
/// their own route.
|
|
class LinearLabelPlacement {
|
|
const LinearLabelPlacement({required this.labels, required this.misfits});
|
|
|
|
/// One box per labelled route, in route order.
|
|
final List<EdgeLabelBox> labels;
|
|
|
|
/// Edge ids whose label had to leave its route for the free shelf below the
|
|
/// drawing. A layout grows its gaps and tries again while this is non-empty.
|
|
final Set<int> misfits;
|
|
}
|
|
|
|
/// Places one measured label per route so no label box comes within
|
|
/// [clearance] of a node box or of an earlier label.
|
|
///
|
|
/// Each label tries positions along its own route, beside a run with
|
|
/// [labelGap] to the wire: the longest horizontal run first (above, then
|
|
/// below), sliding from the middle towards both ends, then the other
|
|
/// horizontal runs, then vertical runs (right, then left). A first pass also
|
|
/// keeps the box off every wire; a second pass allows crossing a wire but
|
|
/// never a node or a label. A label with no free spot on its route goes to a
|
|
/// shelf below everything and is reported in [LinearLabelPlacement.misfits].
|
|
LinearLabelPlacement placeLinearLabels({
|
|
required List<EdgeRoute> routes,
|
|
required Map<int, LabelExtent> extents,
|
|
required List<GraphNodeBox> nodes,
|
|
required double labelGap,
|
|
double clearance = edgeLabelClearance,
|
|
}) {
|
|
final labels = <EdgeLabelBox>[];
|
|
final misfits = <int>{};
|
|
final pending = <(EdgeRoute, LabelExtent)>[];
|
|
for (final route in routes) {
|
|
final extent = extents[route.id];
|
|
if (route.label.isEmpty || extent == null || extent.width == 0) continue;
|
|
final candidates = _candidates(route, extent, labelGap);
|
|
_Rect? chosen;
|
|
for (final avoidWires in const [true, false]) {
|
|
for (final rect in candidates) {
|
|
if (_free(rect, nodes, labels, clearance) &&
|
|
(!avoidWires || !_crossesWire(rect, routes))) {
|
|
chosen = rect;
|
|
break;
|
|
}
|
|
}
|
|
if (chosen != null) break;
|
|
}
|
|
if (chosen == null) {
|
|
misfits.add(route.id);
|
|
pending.add((route, extent));
|
|
continue;
|
|
}
|
|
labels.add(_box(route.id, chosen));
|
|
}
|
|
|
|
// The shelf sits below every node, wire and label, so it cannot overlap.
|
|
var shelf = 0.0;
|
|
for (final node in nodes) {
|
|
shelf = math.max(shelf, node.bottom);
|
|
}
|
|
for (final route in routes) {
|
|
for (final point in route.points) {
|
|
shelf = math.max(shelf, point.y);
|
|
}
|
|
}
|
|
for (final label in labels) {
|
|
shelf = math.max(shelf, label.bottom);
|
|
}
|
|
for (final (route, extent) in pending) {
|
|
var top = shelf + clearance + labelGap;
|
|
final left = math.max(0.0, _centreX(route) - extent.width / 2);
|
|
var rect = _Rect(left, top, extent.width, extent.height);
|
|
while (!_free(rect, nodes, labels, clearance)) {
|
|
top += extent.height + clearance;
|
|
rect = _Rect(left, top, extent.width, extent.height);
|
|
}
|
|
labels.add(_box(route.id, rect));
|
|
}
|
|
labels.sort(
|
|
(a, b) => _indexOf(routes, a.edgeId).compareTo(_indexOf(routes, b.edgeId)),
|
|
);
|
|
return LinearLabelPlacement(labels: labels, misfits: misfits);
|
|
}
|
|
|
|
/// Whether two axis-aligned boxes come within [clearance] of each other.
|
|
bool labelRectsClash(
|
|
double ax,
|
|
double ay,
|
|
double aw,
|
|
double ah,
|
|
double bx,
|
|
double by,
|
|
double bw,
|
|
double bh,
|
|
double clearance,
|
|
) =>
|
|
ax < bx + bw + clearance &&
|
|
bx < ax + aw + clearance &&
|
|
ay < by + bh + clearance &&
|
|
by < ay + ah + clearance;
|
|
|
|
int _indexOf(List<EdgeRoute> routes, int id) =>
|
|
routes.indexWhere((route) => route.id == id);
|
|
|
|
EdgeLabelBox _box(int id, _Rect rect) => EdgeLabelBox(
|
|
edgeId: id,
|
|
x: rect.x,
|
|
y: rect.y,
|
|
width: rect.w,
|
|
height: rect.h,
|
|
);
|
|
|
|
bool _free(
|
|
_Rect rect,
|
|
List<GraphNodeBox> nodes,
|
|
List<EdgeLabelBox> labels,
|
|
double clearance,
|
|
) {
|
|
if (rect.x < 0 || rect.y < 0) return false;
|
|
for (final node in nodes) {
|
|
if (labelRectsClash(
|
|
rect.x,
|
|
rect.y,
|
|
rect.w,
|
|
rect.h,
|
|
node.x,
|
|
node.y,
|
|
node.width,
|
|
node.height,
|
|
clearance,
|
|
)) {
|
|
return false;
|
|
}
|
|
}
|
|
for (final label in labels) {
|
|
if (labelRectsClash(
|
|
rect.x,
|
|
rect.y,
|
|
rect.w,
|
|
rect.h,
|
|
label.x,
|
|
label.y,
|
|
label.width,
|
|
label.height,
|
|
clearance,
|
|
)) {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/// True when a wire passes through the label's interior.
|
|
bool _crossesWire(_Rect rect, List<EdgeRoute> routes) {
|
|
for (final route in routes) {
|
|
for (var i = 1; i < route.points.length; i++) {
|
|
final a = route.points[i - 1], b = route.points[i];
|
|
final x0 = math.min(a.x, b.x), x1 = math.max(a.x, b.x);
|
|
final y0 = math.min(a.y, b.y), y1 = math.max(a.y, b.y);
|
|
final right = rect.x + rect.w, bottom = rect.y + rect.h;
|
|
// Orthogonal segments: one axis is a line, the other an interval.
|
|
final acrossX = x0 == x1
|
|
? x0 > rect.x && x0 < right
|
|
: x0 < right && x1 > rect.x;
|
|
final acrossY = y0 == y1
|
|
? y0 > rect.y && y0 < bottom
|
|
: y0 < bottom && y1 > rect.y;
|
|
if (acrossX && acrossY) return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
List<_Rect> _candidates(EdgeRoute route, LabelExtent extent, double gap) {
|
|
const fractions = <double>[0.5, 0.35, 0.65, 0.2, 0.8, 0, 1];
|
|
final w = extent.width, h = extent.height;
|
|
final horizontals = <_Run>[];
|
|
final verticals = <_Run>[];
|
|
for (var i = 1; i < route.points.length; i++) {
|
|
final a = route.points[i - 1], b = route.points[i];
|
|
if (a.y == b.y && a.x != b.x) {
|
|
horizontals.add(_Run(math.min(a.x, b.x), math.max(a.x, b.x), a.y, i));
|
|
} else if (a.x == b.x && a.y != b.y) {
|
|
verticals.add(_Run(math.min(a.y, b.y), math.max(a.y, b.y), a.x, i));
|
|
}
|
|
}
|
|
int longestFirst(_Run a, _Run b) {
|
|
final byLength = b.length.compareTo(a.length);
|
|
return byLength != 0 ? byLength : a.order.compareTo(b.order);
|
|
}
|
|
|
|
horizontals.sort(longestFirst);
|
|
verticals.sort(longestFirst);
|
|
final rects = <_Rect>[];
|
|
for (final run in horizontals) {
|
|
for (final fraction in fractions) {
|
|
final left = _along(run, fraction, w);
|
|
rects
|
|
..add(_Rect(left, run.at - gap - h, w, h))
|
|
..add(_Rect(left, run.at + gap, w, h));
|
|
}
|
|
}
|
|
for (final run in verticals) {
|
|
for (final fraction in fractions) {
|
|
final top = _along(run, fraction, h);
|
|
rects
|
|
..add(_Rect(run.at + gap, top, w, h))
|
|
..add(_Rect(run.at - gap - w, top, w, h));
|
|
}
|
|
}
|
|
return rects;
|
|
}
|
|
|
|
/// The start of a [size]-long label centred at [fraction] of [run], kept on
|
|
/// the run when it is long enough to hold the whole label.
|
|
double _along(_Run run, double fraction, double size) {
|
|
final centre = run.lo + run.length * fraction;
|
|
if (run.length < size) return run.lo + run.length / 2 - size / 2;
|
|
return math.min(math.max(centre - size / 2, run.lo), run.hi - size);
|
|
}
|
|
|
|
double _centreX(EdgeRoute route) {
|
|
var lo = double.infinity, hi = double.negativeInfinity;
|
|
for (final point in route.points) {
|
|
lo = math.min(lo, point.x);
|
|
hi = math.max(hi, point.x);
|
|
}
|
|
return route.points.isEmpty ? 0 : (lo + hi) / 2;
|
|
}
|
|
|
|
/// One straight run: [lo]..[hi] along its axis, at [at] across it.
|
|
class _Run {
|
|
const _Run(this.lo, this.hi, this.at, this.order);
|
|
|
|
final double lo;
|
|
final double hi;
|
|
final double at;
|
|
final int order;
|
|
|
|
double get length => hi - lo;
|
|
}
|
|
|
|
class _Rect {
|
|
const _Rect(this.x, this.y, this.w, this.h);
|
|
|
|
final double x;
|
|
final double y;
|
|
final double w;
|
|
final double h;
|
|
}
|