use std::collections::{HashMap, HashSet};
use lievisual::geometry::{Point, Rect};
use crate::builder::ir::common::RoutingHint;
use crate::builder::ir::geograph::{GGContainer, GGNode, Geograph, RoutePath, RouteSegment};
use crate::builder::ir::shape::ShapeKind;
const STUB: f64 = 18.0;
#[derive(Clone, Copy)]
pub(crate) struct Slot {
pub(crate) idx: usize,
pub(crate) total: usize,
}
const MIN_ARC: f64 = 28.0;
const MAX_ARC: f64 = 140.0;
const PORT_MIN_SPACING: f64 = 14.0;
const PORT_MAX_SPACING_RATIO: f64 = 0.4;
const PORT_CORNER_MARGIN: f64 = 8.0;
const OFFSET_STEP: f64 = 12.0;
const MAX_OFFSET_TRIES: usize = 8;
const CHANNEL_MARGIN: f64 = 16.0;
const CH_STACK: f64 = 28.0;
const BAND_PAD: f64 = 30.0;
const CORNER_RADIUS: f64 = 14.0;
const CONTAINER_PAD: f64 = 6.0;
#[derive(Clone, Copy)]
enum Plan {
SelfLoop,
Mutual { side: f64 },
BackBow { side: f64 },
BackChannel { ch: f64, side: f64 },
Normal,
}
struct RectGrid {
cell: f64,
min_x: f64,
min_y: f64,
cols: usize,
rows: usize,
buckets: Vec<Vec<usize>>,
}
impl RectGrid {
const EMPTY: Self = RectGrid {
cell: 1.0,
min_x: 0.0,
min_y: 0.0,
cols: 0,
rows: 0,
buckets: Vec::new(),
};
fn new(rects: &[Rect]) -> Self {
if rects.is_empty() {
return Self::EMPTY;
}
let mut min_x = f64::INFINITY;
let mut min_y = f64::INFINITY;
let mut max_x = f64::NEG_INFINITY;
let mut max_y = f64::NEG_INFINITY;
for r in rects {
min_x = min_x.min(r.min_x());
min_y = min_y.min(r.min_y());
max_x = max_x.max(r.max_x());
max_y = max_y.max(r.max_y());
}
if !min_x.is_finite() || !min_y.is_finite() {
return Self::EMPTY;
}
let w = (max_x - min_x).max(1e-6);
let h = (max_y - min_y).max(1e-6);
let n = rects.len() as f64;
let mut cell = ((w * h) / n).sqrt().clamp(8.0, 512.0);
loop {
let cols = (w / cell).ceil() as usize + 1;
let rows = (h / cell).ceil() as usize + 1;
if cols.saturating_mul(rows) <= MAX_GRID_CELLS {
let mut buckets = vec![Vec::new(); cols * rows];
for (i, r) in rects.iter().enumerate() {
let c0 = col_of(r.min_x(), min_x, cell, cols);
let c1 = col_of(r.max_x(), min_x, cell, cols);
let r0 = row_of(r.min_y(), min_y, cell, rows);
let r1 = row_of(r.max_y(), min_y, cell, rows);
for row in r0..=r1 {
for col in c0..=c1 {
buckets[row * cols + col].push(i);
}
}
}
return RectGrid {
cell,
min_x,
min_y,
cols,
rows,
buckets,
};
}
cell *= 2.0;
}
}
fn col_of(&self, x: f64) -> usize {
clamp_cell(((x - self.min_x) / self.cell).floor() as isize, self.cols)
}
fn row_of(&self, y: f64) -> usize {
clamp_cell(((y - self.min_y) / self.cell).floor() as isize, self.rows)
}
fn for_each(&self, area: Rect, mut f: impl FnMut(usize)) {
if self.buckets.is_empty() {
return;
}
let (c0, c1) = (self.col_of(area.min_x()), self.col_of(area.max_x()));
let (r0, r1) = (self.row_of(area.min_y()), self.row_of(area.max_y()));
for row in r0..=r1 {
for col in c0..=c1 {
for &i in &self.buckets[row * self.cols + col] {
f(i);
}
}
}
}
}
const MAX_GRID_CELLS: usize = 1 << 20;
fn clamp_cell(v: isize, n: usize) -> usize {
if v < 0 {
0
} else if v as usize >= n {
n - 1
} else {
v as usize
}
}
fn col_of(x: f64, min_x: f64, cell: f64, cols: usize) -> usize {
clamp_cell(((x - min_x) / cell).floor() as isize, cols)
}
fn row_of(y: f64, min_y: f64, cell: f64, rows: usize) -> usize {
clamp_cell(((y - min_y) / cell).floor() as isize, rows)
}
struct Obstacles {
rects: Vec<(usize, Rect, String)>,
rects_t: Vec<(usize, Rect, String)>,
grid: RectGrid,
grid_t: RectGrid,
all_min_x: f64,
all_max_x: f64,
all_min_x_t: f64,
all_max_x_t: f64,
members: HashMap<String, HashSet<String>>,
}
fn edge_skip<'a>(
s_id: &'a str,
t_id: &'a str,
members: &'a HashMap<String, HashSet<String>>,
) -> impl Fn(&str) -> bool + 'a {
move |owner: &str| -> bool {
if owner == s_id || owner == t_id {
return true;
}
members
.get(owner)
.is_some_and(|m| m.contains(s_id) || m.contains(t_id))
}
}
pub fn route_edges(
gg: &mut Geograph,
direction: crate::ast::Direction,
containers: &[GGContainer],
) {
let node_map: HashMap<&String, &GGNode> = gg.nodes.iter().map(|n| (&n.id, n)).collect();
let node_rects: Vec<(usize, Rect, String)> = gg
.nodes
.iter()
.enumerate()
.map(|(i, n)| (i, node_rect(n), n.id.clone()))
.collect();
let container_rects: Vec<(usize, Rect, String)> = containers
.iter()
.enumerate()
.map(|(i, c)| {
let b = c.bounds;
(
i,
Rect::new(
b.min_x() - CONTAINER_PAD,
b.min_y() - CONTAINER_PAD,
b.max_x() + CONTAINER_PAD,
b.max_y() + CONTAINER_PAD,
),
c.id.clone(),
)
})
.collect();
let mut members: HashMap<String, HashSet<String>> = HashMap::new();
for c in containers {
members.insert(c.id.clone(), c.member_ids.iter().cloned().collect());
}
let mut all_rects = node_rects.clone();
all_rects.extend(container_rects);
let rects_t: Vec<(usize, Rect, String)> = all_rects
.iter()
.map(|(i, r, o)| (*i, tr_rect(*r), o.clone()))
.collect();
let grid = RectGrid::new(&all_rects.iter().map(|(_, r, _)| *r).collect::<Vec<_>>());
let grid_t = RectGrid::new(&rects_t.iter().map(|(_, r, _)| *r).collect::<Vec<_>>());
let (all_min_x, all_max_x) = x_range(&all_rects);
let (all_min_x_t, all_max_x_t) = x_range(&rects_t);
let obstacles = Obstacles {
rects: all_rects,
rects_t,
grid,
grid_t,
all_min_x,
all_max_x,
all_min_x_t,
all_max_x_t,
members,
};
let mut mutual_side: HashMap<(String, String), f64> = HashMap::new();
let mut used_channels: Vec<(f64, f64, f64)> = Vec::new();
let mut used_trunks: Vec<(f64, f64, f64)> = Vec::new();
let edge_pairs: Vec<(String, String)> = gg
.edges
.iter()
.map(|e| (e.source.clone(), e.target.clone()))
.collect();
let centers: HashMap<&str, Point> =
gg.nodes.iter().map(|n| (n.id.as_str(), n.center)).collect();
let directed: std::collections::HashSet<(&str, &str)> = gg
.edges
.iter()
.map(|e| (e.source.as_str(), e.target.as_str()))
.collect();
let mut mutual_pairs: std::collections::HashSet<(String, String)> =
std::collections::HashSet::new();
for e in &gg.edges {
if directed.contains(&(e.target.as_str(), e.source.as_str())) {
mutual_pairs.insert((e.source.clone(), e.target.clone()));
}
}
let mut plans: Vec<Option<Plan>> = Vec::with_capacity(gg.edges.len());
for e in &gg.edges {
match (node_map.get(&e.source), node_map.get(&e.target)) {
(Some(s), Some(t)) => {
let plan = if s.id == t.id {
Plan::SelfLoop
} else if mutual_pairs.contains(&(e.source.clone(), e.target.clone())) {
Plan::Mutual {
side: mutual_side_for(&e.source, &e.target, &mut mutual_side),
}
} else if is_back_edge(s, t, direction) {
let side = mutual_side_for(&e.source, &e.target, &mut mutual_side);
match plan_back_channel(
s,
t,
direction,
&obstacles,
&edge_pairs,
¢ers,
&mut used_channels,
) {
Some((ch, ch_side)) => Plan::BackChannel { ch, side: ch_side },
None => Plan::BackBow { side },
}
} else {
Plan::Normal
};
plans.push(Some(plan));
}
_ => plans.push(None),
}
}
let mut edge_ports: Vec<Option<(Port, Port)>> = vec![None; gg.edges.len()];
let mut used_out: HashMap<String, HashSet<Port>> = HashMap::new();
let mut used_in: HashMap<String, HashSet<Port>> = HashMap::new();
for (i, e) in gg.edges.iter().enumerate() {
if !matches!(plans[i], Some(Plan::Normal) | None) {
continue;
}
if let (Some(s), Some(t)) = (node_map.get(&e.source), node_map.get(&e.target)) {
let sp = edge_port(s, t, direction, true, false, 0.0, used_in.get(&e.source));
let tp = edge_port(t, s, direction, false, false, 0.0, used_out.get(&e.target));
used_out.entry(e.source.clone()).or_default().insert(sp);
used_in.entry(e.target.clone()).or_default().insert(tp);
edge_ports[i] = Some((sp, tp));
}
}
for (i, e) in gg.edges.iter().enumerate() {
match plans[i] {
Some(Plan::BackBow { side }) => {
if let (Some(s), Some(t)) = (node_map.get(&e.source), node_map.get(&e.target)) {
let sp = edge_port(s, t, direction, true, true, side, used_in.get(&e.source));
let tp = edge_port(t, s, direction, false, true, side, used_out.get(&e.target));
used_out.entry(e.source.clone()).or_default().insert(sp);
used_in.entry(e.target.clone()).or_default().insert(tp);
edge_ports[i] = Some((sp, tp));
}
}
Some(Plan::BackChannel { side, .. }) => {
let (sp, tp) = channel_ports(side, direction);
used_out.entry(e.source.clone()).or_default().insert(sp);
used_in.entry(e.target.clone()).or_default().insert(tp);
edge_ports[i] = Some((sp, tp));
}
_ => {}
}
}
let mut src_groups: HashMap<(String, Port), Vec<(usize, f64)>> = HashMap::new();
let mut tgt_groups: HashMap<(String, Port), Vec<(usize, f64)>> = HashMap::new();
for (i, e) in gg.edges.iter().enumerate() {
let Some((sp, tp)) = edge_ports[i] else {
continue;
};
let (Some(s), Some(t)) = (node_map.get(&e.source), node_map.get(&e.target)) else {
continue;
};
src_groups
.entry((e.source.clone(), sp))
.or_default()
.push((i, axis_projection(sp, t.center)));
tgt_groups
.entry((e.target.clone(), tp))
.or_default()
.push((i, axis_projection(tp, s.center)));
}
let mut slots: Vec<(Slot, Slot)> =
vec![(Slot { idx: 0, total: 1 }, Slot { idx: 0, total: 1 }); gg.edges.len()];
rank_slots(src_groups, &mut slots, true);
rank_slots(tgt_groups, &mut slots, false);
for (i, e) in gg.edges.iter_mut().enumerate() {
let Some(plan) = plans[i] else {
continue;
};
let (Some(s), Some(t)) = (node_map.get(&e.source), node_map.get(&e.target)) else {
continue;
};
let s = *s;
let t = *t;
let (s_slot, t_slot) = slots[i];
let mut anchor_override = None;
let route = match plan {
Plan::SelfLoop => {
let (r, anchor) = self_loop_route(s);
anchor_override = Some(anchor);
r
}
Plan::Mutual { side } => mutual_dual_route(s, t, side),
_ => {
let Some((sp, tp)) = edge_ports[i] else {
continue;
};
let s_port = (sp, s_slot);
let t_port = (tp, t_slot);
match plan {
Plan::BackBow { side } => back_edge_route(s, t, &s_port, &t_port, side),
Plan::BackChannel { ch, .. } => channel_route(s, t, ch, &s_port, &t_port),
_ => match e.routing_hint {
RoutingHint::Spline => spline_route_safe(
s,
t,
&s_port,
&t_port,
&obstacles,
&mut used_channels,
),
_ => orthogonal_route(s, t, &s_port, &t_port, &obstacles, &mut used_trunks),
},
}
}
};
if e.label_text.is_some() {
e.label_anchor = Some(anchor_override.unwrap_or_else(|| route.midpoint()));
}
e.route = route;
}
}
fn mutual_side_for(source: &str, target: &str, seen: &mut HashMap<(String, String), f64>) -> f64 {
let key = (source.to_owned(), target.to_owned());
if let Some(&s) = seen.get(&key) {
return s;
}
let reverse_key = (target.to_owned(), source.to_owned());
if let Some(&rev) = seen.get(&reverse_key) {
let side = -rev;
seen.insert(key, side);
side
} else {
seen.insert(key, 1.0);
1.0
}
}
fn self_loop_route(n: &GGNode) -> (RoutePath, Point) {
let (hw, hh) = (n.size.width / 2.0, n.size.height / 2.0);
let p0 = port_point_offset(n, Port::Right, -hh * 0.3);
let p3 = port_point_offset(n, Port::Right, hh * 0.3);
let ext = (hh * 1.2).max(30.0);
let outer = n.center.x + hw + ext;
let p1 = Point::new(outer, n.center.y - hh * 0.9);
let p2 = Point::new(outer, n.center.y + hh * 0.9);
let anchor = Point::new(outer + 10.0, n.center.y);
let mut r = RoutePath::new();
r.push(RouteSegment::CubicBezier { p0, p1, p2, p3 });
(r, anchor)
}
fn mutual_dual_route(s: &GGNode, t: &GGNode, side: f64) -> RoutePath {
let dx = (t.center.x - s.center.x).abs();
let dy = (t.center.y - s.center.y).abs();
let off = (s.size.width.min(t.size.width) * 0.07).clamp(4.0, 12.0);
let bow = off * 0.9;
let mut r = RoutePath::new();
if dy >= dx {
let forward = t.center.y >= s.center.y;
let sp = if forward { Port::Bottom } else { Port::Top };
let tp = if forward { Port::Top } else { Port::Bottom };
let p0 = port_point_offset(s, sp, side * off);
let p3 = port_point_offset(t, tp, side * off);
let h = p3.y - p0.y;
let p1 = Point::new(p0.x + side * bow, p0.y + h * 0.45);
let p2 = Point::new(p3.x + side * bow, p3.y - h * 0.45);
r.push(RouteSegment::CubicBezier { p0, p1, p2, p3 });
} else {
let forward = t.center.x >= s.center.x;
let sp = if forward { Port::Right } else { Port::Left };
let tp = if forward { Port::Left } else { Port::Right };
let p0 = port_point_offset(s, sp, side * off);
let p3 = port_point_offset(t, tp, side * off);
let w = p3.x - p0.x;
let p1 = Point::new(p0.x + w * 0.45, p0.y + side * bow);
let p2 = Point::new(p3.x - w * 0.45, p3.y + side * bow);
r.push(RouteSegment::CubicBezier { p0, p1, p2, p3 });
}
r
}
fn back_edge_route(
s: &GGNode,
t: &GGNode,
s_slot: &(Port, Slot),
t_slot: &(Port, Slot),
side: f64,
) -> RoutePath {
let (sp, tp) = (s_slot.0, t_slot.0);
let p0 = port_point_at(s, sp, s_slot.1);
let p3 = port_point_at(t, tp, t_slot.1);
let mut r = RoutePath::new();
let src_side = matches!(sp, Port::Left | Port::Right);
let tgt_side = matches!(tp, Port::Left | Port::Right);
if src_side || tgt_side {
let dx = p3.x - p0.x;
let dy = p3.y - p0.y;
let ext = ((dx * dx + dy * dy).sqrt() * 0.45).clamp(24.0, 200.0);
let (n1, n2) = (port_normal(sp), port_normal(tp));
let p1 = Point::new(p0.x + n1.0 * ext, p0.y + n1.1 * ext);
let p2 = Point::new(p3.x + n2.0 * ext, p3.y + n2.1 * ext);
r.push(RouteSegment::CubicBezier { p0, p1, p2, p3 });
return r;
}
if matches!(sp, Port::Top | Port::Bottom) {
let d = if p3.y >= p0.y { 1.0 } else { -1.0 };
let y_ext = (p3.y - p0.y).abs() * 0.4 + 20.0;
let x_off = s.size.width.max(t.size.width) * 0.25;
let p1 = Point::new(p0.x + side * x_off, p0.y + d * y_ext);
let p2 = Point::new(p3.x - side * x_off, p3.y - d * y_ext);
r.push(RouteSegment::CubicBezier { p0, p1, p2, p3 });
} else {
let d = if p3.x >= p0.x { 1.0 } else { -1.0 };
let x_ext = (p3.x - p0.x).abs() * 0.4 + 20.0;
let y_off = s.size.height.max(t.size.height) * 0.25;
let p1 = Point::new(p0.x + d * x_ext, p0.y + side * y_off);
let p2 = Point::new(p3.x - d * x_ext, p3.y - side * y_off);
r.push(RouteSegment::CubicBezier { p0, p1, p2, p3 });
}
r
}
fn channel_route(
s: &GGNode,
t: &GGNode,
ch: f64,
s_slot: &(Port, Slot),
t_slot: &(Port, Slot),
) -> RoutePath {
let (sp, tp) = (s_slot.0, t_slot.0);
let p0 = port_point_at(s, sp, s_slot.1);
let p3 = port_point_at(t, tp, t_slot.1);
let vertical = matches!(sp, Port::Left | Port::Right);
let tr = |p: Point| if vertical { p } else { Point::new(p.y, p.x) };
let (a, b) = (tr(p0), tr(p3));
let pts_v = [a, Point::new(ch, a.y), Point::new(ch, b.y), b];
if vertical {
rounded_polyline(&pts_v, CORNER_RADIUS)
} else {
let pts: Vec<Point> = pts_v.iter().map(|p| tr(*p)).collect();
rounded_polyline(&pts, CORNER_RADIUS)
}
}
fn channel_conflicts_used(ch: f64, top: f64, bot: f64, used: &[(f64, f64, f64)]) -> bool {
used.iter()
.any(|(c, y0, y1)| (c - ch).abs() < 2.0 && *y1 > top && *y0 < bot)
}
fn trunk_conflicts_used(trunk: f64, s0: f64, s1: f64, used: &[(f64, f64, f64)]) -> bool {
used.iter()
.any(|(t, u0, u1)| (t - trunk).abs() < 2.0 && *u1 > s0 && *u0 < s1)
}
#[allow(clippy::too_many_arguments)]
fn try_channel_side(
start: f64,
to_right: bool,
top: f64,
bot: f64,
rects: &[(usize, Rect, String)],
grid: &RectGrid,
skip: &dyn Fn(&str) -> bool,
ends_clear: &dyn Fn(f64) -> bool,
used: &[(f64, f64, f64)],
) -> Option<f64> {
let mut ch = settle_channel(start, to_right, top, bot, rects, grid, skip)?;
if !ends_clear(ch) {
return None;
}
for _ in 0..6 {
if !channel_conflicts_used(ch, top, bot, used) {
return Some(ch);
}
ch = if to_right {
ch + CH_STACK
} else {
ch - CH_STACK
};
ch = settle_channel(ch, to_right, top, bot, rects, grid, skip)?;
if !ends_clear(ch) {
return None;
}
}
None
}
fn plan_back_channel(
s: &GGNode,
t: &GGNode,
direction: crate::ast::Direction,
obstacles: &Obstacles,
edges: &[(String, String)],
centers: &HashMap<&str, Point>,
used: &mut Vec<(f64, f64, f64)>,
) -> Option<(f64, f64)> {
use crate::ast::Direction;
let vert = matches!(direction, Direction::TB | Direction::TD | Direction::BT);
let tr = |p: Point| if vert { p } else { Point::new(p.y, p.x) };
let (rects, grid) = if vert {
(&obstacles.rects, &obstacles.grid)
} else {
(&obstacles.rects_t, &obstacles.grid_t)
};
let sc = tr(s.center);
let tc = tr(t.center);
if sc.y <= tc.y {
return None;
}
let (top, bot) = (tc.y, sc.y);
let mid_x = (sc.x + tc.x) / 2.0;
let skip = edge_skip(&s.id, &t.id, &obstacles.members);
let band = Rect::new(
(sc.x.min(tc.x) - BAND_PAD).min(mid_x - BAND_PAD),
top,
(sc.x.max(tc.x) + BAND_PAD).max(mid_x + BAND_PAD),
bot,
);
let mut any = false;
let mut ob_min = f64::INFINITY;
let mut ob_max = f64::NEG_INFINITY;
grid.for_each(band, |i| {
let (_, r, owner) = &rects[i];
if skip(owner) {
return;
}
if rects_overlap(*r, band) {
any = true;
ob_min = ob_min.min(r.min_x());
ob_max = ob_max.max(r.max_x());
}
});
if !any {
return None;
}
let ends_clear = |ch: f64| -> bool {
[sc.y, tc.y].iter().all(|&y| {
polyline_clear(
&[Point::new(sc.x.min(ch), y), Point::new(sc.x.max(ch), y)],
&skip,
rects,
grid,
) && polyline_clear(
&[Point::new(tc.x.min(ch), y), Point::new(tc.x.max(ch), y)],
&skip,
rects,
grid,
)
})
};
let right = try_channel_side(
ob_max + CHANNEL_MARGIN,
true,
top,
bot,
rects,
grid,
&skip,
&ends_clear,
used,
);
let left = try_channel_side(
ob_min - CHANNEL_MARGIN,
false,
top,
bot,
rects,
grid,
&skip,
&ends_clear,
used,
);
let crossers = |ch: f64, to_right: bool| -> usize {
let beyond = |x: f64| if to_right { x > ch } else { x < ch };
let mut cnt = 0usize;
for (u, v) in edges {
if u == &s.id || u == &t.id || v == &s.id || v == &t.id {
continue;
}
let (Some(&uc), Some(&vc)) = (centers.get(u.as_str()), centers.get(v.as_str())) else {
continue;
};
let (uc, vc) = (tr(uc), tr(vc));
let in_span = if beyond(uc.x) {
vc.y
} else if beyond(vc.x) {
uc.y
} else {
continue;
};
if in_span > top && in_span < bot {
cnt += 1;
}
}
cnt
};
let score =
|ch: f64, to_right: bool| -> (usize, f64) { (crossers(ch, to_right), (ch - mid_x).abs()) };
let chosen = match (right, left) {
(Some(r), Some(l)) => {
if score(r, true) <= score(l, false) {
Some((r, 1.0))
} else {
Some((l, -1.0))
}
}
(Some(r), None) => Some((r, 1.0)),
(None, Some(l)) => Some((l, -1.0)),
(None, None) => None,
};
if let Some((ch, _)) = chosen {
used.push((ch, top, bot));
}
chosen
}
fn settle_channel(
mut ch: f64,
to_right: bool,
top: f64,
bot: f64,
rects: &[(usize, Rect, String)],
grid: &RectGrid,
skip: &dyn Fn(&str) -> bool,
) -> Option<f64> {
for _ in 0..60 {
let area = Rect::new(ch - 1e-6, top, ch + 1e-6, bot);
let mut blocker: Option<usize> = None;
grid.for_each(area, |i| {
let (_, r, owner) = &rects[i];
if skip(owner) {
return;
}
if r.min_y() <= bot && r.max_y() >= top && r.min_x() < ch && r.max_x() > ch {
blocker = Some(blocker.map_or(i, |b: usize| b.min(i)));
}
});
let Some(i) = blocker else { return Some(ch) };
let r = rects[i].1;
ch = if to_right {
r.max_x() + CHANNEL_MARGIN
} else {
r.min_x() - CHANNEL_MARGIN
};
}
None
}
fn spline_route(s: &GGNode, t: &GGNode, s_slot: &(Port, Slot), t_slot: &(Port, Slot)) -> RoutePath {
let sp = s_slot.0;
let tp = t_slot.0;
let p0 = port_point_at(s, sp, s_slot.1);
let p3 = port_point_at(t, tp, t_slot.1);
let (ox, oy) = port_normal(sp);
let (ix, iy) = port_normal(tp);
let gap = ((p3.x - p0.x) * ox + (p3.y - p0.y) * oy).max(0.0);
let mut arc = (gap * 0.5).clamp(MIN_ARC, MAX_ARC);
if gap > 0.0 {
arc = arc.min(gap);
}
let vx = p3.x - p0.x;
let vy = p3.y - p0.y;
let tvx = vx * (1.0 - ox * ox) - vy * ox * oy;
let tvy = vy * (1.0 - oy * oy) - vx * ox * oy;
let bias = 0.25;
let p1 = Point::new(p0.x + ox * arc + tvx * bias, p0.y + oy * arc + tvy * bias);
let p2 = Point::new(p3.x + ix * arc - tvx * bias, p3.y + iy * arc - tvy * bias);
let mut r = RoutePath::new();
r.push(RouteSegment::CubicBezier { p0, p1, p2, p3 });
r
}
fn spline_route_safe(
s: &GGNode,
t: &GGNode,
s_slot: &(Port, Slot),
t_slot: &(Port, Slot),
obstacles: &Obstacles,
used_channels: &mut Vec<(f64, f64, f64)>,
) -> RoutePath {
let naive = spline_route(s, t, s_slot, t_slot);
let (sp, tp) = (s_slot.0, t_slot.0);
let vertical = matches!(sp, Port::Top | Port::Bottom);
let tr = |p: Point| if vertical { p } else { Point::new(p.y, p.x) };
let skip = edge_skip(&s.id, &t.id, &obstacles.members);
let (rects_v, grid_v) = if vertical {
(&obstacles.rects, &obstacles.grid)
} else {
(&obstacles.rects_t, &obstacles.grid_t)
};
let samples_v: Vec<Point> = sample_path(&naive, 32).iter().map(|p| tr(*p)).collect();
let mut hit = false;
let mut hit_min = f64::INFINITY;
let mut hit_max = f64::NEG_INFINITY;
for w in samples_v.windows(2) {
let area = seg_bbox(w[0], w[1]);
grid_v.for_each(area, |i| {
let (_, r, owner) = &rects_v[i];
if skip(owner) {
return;
}
if segment_intersects_rect(w[0], w[1], r) {
hit = true;
hit_min = hit_min.min(r.min_x());
hit_max = hit_max.max(r.max_x());
}
});
}
if !hit {
return naive;
}
let p0v = tr(port_point_at(s, sp, s_slot.1));
let p3v = tr(port_point_at(t, tp, t_slot.1));
let down = p3v.y >= p0v.y;
let av = Point::new(p0v.x, p0v.y + if down { STUB } else { -STUB });
let bv = Point::new(p3v.x, p3v.y + if down { -STUB } else { STUB });
let top = av.y.min(bv.y);
let bot = av.y.max(bv.y);
let mut candidates: Vec<f64> = Vec::new();
if let Some(ch) = settle_channel(
hit_max + CHANNEL_MARGIN,
true,
top,
bot,
rects_v,
grid_v,
&skip,
) {
candidates.push(ch);
}
if let Some(ch) = settle_channel(
hit_min - CHANNEL_MARGIN,
false,
top,
bot,
rects_v,
grid_v,
&skip,
) {
candidates.push(ch);
}
let (all_min, all_max) = if vertical {
(obstacles.all_min_x, obstacles.all_max_x)
} else {
(obstacles.all_min_x_t, obstacles.all_max_x_t)
};
candidates.push(all_max + CHANNEL_MARGIN);
candidates.push(all_min - CHANNEL_MARGIN);
let mut best: Option<(f64, f64)> = None; for strict in [true, false] {
for ch in &candidates {
let pts = [
p0v,
av,
Point::new(*ch, av.y),
Point::new(*ch, bv.y),
bv,
p3v,
];
if !polyline_clear(&pts, &skip, rects_v, grid_v) {
continue;
}
if strict && channel_conflicts_used(*ch, top, bot, used_channels) {
continue;
}
let cost = (ch - p0v.x).abs() + (ch - p3v.x).abs();
let better = match best {
None => true,
Some((bc, bch)) => cost < bc || (cost == bc && *ch > bch),
};
if better {
best = Some((cost, *ch));
}
}
if best.is_some() {
break;
}
}
let Some((_, ch)) = best else { return naive };
used_channels.push((ch, top, bot));
let pts_v = [p0v, av, Point::new(ch, av.y), Point::new(ch, bv.y), bv, p3v];
if vertical {
rounded_polyline(&pts_v, CORNER_RADIUS)
} else {
let pts: Vec<Point> = pts_v.iter().map(|p| tr(*p)).collect();
rounded_polyline(&pts, CORNER_RADIUS)
}
}
fn orthogonal_route(
s: &GGNode,
t: &GGNode,
s_slot: &(Port, Slot),
t_slot: &(Port, Slot),
obstacles: &Obstacles,
used_trunks: &mut Vec<(f64, f64, f64)>,
) -> RoutePath {
let (sp, tp) = (s_slot.0, t_slot.0);
let start = port_point_at(s, sp, s_slot.1);
let end = port_point_at(t, tp, t_slot.1);
let skip = edge_skip(&s.id, &t.id, &obstacles.members);
let vertical_main = matches!(sp, Port::Top | Port::Bottom);
let (a, b) = if vertical_main {
let out = if sp == Port::Bottom { STUB } else { -STUB };
let inn = if tp == Port::Top { -STUB } else { STUB };
(
Point::new(start.x, start.y + out),
Point::new(end.x, end.y + inn),
)
} else {
let out = if sp == Port::Right { STUB } else { -STUB };
let inn = if tp == Port::Left { -STUB } else { STUB };
(
Point::new(start.x + out, start.y),
Point::new(end.x + inn, end.y),
)
};
let base_trunk = if vertical_main {
(a.x + b.x) / 2.0
} else {
(a.y + b.y) / 2.0
};
let (s0, s1) = if vertical_main {
(a.y.min(b.y), a.y.max(b.y))
} else {
(a.x.min(b.x), a.x.max(b.x))
};
let build = |trunk: f64| -> Vec<Point> {
if vertical_main {
vec![
start,
a,
Point::new(trunk, a.y),
Point::new(trunk, b.y),
b,
end,
]
} else {
vec![
start,
a,
Point::new(a.x, trunk),
Point::new(b.x, trunk),
b,
end,
]
}
};
let mut candidates: Vec<f64> = vec![base_trunk];
for step in 1..=MAX_OFFSET_TRIES {
candidates.push(base_trunk + step as f64 * OFFSET_STEP);
candidates.push(base_trunk - step as f64 * OFFSET_STEP);
}
let mut best: Option<(usize, bool, f64, Vec<Point>)> = None;
for trunk in candidates {
let pts = build(trunk);
let c = polyline_conflicts(&pts, &skip, &obstacles.rects, &obstacles.grid);
let used = trunk_conflicts_used(trunk, s0, s1, used_trunks);
let better = match &best {
None => true,
Some((bc, bu, bt, _)) => {
c < *bc
|| (c == *bc && (!used && *bu))
|| (c == *bc
&& used == *bu
&& (trunk - base_trunk).abs() < (bt - base_trunk).abs())
}
};
if better {
best = Some((c, used, trunk, pts));
}
if c == 0 && !used {
break;
}
}
let Some((c, _, trunk, pts)) = best else {
return points_to_route(&build(base_trunk));
};
if c == 0 {
used_trunks.push((trunk, s0, s1));
}
points_to_route(&pts)
}
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
enum Port {
Top,
Bottom,
Left,
Right,
}
fn port_normal(p: Port) -> (f64, f64) {
match p {
Port::Top => (0.0, -1.0),
Port::Bottom => (0.0, 1.0),
Port::Left => (-1.0, 0.0),
Port::Right => (1.0, 0.0),
}
}
fn node_rect(n: &GGNode) -> Rect {
let half_w = n.size.width / 2.0 + 2.0;
let half_h = n.size.height / 2.0 + 2.0;
Rect::new(
n.center.x - half_w,
n.center.y - half_h,
n.center.x + half_w,
n.center.y + half_h,
)
}
fn pick_port(from: &GGNode, toward: &GGNode, direction: crate::ast::Direction) -> Port {
use crate::ast::Direction;
const SIDE_BIAS: f64 = 2.5;
let dx = toward.center.x - from.center.x;
let dy = toward.center.y - from.center.y;
let hw = (from.size.width / 2.0).max(1.0);
let hh = (from.size.height / 2.0).max(1.0);
match direction {
Direction::TB | Direction::TD | Direction::BT => {
if dx.abs() * hh > dy.abs() * hw * SIDE_BIAS {
if dx >= 0.0 { Port::Right } else { Port::Left }
} else if dy >= 0.0 {
Port::Bottom
} else {
Port::Top
}
}
Direction::LR | Direction::RL => {
if dy.abs() * hw > dx.abs() * hh * SIDE_BIAS {
if dy >= 0.0 { Port::Bottom } else { Port::Top }
} else if dx >= 0.0 {
Port::Right
} else {
Port::Left
}
}
}
}
fn is_back_edge(s: &GGNode, t: &GGNode, direction: crate::ast::Direction) -> bool {
use crate::ast::Direction;
match direction {
Direction::TB | Direction::TD => s.center.y > t.center.y,
Direction::BT => s.center.y < t.center.y,
Direction::LR => s.center.x > t.center.x,
Direction::RL => s.center.x < t.center.x,
}
}
fn channel_ports(side: f64, direction: crate::ast::Direction) -> (Port, Port) {
use crate::ast::Direction;
let vert = matches!(direction, Direction::TB | Direction::TD | Direction::BT);
if vert {
if side > 0.0 {
(Port::Right, Port::Right)
} else {
(Port::Left, Port::Left)
}
} else if side > 0.0 {
(Port::Bottom, Port::Bottom)
} else {
(Port::Top, Port::Top)
}
}
fn edge_port(
n: &GGNode,
peer: &GGNode,
direction: crate::ast::Direction,
is_out: bool,
is_back: bool,
side: f64,
used_reverse: Option<&HashSet<Port>>,
) -> Port {
use crate::ast::Direction;
let (out_main, in_main) = match direction {
Direction::TB | Direction::TD => (Port::Bottom, Port::Top),
Direction::BT => (Port::Top, Port::Bottom),
Direction::LR => (Port::Right, Port::Left),
Direction::RL => (Port::Left, Port::Right),
};
let (main, anti) = match (is_back, is_out) {
(false, true) | (true, false) => (out_main, in_main),
(false, false) | (true, true) => (in_main, out_main),
};
let (s1, s2) = if is_back {
side_pair_centered(direction, side)
} else {
side_pair(n, peer, direction)
};
let first = if is_back {
main
} else {
pick_port(n, peer, direction)
};
let mut cands = vec![first];
for p in [main, s1, s2, anti] {
if !cands.contains(&p) {
cands.push(p);
}
}
match used_reverse {
Some(m) => cands.into_iter().find(|p| !m.contains(p)).unwrap_or(first),
None => first,
}
}
fn side_pair_centered(direction: crate::ast::Direction, bias: f64) -> (Port, Port) {
use crate::ast::Direction;
match direction {
Direction::TB | Direction::TD | Direction::BT => {
if bias > 0.0 {
(Port::Right, Port::Left)
} else {
(Port::Left, Port::Right)
}
}
Direction::LR | Direction::RL => {
if bias > 0.0 {
(Port::Bottom, Port::Top)
} else {
(Port::Top, Port::Bottom)
}
}
}
}
fn side_pair(n: &GGNode, peer: &GGNode, direction: crate::ast::Direction) -> (Port, Port) {
let bias = match direction {
crate::ast::Direction::TB | crate::ast::Direction::TD | crate::ast::Direction::BT => {
if peer.center.x >= n.center.x {
1.0
} else {
-1.0
}
}
_ => {
if peer.center.y >= n.center.y {
1.0
} else {
-1.0
}
}
};
side_pair_centered(direction, bias)
}
fn axis_projection(port: Port, peer: Point) -> f64 {
match port {
Port::Top | Port::Bottom => peer.x,
Port::Left | Port::Right => peer.y,
}
}
fn rank_slots(
groups: HashMap<(String, Port), Vec<(usize, f64)>>,
slots: &mut [(Slot, Slot)],
is_src: bool,
) {
use std::cmp::Ordering;
for (_, mut members) in groups {
members.sort_by(|a, b| {
a.1.partial_cmp(&b.1)
.unwrap_or(Ordering::Equal)
.then(a.0.cmp(&b.0))
});
let total = members.len();
for (idx, (edge_i, _)) in members.into_iter().enumerate() {
let slot = Slot { idx, total };
if is_src {
slots[edge_i].0 = slot;
} else {
slots[edge_i].1 = slot;
}
}
}
}
fn port_point_at(n: &GGNode, p: Port, slot: Slot) -> Point {
let span = match p {
Port::Top | Port::Bottom => n.size.width,
Port::Left | Port::Right => n.size.height,
};
if slot.total <= 1 {
return port_point_offset(n, p, 0.0);
}
let mut spacing = (span / slot.total as f64).clamp(
PORT_MIN_SPACING,
(span * PORT_MAX_SPACING_RATIO).max(PORT_MIN_SPACING),
);
let usable = (span - 2.0 * PORT_CORNER_MARGIN).max(PORT_MIN_SPACING);
spacing = spacing.min(usable / (slot.total - 1) as f64);
let offset = (slot.idx as f64 - (slot.total as f64 - 1.0) / 2.0) * spacing;
port_point_offset(n, p, offset)
}
fn port_point_offset(n: &GGNode, p: Port, offset: f64) -> Point {
let (hw, hh) = (n.size.width / 2.0, n.size.height / 2.0);
let (cx, cy) = (n.center.x, n.center.y);
match n.shape {
ShapeKind::Diamond => match p {
Port::Top | Port::Bottom => {
let dx = offset.clamp(-hw * 0.75, hw * 0.75);
let sign = if p == Port::Top { -1.0 } else { 1.0 };
let y = hh * (1.0 - dx.abs() / hw.max(1e-9));
Point::new(cx + dx, cy + sign * y)
}
Port::Left | Port::Right => {
let dy = offset.clamp(-hh * 0.75, hh * 0.75);
let sign = if p == Port::Left { -1.0 } else { 1.0 };
let x = hw * (1.0 - dy.abs() / hh.max(1e-9));
Point::new(cx + sign * x, cy + dy)
}
},
ShapeKind::Circle | ShapeKind::DoubleCircle | ShapeKind::StartDot | ShapeKind::EndDot => {
match p {
Port::Top | Port::Bottom => {
let dx = offset.clamp(-hw * 0.9, hw * 0.9);
let sign = if p == Port::Top { -1.0 } else { 1.0 };
let t = (1.0 - (dx / hw.max(1e-9)).powi(2)).max(0.0).sqrt();
Point::new(cx + dx, cy + sign * hh * t)
}
Port::Left | Port::Right => {
let dy = offset.clamp(-hh * 0.9, hh * 0.9);
let sign = if p == Port::Left { -1.0 } else { 1.0 };
let t = (1.0 - (dy / hh.max(1e-9)).powi(2)).max(0.0).sqrt();
Point::new(cx + sign * hw * t, cy + dy)
}
}
}
_ => match p {
Port::Top => Point::new(cx + offset, cy - hh),
Port::Bottom => Point::new(cx + offset, cy + hh),
Port::Left => Point::new(cx - hw, cy + offset),
Port::Right => Point::new(cx + hw, cy + offset),
},
}
}
fn tr_rect(r: Rect) -> Rect {
Rect::new(r.min_y(), r.min_x(), r.max_y(), r.max_x())
}
fn rects_overlap(a: Rect, b: Rect) -> bool {
a.min_x() <= b.max_x()
&& a.max_x() >= b.min_x()
&& a.min_y() <= b.max_y()
&& a.max_y() >= b.min_y()
}
fn x_range(rects: &[(usize, Rect, String)]) -> (f64, f64) {
let mut min = f64::INFINITY;
let mut max = f64::NEG_INFINITY;
for (_, r, _) in rects {
min = min.min(r.min_x());
max = max.max(r.max_x());
}
(min, max)
}
fn polyline_clear(
pts: &[Point],
skip: &dyn Fn(&str) -> bool,
rects: &[(usize, Rect, String)],
grid: &RectGrid,
) -> bool {
for w in pts.windows(2) {
let area = seg_bbox(w[0], w[1]);
let mut clear = true;
grid.for_each(area, |i| {
if clear {
let (_, r, owner) = &rects[i];
if !skip(owner) && segment_intersects_rect(w[0], w[1], r) {
clear = false;
}
}
});
if !clear {
return false;
}
}
true
}
fn polyline_conflicts(
pts: &[Point],
skip: &dyn Fn(&str) -> bool,
rects: &[(usize, Rect, String)],
grid: &RectGrid,
) -> usize {
pts.windows(2)
.filter(|w| {
let area = seg_bbox(w[0], w[1]);
let mut hit = false;
grid.for_each(area, |i| {
if !hit {
let (_, r, owner) = &rects[i];
if !skip(owner) && segment_intersects_rect(w[0], w[1], r) {
hit = true;
}
}
});
hit
})
.count()
}
fn seg_bbox(a: Point, b: Point) -> Rect {
Rect::new(a.x.min(b.x), a.y.min(b.y), a.x.max(b.x), a.y.max(b.y))
}
fn points_to_route(points: &[Point]) -> RoutePath {
let mut pts: Vec<Point> = Vec::new();
for &p in points {
if let Some(last) = pts.last()
&& (p.x - last.x).abs() < 1e-9
&& (p.y - last.y).abs() < 1e-9
{
continue;
}
if pts.len() >= 2 {
let a = pts[pts.len() - 2];
let b = *pts.last().unwrap();
if ((b.x - a.x) * (p.y - b.y) - (b.y - a.y) * (p.x - b.x)).abs() < 1e-6 {
*pts.last_mut().unwrap() = p;
continue;
}
}
pts.push(p);
}
crate::builder::ir::geograph::line_route(&pts)
}
fn rounded_polyline(pts: &[Point], radius: f64) -> RoutePath {
let mut r = RoutePath::new();
if pts.len() < 2 {
return crate::builder::ir::geograph::line_route(pts);
}
let mut cur = pts[0];
for i in 1..pts.len().saturating_sub(1) {
let corner = pts[i];
let next = pts[i + 1];
let (d1x, d1y) = (corner.x - cur.x, corner.y - cur.y);
let (d2x, d2y) = (next.x - corner.x, next.y - corner.y);
let l1 = (d1x * d1x + d1y * d1y).sqrt();
let l2 = (d2x * d2x + d2y * d2y).sqrt();
if l1 < 1e-9 || l2 < 1e-9 {
continue;
}
let rr = radius.min(l1 * 0.5).min(l2 * 0.5);
let cs = Point::new(corner.x - d1x / l1 * rr, corner.y - d1y / l1 * rr);
let ce = Point::new(corner.x + d2x / l2 * rr, corner.y + d2y / l2 * rr);
if (cs.x - cur.x).abs() > 1e-6 || (cs.y - cur.y).abs() > 1e-6 {
r.push(RouteSegment::Line { from: cur, to: cs });
}
let p1 = Point::new(
cs.x + (corner.x - cs.x) * 2.0 / 3.0,
cs.y + (corner.y - cs.y) * 2.0 / 3.0,
);
let p2 = Point::new(
ce.x + (corner.x - ce.x) * 2.0 / 3.0,
ce.y + (corner.y - ce.y) * 2.0 / 3.0,
);
r.push(RouteSegment::CubicBezier {
p0: cs,
p1,
p2,
p3: ce,
});
cur = ce;
}
let last = *pts.last().unwrap();
if (last.x - cur.x).abs() > 1e-6 || (last.y - cur.y).abs() > 1e-6 {
r.push(RouteSegment::Line {
from: cur,
to: last,
});
}
r
}
fn sample_path(r: &RoutePath, n: usize) -> Vec<Point> {
let mut out = Vec::new();
for seg in r.iter() {
match *seg {
RouteSegment::Line { from, to } => {
for i in 0..=n {
let t = i as f64 / n as f64;
out.push(Point::new(
from.x + (to.x - from.x) * t,
from.y + (to.y - from.y) * t,
));
}
}
RouteSegment::CubicBezier { p0, p1, p2, p3 } => {
for i in 0..=n {
let t = i as f64 / n as f64;
let u = 1.0 - t;
let (a, b, c, d) = (u * u * u, 3.0 * u * u * t, 3.0 * u * t * t, t * t * t);
out.push(Point::new(
a * p0.x + b * p1.x + c * p2.x + d * p3.x,
a * p0.y + b * p1.y + c * p2.y + d * p3.y,
));
}
}
}
}
out
}
use super::spatial::segment_intersects_rect;
#[cfg(test)]
mod tests {
use super::*;
use crate::builder::ir::common::{
ArrowKind, ArrowSpec, ContainerKind, NodeDetail, NodeRole, ResolvedPorts,
};
use crate::builder::ir::geograph::{GGContainer, GGEdge, GGNode, Geograph};
use crate::builder::ir::shape::ShapeKind;
use crate::builder::ir::unigraph::EdgeKind;
fn mk_node(id: &str, x: f64, y: f64, w: f64, h: f64) -> GGNode {
let p = Point::new(x, y);
GGNode {
id: id.to_string(),
role: NodeRole::Atom,
center: p,
size: lievisual::geometry::Size::new(w, h),
shape: ShapeKind::Rectangle,
ports: ResolvedPorts {
top: Point::new(x, y - h / 2.0),
bottom: Point::new(x, y + h / 2.0),
left: Point::new(x - w / 2.0, y),
right: Point::new(x + w / 2.0, y),
},
label: None,
detail: NodeDetail::None,
}
}
fn mk_edge(s: &str, t: &str) -> GGEdge {
GGEdge {
id: format!("{}-{}", s, t),
source: s.to_string(),
target: t.to_string(),
route: RoutePath::new(),
label_text: None,
label_anchor: None,
kind: EdgeKind::Flow,
arrow: ArrowSpec {
start: ArrowKind::None,
end: ArrowKind::Arrow,
},
routing_hint: crate::builder::ir::common::RoutingHint::Orthogonal,
line_kind: crate::builder::ir::common::LineKind::Solid,
cardinality: (None, None),
cardinality_text: (None, None),
}
}
fn segs_cross(a: Point, b: Point, c: Point, d: Point) -> bool {
let cross =
|o: Point, p: Point, q: Point| (p.x - o.x) * (q.y - o.y) - (p.y - o.y) * (q.x - o.x);
let d1 = cross(c, d, a);
let d2 = cross(c, d, b);
let d3 = cross(a, b, c);
let d4 = cross(a, b, d);
((d1 > 0.0) != (d2 > 0.0)) && ((d3 > 0.0) != (d4 > 0.0))
}
#[test]
fn fan_out_spline_edges_stay_in_corridor_and_never_cross() {
let xs = [-336.0, -168.0, 0.0, 168.0, 336.0];
let mut nodes = vec![mk_node("A", 0.0, 0.0, 120.0, 60.0)];
for (i, x) in xs.iter().enumerate() {
nodes.push(mk_node(&format!("C{i}"), *x, 116.0, 120.0, 60.0));
}
let mut edges = Vec::new();
for (i, _) in xs.iter().enumerate() {
let mut e = mk_edge("A", &format!("C{i}"));
e.routing_hint = crate::builder::ir::common::RoutingHint::Spline;
edges.push(e);
}
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes,
edges,
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
for e in &gg.edges {
for p in sample_path(&e.route, 48) {
assert!(
p.y >= 30.0 - 1e-6 && p.y <= 86.0 + 1e-6,
"出边 {}-{} 逸出层间走廊: y={} (期望 30..=86)",
e.source,
e.target,
p.y
);
}
}
let samples: Vec<Vec<Point>> = gg.edges.iter().map(|e| sample_path(&e.route, 48)).collect();
for i in 0..samples.len() {
for j in (i + 1)..samples.len() {
for k in 0..samples[i].len() - 1 {
for l in 0..samples[j].len() - 1 {
assert!(
!segs_cross(
samples[i][k],
samples[i][k + 1],
samples[j][l],
samples[j][l + 1]
),
"出边 {} 与 {} 发生交叉: seg1 {:?}->{:?}, seg2 {:?}->{:?}",
gg.edges[i].target,
gg.edges[j].target,
samples[i][k],
samples[i][k + 1],
samples[j][l],
samples[j][l + 1]
);
}
}
}
}
}
#[test]
fn back_edge_enters_target_on_a_free_side() {
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("A", 0.0, 0.0, 60.0, 40.0),
mk_node("B", 0.0, 150.0, 60.0, 40.0),
mk_node("C", 0.0, 300.0, 60.0, 40.0),
mk_node("D", 0.0, 450.0, 60.0, 40.0),
],
edges: vec![
mk_edge("A", "B"),
mk_edge("B", "C"),
mk_edge("C", "D"),
mk_edge("D", "B"),
],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
let back = &gg.edges[3];
let end = back.route.end();
let on_side = ((end.x - 30.0).abs() < 1.0) || ((end.x + 30.0).abs() < 1.0);
assert!(on_side, "回边应从 B 的侧面进入, end={end:?}");
assert!(
(end.y - 170.0).abs() > 1.0,
"回边不应与 B→C 的出边共用底部端面: end={end:?}"
);
let end = gg.edges[0].route.end();
assert!(
(end.y - 130.0).abs() < 1.0,
"A→B 仍应从 B 顶部进入, end={end:?}"
);
}
#[test]
fn retry_back_edge_avoids_input_bottom() {
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("Input", 0.0, 104.0, 60.0, 40.0),
mk_node("Decision", 0.0, 208.0, 60.0, 40.0),
mk_node("Retry", 80.0, 312.0, 60.0, 40.0),
],
edges: vec![
mk_edge("Input", "Decision"),
mk_edge("Decision", "Retry"),
mk_edge("Retry", "Input"),
],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
let back = &gg.edges[2];
let end = back.route.end();
let on_side = ((end.x - 30.0).abs() < 1.0) || ((end.x + 30.0).abs() < 1.0);
assert!(on_side, "回边应从 Input 的侧面进入, end={end:?}");
let on_bottom = end.y > 123.0 && end.x.abs() < 1.0;
assert!(!on_bottom, "回边不应从 Input 底部进入: end={end:?}");
}
#[test]
fn orthogonal_route_has_orthogonal_segments_and_avoids_node() {
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("A", 0.0, 0.0, 60.0, 40.0),
mk_node("B", 200.0, 0.0, 60.0, 40.0),
mk_node("C", 100.0, 0.0, 60.0, 40.0),
],
edges: vec![mk_edge("A", "B")],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
let route = &gg.edges[0].route;
assert!(route.len() >= 3, "正交路由段过少: {:?}", route);
let c_rect = Rect::new(100.0 - 32.0, 0.0 - 22.0, 100.0 + 32.0, 0.0 + 22.0);
for seg in route.iter() {
let (a, b) = (seg.start(), seg.end());
assert!(
!segment_intersects_rect(a, b, &c_rect),
"路由穿越中间阻挡节点 C: {:?} -> {:?}",
a,
b
);
}
}
#[test]
fn route_preserves_endpoints() {
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("A", 0.0, 0.0, 60.0, 40.0),
mk_node("B", 0.0, 150.0, 60.0, 40.0),
],
edges: vec![mk_edge("A", "B")],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
let route = &gg.edges[0].route;
let start = route.start();
assert!((start.x - 0.0).abs() < 1.0, "起点 x 应≈0");
assert!(
start.y > 0.0 && start.y < 40.0,
"起点应在 A 底部出线, got {:?}",
start
);
let end = route.end();
assert!(
end.y > 110.0 && end.y < 150.0,
"终点应在 B 顶部入线, got {:?}",
end
);
}
#[test]
fn self_loop_route_bulges_right() {
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![mk_node("B", 0.0, 0.0, 120.0, 60.0)],
edges: vec![mk_edge("B", "B")],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
let route = &gg.edges[0].route;
assert!(!route.is_empty(), "自环路由不应为空");
let samples = sample_path(route, 32);
let max_x = samples
.iter()
.map(|p| p.x)
.fold(f64::NEG_INFINITY, f64::max);
assert!(max_x > 60.0 + 10.0, "自环应外凸出右边缘, max_x={max_x}");
assert!((route.start().x - 60.0).abs() < 1e-6);
assert!((route.end().x - 60.0).abs() < 1e-6);
}
#[test]
fn mutual_pair_edges_are_separated() {
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("B", 0.0, 0.0, 120.0, 60.0),
mk_node("C", 0.0, 140.0, 120.0, 60.0),
],
edges: vec![mk_edge("B", "C"), mk_edge("C", "B")],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
gg.edges[0].routing_hint = crate::builder::ir::common::RoutingHint::Spline;
gg.edges[1].routing_hint = crate::builder::ir::common::RoutingHint::Spline;
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
let x0 = gg.edges[0].route.start().x;
let x1 = gg.edges[1].route.start().x;
assert!(
(x0 - x1).abs() > 2.0,
"双向对两条边应左右分开: {x0} vs {x1}"
);
assert!(
(x0 - 0.0).abs() < 20.0 && (x1 - 0.0).abs() < 20.0,
"双向对偏移应很小(紧贴风格)"
);
}
#[test]
fn diamond_ports_lie_on_shape_boundary() {
let n = mk_node("D", 0.0, 0.0, 200.0, 120.0);
let mut n = n;
n.shape = ShapeKind::Diamond;
let p = port_point_offset(&n, Port::Bottom, 66.0);
let ratio = (p.x / 100.0).abs() + (p.y / 60.0).abs();
assert!(
(ratio - 1.0).abs() < 1e-6,
"端口应落在菱形边界上, ratio={ratio}"
);
let top = port_point_offset(&n, Port::Top, 0.0);
assert!((top.y - (-60.0)).abs() < 1e-6 && (top.x - 0.0).abs() < 1e-6);
}
#[test]
fn normal_edge_avoids_container() {
let container = GGContainer {
id: "sub1".into(),
bounds: Rect::new(-40.0, -20.0, 40.0, 100.0),
title: None,
kind: ContainerKind::Subgraph,
member_ids: vec![],
};
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("A", 0.0, -140.0, 60.0, 40.0),
mk_node("B", 0.0, 200.0, 60.0, 40.0),
],
edges: vec![mk_edge("A", "B")],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
gg.edges[0].routing_hint = crate::builder::ir::common::RoutingHint::Spline;
route_edges(&mut gg, crate::ast::Direction::TB, &[container]);
let route = &gg.edges[0].route;
for p in sample_path(route, 64) {
assert!(
!(p.x > -40.0 && p.x < 40.0 && p.y > -20.0 && p.y < 100.0),
"边 A->B 穿过容器框: {p:?}"
);
}
}
#[test]
fn intra_container_edge_stays_inside() {
let container = GGContainer {
id: "sub1".into(),
bounds: Rect::new(-80.0, -30.0, 80.0, 130.0),
title: None,
kind: ContainerKind::Subgraph,
member_ids: vec!["A".into(), "B".into()],
};
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("A", 0.0, 0.0, 60.0, 40.0),
mk_node("B", 0.0, 80.0, 60.0, 40.0),
],
edges: vec![mk_edge("A", "B")],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
gg.edges[0].routing_hint = crate::builder::ir::common::RoutingHint::Spline;
route_edges(&mut gg, crate::ast::Direction::TB, &[container]);
assert_eq!(gg.edges[0].route.len(), 1, "容器内边不应被绕行");
}
#[test]
fn orthogonal_edges_do_not_share_trunk() {
let mut gg = Geograph {
size: lievisual::geometry::Size::new(0.0, 0.0),
background: lievisual::geometry::Color::default(),
nodes: vec![
mk_node("A1", -30.0, 0.0, 60.0, 40.0),
mk_node("A2", 30.0, 0.0, 60.0, 40.0),
mk_node("B1", 30.0, 200.0, 60.0, 40.0),
mk_node("B2", -30.0, 200.0, 60.0, 40.0),
],
edges: vec![mk_edge("A1", "B1"), mk_edge("A2", "B2")],
containers: vec![],
title: None,
show_data: false,
activations: vec![],
sequence_dividers: vec![],
};
route_edges(&mut gg, crate::ast::Direction::TB, &[]);
let mut trunk_x: Vec<f64> = Vec::new();
for e in &gg.edges {
for seg in e.route.iter() {
if let RouteSegment::Line { from, to } = seg
&& (from.x - to.x).abs() < 1e-6
&& (from.y - to.y).abs() > 40.0
{
trunk_x.push(from.x);
}
}
}
assert!(trunk_x.len() >= 2, "应有至少两条正交主干: {trunk_x:?}");
for i in 0..trunk_x.len() {
for j in (i + 1)..trunk_x.len() {
assert!(
(trunk_x[i] - trunk_x[j]).abs() > 2.0,
"两条正交主干重叠: {trunk_x:?}"
);
}
}
}
}
#[cfg(test)]
mod grid_tests {
use super::*;
fn rects(items: &[(f64, f64, f64, f64)]) -> Vec<Rect> {
items
.iter()
.map(|&(x0, y0, x1, y1)| Rect::new(x0, y0, x1, y1))
.collect()
}
#[test]
fn grid_query_returns_only_overlapping_rects() {
let r = rects(&[
(0.0, 0.0, 100.0, 100.0),
(500.0, 500.0, 600.0, 600.0),
(1000.0, 0.0, 1100.0, 50.0),
]);
let grid = RectGrid::new(&r);
let mut hits: Vec<usize> = Vec::new();
grid.for_each(Rect::new(90.0, 90.0, 110.0, 110.0), |i| hits.push(i));
assert!(hits.contains(&0), "查询区域应与 0 号矩形相交: {hits:?}");
assert!(!hits.contains(&1), "远端矩形不应被返回: {hits:?}");
assert!(!hits.contains(&2), "远端矩形不应被返回: {hits:?}");
}
#[test]
fn grid_query_handles_out_of_range_and_empty() {
let r = rects(&[(0.0, 0.0, 10.0, 10.0)]);
let grid = RectGrid::new(&r);
let query = Rect::new(-1e6, -1e6, -9e5, -9e5);
let mut exact = 0usize;
grid.for_each(query, |i| {
if rects_overlap(r[i], query) {
exact += 1;
}
});
assert_eq!(exact, 0, "网格外查询不得产生精确命中");
let empty = RectGrid::new(&[]);
let mut hits = 0usize;
empty.for_each(Rect::new(-1.0, -1.0, 1.0, 1.0), |_| hits += 1);
assert_eq!(hits, 0, "空网格不应命中");
}
#[test]
fn grid_may_return_duplicates_but_never_misses() {
let r = rects(&[(-50.0, -50.0, 50.0, 50.0), (400.0, 400.0, 500.0, 500.0)]);
let grid = RectGrid::new(&r);
let mut hits: Vec<usize> = Vec::new();
grid.for_each(Rect::new(-60.0, -60.0, 60.0, 60.0), |i| hits.push(i));
assert!(hits.contains(&0));
assert!(!hits.contains(&1));
assert!(!hits.is_empty(), "查询区域至少应命中自身所在格: {hits:?}");
}
}