1use std::collections::{HashMap, HashSet};
20
21use crate::types::Position;
22
23const EPS: f64 = 0.5;
25
26const DIR_NONE: usize = 0;
27const DIR_H: usize = 1;
28const DIR_V: usize = 2;
29
30const HEURISTIC_WEIGHT: f64 = 1.1;
34
35const OFF_GOAL_ROW_BIAS: f64 = 0.04;
42
43const ESCAPE_SPREAD_BUDGET: f64 = 64.0;
45
46#[derive(Clone, Copy, Debug, Default, PartialEq)]
48pub struct SubwayRect {
49 pub x: f64,
50 pub y: f64,
51 pub w: f64,
52 pub h: f64,
53}
54
55#[derive(Clone, Copy, Debug, PartialEq)]
57pub struct SubwayConnection {
58 pub start: Position,
60 pub end: Position,
62 pub start_rect: Option<usize>,
64 pub end_rect: Option<usize>,
65}
66
67#[derive(Clone, Copy, Debug)]
69pub struct SubwayOptions {
70 pub margin: f64,
72 pub lane_gap: f64,
74 pub bend_penalty: f64,
76 pub max_grid_cells: usize,
78 pub max_expansions: usize,
80 pub max_total_expansions: usize,
82 pub crossing_penalty: f64,
84 pub overlap_factor: f64,
87}
88
89impl Default for SubwayOptions {
90 fn default() -> Self {
91 Self {
92 margin: 16.0,
93 lane_gap: 8.0,
94 bend_penalty: 60.0,
95 max_grid_cells: 400_000,
96 max_expansions: 30_000,
97 max_total_expansions: 600_000,
98 crossing_penalty: 30.0,
104 overlap_factor: 0.0,
105 }
106 }
107}
108
109type AnchorKey = (i64, i64);
112
113fn anchor_key(p: Position) -> AnchorKey {
114 (p.x.round() as i64, p.y.round() as i64)
115}
116
117pub fn route_intersects_rect(pts: &[Position], rect: SubwayRect, pad: f64) -> bool {
120 let left = rect.x - pad;
121 let right = rect.x + rect.w + pad;
122 let top = rect.y - pad;
123 let bottom = rect.y + rect.h + pad;
124 pts.windows(2).any(|w| {
125 let (a, b) = (w[0], w[1]);
126 a.x.max(b.x) >= left
127 && a.x.min(b.x) <= right
128 && a.y.max(b.y) >= top
129 && a.y.min(b.y) <= bottom
130 })
131}
132
133#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
135pub struct SubwayRoutingStats {
136 pub grid_width: usize,
137 pub grid_height: usize,
138 pub grid_cells: usize,
139 pub expansions: usize,
140 pub routed: usize,
141 pub grid_fallbacks: usize,
142 pub budget_fallbacks: usize,
143 pub no_path_fallbacks: usize,
144}
145
146impl SubwayRoutingStats {
147 pub fn fallbacks(self) -> usize {
148 self.grid_fallbacks + self.budget_fallbacks + self.no_path_fallbacks
149 }
150}
151
152pub fn compute_subway_routes(
159 rects: &[SubwayRect],
160 connections: &[SubwayConnection],
161 options: &SubwayOptions,
162) -> Vec<Vec<Position>> {
163 compute_subway_routes_with_stats(rects, connections, options).0
164}
165
166pub fn compute_subway_routes_with_stats(
167 rects: &[SubwayRect],
168 connections: &[SubwayConnection],
169 options: &SubwayOptions,
170) -> (Vec<Vec<Position>>, SubwayRoutingStats) {
171 let mut routes: Vec<Vec<Position>> = vec![Vec::new(); connections.len()];
172 let mut stats = SubwayRoutingStats::default();
173 if connections.is_empty() {
174 return (routes, stats);
175 }
176
177 let valid: Vec<usize> = (0..rects.len())
179 .filter(|&i| rects[i].w > 0.0 && rects[i].h > 0.0)
180 .collect();
181 let valid_rects: Vec<SubwayRect> = valid.iter().map(|&i| rects[i]).collect();
182
183 let inflations = compute_inflations(&valid_rects, options.margin);
189 let mut slot: HashMap<usize, usize> = HashMap::new();
191 for (slot_idx, &rect_idx) in valid.iter().enumerate() {
192 slot.insert(rect_idx, slot_idx);
193 }
194 let inflation_of = |rect_idx: Option<usize>| -> Option<&SideInflation> {
195 rect_idx.and_then(|i| slot.get(&i)).map(|&s| &inflations[s])
196 };
197 let rect_of = |rect_idx: Option<usize>| -> Option<SubwayRect> {
198 rect_idx.and_then(|i| slot.get(&i)).map(|&s| valid_rects[s])
199 };
200
201 let mut jobs: Vec<Job> = connections
206 .iter()
207 .enumerate()
208 .map(|(i, c)| Job {
209 index: i,
210 conn: *c,
211 stub_start: make_stub(
212 c.start,
213 rect_of(c.start_rect),
214 inflation_of(c.start_rect),
215 options.margin,
216 ),
217 stub_end: make_stub(
218 c.end,
219 rect_of(c.end_rect),
220 inflation_of(c.end_rect),
221 options.margin,
222 ),
223 })
224 .collect();
225
226 apply_escape_lanes(
232 &mut jobs,
233 &slot,
234 &valid_rects,
235 &inflations,
236 options.lane_gap,
237 );
238
239 let inflated: Vec<InflatedRect> = valid_rects
240 .iter()
241 .zip(inflations.iter())
242 .map(|(r, s)| InflatedRect {
243 left: r.x - s.left,
244 right: r.x + r.w + s.right,
245 top: r.y - s.top,
246 bottom: r.y + r.h + s.bottom,
247 })
248 .collect();
249
250 let mut xs_raw = Vec::with_capacity(inflated.len() * 2 + jobs.len() * 2);
253 let mut ys_raw = Vec::with_capacity(inflated.len() * 2 + jobs.len() * 2);
254 for r in &inflated {
255 xs_raw.push(r.left);
256 xs_raw.push(r.right);
257 ys_raw.push(r.top);
258 ys_raw.push(r.bottom);
259 }
260 for j in &jobs {
261 xs_raw.push(j.stub_start.x);
262 xs_raw.push(j.stub_end.x);
263 ys_raw.push(j.stub_start.y);
264 ys_raw.push(j.stub_end.y);
265 }
266 let xs = dedupe_sorted(xs_raw);
267 let ys = dedupe_sorted(ys_raw);
268 let (nx, ny) = (xs.len(), ys.len());
269 stats.grid_width = nx;
270 stats.grid_height = ny;
271 stats.grid_cells = nx.saturating_mul(ny);
272
273 if nx < 2 || ny < 2 || stats.grid_cells > options.max_grid_cells {
274 for j in &jobs {
275 routes[j.index] = elbow_route(&j.conn, j.stub_start, j.stub_end);
276 }
277 stats.grid_fallbacks = jobs.len();
278 nudge_overlaps(&mut routes, options.lane_gap, &valid_rects);
279 return (routes, stats);
280 }
281
282 let mut h_blocked = vec![false; ny * (nx - 1)];
286 let mut v_blocked = vec![false; nx * (ny - 1)];
287 for r in &inflated {
288 let ry0 = upper_bound(&ys, r.top + EPS);
290 let ry1 = lower_bound(&ys, r.bottom - EPS) as isize - 1;
291 let hx0 = (upper_bound(&xs, r.left + EPS) as isize - 1).max(0);
293 let hx1 = (lower_bound(&xs, r.right - EPS) as isize - 1).min(nx as isize - 2);
294 for yi in ry0 as isize..=ry1 {
295 let base = yi as usize * (nx - 1);
296 for xi in hx0..=hx1 {
297 h_blocked[base + xi as usize] = true;
298 }
299 }
300 let cx0 = upper_bound(&xs, r.left + EPS);
302 let cx1 = lower_bound(&xs, r.right - EPS) as isize - 1;
303 let vy0 = (upper_bound(&ys, r.top + EPS) as isize - 1).max(0);
305 let vy1 = (lower_bound(&ys, r.bottom - EPS) as isize - 1).min(ny as isize - 2);
306 for xi in cx0 as isize..=cx1 {
307 let base = xi as usize * (ny - 1);
308 for yi in vy0..=vy1 {
309 v_blocked[base + yi as usize] = true;
310 }
311 }
312 }
313
314 let states = nx * ny * 3;
317 let mut scratch = AStarScratch {
318 g_score: vec![0.0; states],
319 came_from: vec![-1; states],
320 generation: vec![0; states],
321 current_gen: 0,
322 heap: MinHeap::default(),
323 expansions_used: 0,
324 };
325
326 let mut occ = Occupancy::default();
331 let mut order: Vec<usize> = (0..jobs.len()).collect();
332 order.sort_by(|&a, &b| {
333 let span =
334 |j: &Job| (j.stub_end.x - j.stub_start.x).abs() + (j.stub_end.y - j.stub_start.y).abs();
335 span(&jobs[a])
336 .partial_cmp(&span(&jobs[b]))
337 .unwrap_or(std::cmp::Ordering::Equal)
338 .then(a.cmp(&b))
339 });
340
341 for oi in order {
342 let j = &jobs[oi];
343 let sxi = index_of(&xs, j.stub_start.x);
344 let syi = index_of(&ys, j.stub_start.y);
345 let exi = index_of(&xs, j.stub_end.x);
346 let eyi = index_of(&ys, j.stub_end.y);
347
348 let budget = options.max_expansions.min(
349 options
350 .max_total_expansions
351 .saturating_sub(scratch.expansions_used),
352 );
353
354 let s_key = anchor_key(j.conn.start);
355 let e_key = anchor_key(j.conn.end);
356
357 let expansions_before = scratch.expansions_used;
358 let mut path = None;
359 if budget > 0
360 && let (Some(sxi), Some(syi), Some(exi), Some(eyi)) = (sxi, syi, exi, eyi)
361 {
362 path = astar(
363 &xs,
364 &ys,
365 &h_blocked,
366 &v_blocked,
367 (sxi, syi),
368 (exi, eyi),
369 options,
370 2.0 * options.margin + EPS,
371 budget,
372 &mut scratch,
373 if options.crossing_penalty > 0.0 || options.overlap_factor > 0.0 {
374 Some(&occ)
375 } else {
376 None
377 },
378 s_key,
379 e_key,
380 );
381 }
382
383 match path {
384 Some(path) => {
385 stats.routed += 1;
386 let mut full = Vec::with_capacity(path.len() + 2);
387 full.push(j.conn.start);
388 full.extend(path);
389 full.push(j.conn.end);
390 let full = simplify(&full);
391 mark_occupancy(&mut occ, &xs, &ys, &full, s_key, e_key);
392 routes[j.index] = full;
393 }
394 None => {
395 if budget == 0 || scratch.expansions_used - expansions_before >= budget {
396 stats.budget_fallbacks += 1;
397 } else {
398 stats.no_path_fallbacks += 1;
399 }
400 routes[j.index] = elbow_route(&j.conn, j.stub_start, j.stub_end);
401 }
402 }
403 }
404
405 stats.expansions = scratch.expansions_used;
406 nudge_overlaps(&mut routes, options.lane_gap, &valid_rects);
407 (routes, stats)
408}
409
410struct Job {
411 index: usize,
412 conn: SubwayConnection,
413 stub_start: Position,
414 stub_end: Position,
415}
416
417#[derive(Clone, Copy)]
418struct InflatedRect {
419 left: f64,
420 right: f64,
421 top: f64,
422 bottom: f64,
423}
424
425#[derive(Clone, Copy)]
426struct SideInflation {
427 left: f64,
428 right: f64,
429 top: f64,
430 bottom: f64,
431 clear_left: f64,
434 clear_right: f64,
435}
436
437fn compute_inflations(rects: &[SubwayRect], margin: f64) -> Vec<SideInflation> {
441 let mut inf = vec![
442 SideInflation {
443 left: margin,
444 right: margin,
445 top: margin,
446 bottom: margin,
447 clear_left: f64::INFINITY,
448 clear_right: f64::INFINITY,
449 };
450 rects.len()
451 ];
452 for i in 0..rects.len() {
453 for j in (i + 1)..rects.len() {
454 let (a, b) = (rects[i], rects[j]);
455 let v_close = a.y - margin < b.y + b.h + margin && b.y - margin < a.y + a.h + margin;
458 if v_close {
459 if a.x + a.w <= b.x {
460 let gap = b.x - (a.x + a.w);
461 inf[i].clear_right = inf[i].clear_right.min(gap);
462 inf[j].clear_left = inf[j].clear_left.min(gap);
463 let half = (gap / 2.0).max(0.0);
464 if half < margin {
465 inf[i].right = inf[i].right.min(half);
466 inf[j].left = inf[j].left.min(half);
467 }
468 } else if b.x + b.w <= a.x {
469 let gap = a.x - (b.x + b.w);
470 inf[j].clear_right = inf[j].clear_right.min(gap);
471 inf[i].clear_left = inf[i].clear_left.min(gap);
472 let half = (gap / 2.0).max(0.0);
473 if half < margin {
474 inf[j].right = inf[j].right.min(half);
475 inf[i].left = inf[i].left.min(half);
476 }
477 }
478 }
479 let h_close = a.x - margin < b.x + b.w + margin && b.x - margin < a.x + a.w + margin;
480 if h_close {
481 if a.y + a.h <= b.y {
482 let half = ((b.y - (a.y + a.h)) / 2.0).max(0.0);
483 if half < margin {
484 inf[i].bottom = inf[i].bottom.min(half);
485 inf[j].top = inf[j].top.min(half);
486 }
487 } else if b.y + b.h <= a.y {
488 let half = ((a.y - (b.y + b.h)) / 2.0).max(0.0);
489 if half < margin {
490 inf[j].bottom = inf[j].bottom.min(half);
491 inf[i].top = inf[i].top.min(half);
492 }
493 }
494 }
495 }
496 }
497 inf
498}
499
500fn stub_direction(anchor: Position, rect: Option<SubwayRect>) -> f64 {
502 match rect {
503 Some(r) if r.w > 0.0 => {
504 if anchor.x >= r.x + r.w / 2.0 {
505 1.0
506 } else {
507 -1.0
508 }
509 }
510 _ => 1.0,
511 }
512}
513
514fn make_stub(
516 anchor: Position,
517 rect: Option<SubwayRect>,
518 inflation: Option<&SideInflation>,
519 margin: f64,
520) -> Position {
521 let dir = stub_direction(anchor, rect);
522 let Some(r) = rect.filter(|r| r.w > 0.0) else {
523 return Position::new(anchor.x + dir * margin, anchor.y);
524 };
525 let x = if dir > 0.0 {
526 (anchor.x + EPS).max(r.x + r.w + inflation.map_or(margin, |s| s.right))
527 } else {
528 (anchor.x - EPS).min(r.x - inflation.map_or(margin, |s| s.left))
529 };
530 Position::new(x, anchor.y)
531}
532
533fn apply_escape_lanes(
537 jobs: &mut [Job],
538 slot: &HashMap<usize, usize>,
539 valid_rects: &[SubwayRect],
540 inflations: &[SideInflation],
541 lane_gap: f64,
542) {
543 struct EscapeRef {
544 job: usize,
545 is_end: bool,
547 node_slot: usize,
548 pin_y: f64,
549 away_y: f64,
550 dir: f64,
551 anchor: AnchorKey,
552 }
553
554 let mut groups: HashMap<(usize, i8), Vec<EscapeRef>> = HashMap::new();
555 for (ji, j) in jobs.iter().enumerate() {
556 for is_end in [false, true] {
557 let (rect_idx, pin, away) = if is_end {
558 (j.conn.end_rect, j.conn.end, j.conn.start)
559 } else {
560 (j.conn.start_rect, j.conn.start, j.conn.end)
561 };
562 let Some(&s) = rect_idx.and_then(|i| slot.get(&i)) else {
563 continue;
564 };
565 let rect = valid_rects[s];
566 let dir = stub_direction(pin, Some(rect));
567 groups
568 .entry((s, if dir > 0.0 { 1 } else { -1 }))
569 .or_default()
570 .push(EscapeRef {
571 job: ji,
572 is_end,
573 node_slot: s,
574 pin_y: pin.y,
575 away_y: away.y,
576 dir,
577 anchor: anchor_key(pin),
578 });
579 }
580 }
581
582 let mut keys: Vec<(usize, i8)> = groups.keys().copied().collect();
585 keys.sort();
586
587 for key in keys {
588 let group = &groups[&key];
589 let mut anchors: HashMap<AnchorKey, (f64, f64, usize)> = HashMap::new();
591 for m in group {
592 let e = anchors.entry(m.anchor).or_insert((m.pin_y, 0.0, 0));
593 e.1 += m.away_y;
594 e.2 += 1;
595 }
596 if anchors.len() < 2 {
597 continue;
598 }
599
600 let min_y = anchors.values().map(|a| a.0).fold(f64::INFINITY, f64::min);
601 let max_y = anchors
602 .values()
603 .map(|a| a.0)
604 .fold(f64::NEG_INFINITY, f64::max);
605
606 let mut ranked: Vec<(AnchorKey, f64, f64)> = anchors
609 .iter()
610 .map(|(&k, &(pin_y, away_sum, n))| {
611 let away = away_sum / n as f64;
612 let depth = if away > pin_y {
613 max_y - pin_y
614 } else {
615 pin_y - min_y
616 };
617 (k, depth, pin_y)
618 })
619 .collect();
620 ranked.sort_by(|p, q| {
621 p.1.partial_cmp(&q.1)
622 .unwrap_or(std::cmp::Ordering::Equal)
623 .then(p.2.partial_cmp(&q.2).unwrap_or(std::cmp::Ordering::Equal))
624 .then(p.0.cmp(&q.0))
625 });
626 let rank_of: HashMap<AnchorKey, usize> =
627 ranked.iter().enumerate().map(|(i, r)| (r.0, i)).collect();
628
629 for m in group {
630 let rank = rank_of[&m.anchor];
631 if rank == 0 {
632 continue;
633 }
634 let s = inflations[m.node_slot];
635 let (inf, clear) = if m.dir > 0.0 {
636 (s.right, s.clear_right)
637 } else {
638 (s.left, s.clear_left)
639 };
640 let max_spread = ESCAPE_SPREAD_BUDGET.min(clear - inf - 4.0).max(0.0);
641 let ext = (rank as f64 * lane_gap).min(max_spread);
642 if ext > 0.0 {
643 let job = &mut jobs[m.job];
644 let stub = if m.is_end {
645 &mut job.stub_end
646 } else {
647 &mut job.stub_start
648 };
649 stub.x += m.dir * ext;
650 }
651 }
652 }
653}
654
655fn elbow_route(c: &SubwayConnection, stub_start: Position, stub_end: Position) -> Vec<Position> {
657 let mid_x = (stub_start.x + stub_end.x) / 2.0;
658 simplify(&[
659 c.start,
660 stub_start,
661 Position::new(mid_x, stub_start.y),
662 Position::new(mid_x, stub_end.y),
663 stub_end,
664 c.end,
665 ])
666}
667
668struct AStarScratch {
673 g_score: Vec<f64>,
674 came_from: Vec<i32>,
675 generation: Vec<i32>,
677 current_gen: i32,
678 heap: MinHeap,
679 expansions_used: usize,
681}
682
683#[derive(Default)]
685struct Occupancy {
686 h_edge: HashMap<usize, HashSet<AnchorKey>>,
688 v_edge: HashMap<usize, HashSet<AnchorKey>>,
690 h_vertex: HashMap<usize, HashSet<AnchorKey>>,
692 v_vertex: HashMap<usize, HashSet<AnchorKey>>,
694}
695
696fn has_foreign(set: &HashSet<AnchorKey>, k1: AnchorKey, k2: AnchorKey) -> bool {
698 set.iter().any(|k| *k != k1 && *k != k2)
699}
700
701fn add_occ(map: &mut HashMap<usize, HashSet<AnchorKey>>, idx: usize, k1: AnchorKey, k2: AnchorKey) {
702 let set = map.entry(idx).or_default();
703 set.insert(k1);
704 set.insert(k2);
705}
706
707#[allow(clippy::too_many_arguments)]
708fn astar(
709 xs: &[f64],
710 ys: &[f64],
711 h_blocked: &[bool],
712 v_blocked: &[bool],
713 start: (usize, usize),
714 goal: (usize, usize),
715 options: &SubwayOptions,
716 escape_cap: f64,
717 max_expansions: usize,
718 scratch: &mut AStarScratch,
719 occ: Option<&Occupancy>,
720 s_key: AnchorKey,
721 e_key: AnchorKey,
722) -> Option<Vec<Position>> {
723 let (nx, ny) = (xs.len(), ys.len());
724 let (sxi, syi) = start;
725 let (exi, eyi) = goal;
726 let state_of = |xi: usize, yi: usize, dir: usize| (yi * nx + xi) * 3 + dir;
727
728 const WINDOW_PAD: f64 = 800.0;
732 let xi_min = lower_bound(xs, xs[sxi].min(xs[exi]) - WINDOW_PAD);
733 let xi_max = upper_bound(xs, xs[sxi].max(xs[exi]) + WINDOW_PAD) - 1;
734 let yi_min = lower_bound(ys, ys[syi].min(ys[eyi]) - WINDOW_PAD);
735 let yi_max = upper_bound(ys, ys[syi].max(ys[eyi]) + WINDOW_PAD) - 1;
736
737 scratch.current_gen += 1;
738 let generation = scratch.current_gen;
739 scratch.heap.clear();
740
741 let (ex, ey) = (xs[exi], ys[eyi]);
742
743 let start_state = state_of(sxi, syi, DIR_NONE);
744 scratch.g_score[start_state] = 0.0;
745 scratch.came_from[start_state] = -1;
746 scratch.generation[start_state] = generation;
747 scratch.heap.push(
748 start_state,
749 ((ex - xs[sxi]).abs() + (ey - ys[syi]).abs()) * HEURISTIC_WEIGHT,
750 );
751
752 let mut expansions = 0usize;
753 while let Some(current) = scratch.heap.pop() {
754 scratch.expansions_used += 1;
755 expansions += 1;
756 if expansions > max_expansions {
757 return None;
758 }
759
760 let dir = current % 3;
761 let cell = current / 3;
762 let xi = cell % nx;
763 let yi = cell / nx;
764
765 if xi == exi && yi == eyi {
766 return Some(reconstruct(xs, ys, nx, scratch, generation, current));
767 }
768
769 let g = scratch.g_score[current];
770 let is_start = current == start_state;
776
777 for step in [-1isize, 1] {
779 let nxi = xi as isize + step;
780 if nxi < xi_min as isize || nxi > xi_max as isize {
781 continue;
782 }
783 let nxi = nxi as usize;
784 let edge = yi * (nx - 1) + if step == 1 { xi } else { nxi };
785 let len = (xs[nxi] - xs[xi]).abs();
786 if h_blocked[edge] {
787 let may_escape = is_start || (nxi == exi && yi == eyi);
788 if !may_escape || len > escape_cap {
789 continue;
790 }
791 }
792 let mut cost =
793 len * if yi == eyi {
794 1.0
795 } else {
796 1.0 + OFF_GOAL_ROW_BIAS
797 } + if dir == DIR_V {
798 options.bend_penalty
799 } else {
800 0.0
801 };
802 if let Some(occ) = occ {
803 if occ
804 .h_edge
805 .get(&edge)
806 .is_some_and(|s| has_foreign(s, s_key, e_key))
807 {
808 cost += len * options.overlap_factor;
809 }
810 if occ
811 .v_vertex
812 .get(&(yi * nx + nxi))
813 .is_some_and(|s| has_foreign(s, s_key, e_key))
814 {
815 cost += options.crossing_penalty;
816 }
817 }
818 let next = state_of(nxi, yi, DIR_H);
819 let ng = g + cost;
820 if scratch.generation[next] != generation || ng < scratch.g_score[next] {
821 scratch.g_score[next] = ng;
822 scratch.came_from[next] = current as i32;
823 scratch.generation[next] = generation;
824 let h = ((ex - xs[nxi]).abs() + (ey - ys[yi]).abs()) * HEURISTIC_WEIGHT;
825 scratch.heap.push(next, ng + h);
826 }
827 }
828
829 for step in [-1isize, 1] {
831 let nyi = yi as isize + step;
832 if nyi < yi_min as isize || nyi > yi_max as isize {
833 continue;
834 }
835 let nyi = nyi as usize;
836 let edge = xi * (ny - 1) + if step == 1 { yi } else { nyi };
837 let len = (ys[nyi] - ys[yi]).abs();
838 if v_blocked[edge] {
839 let may_escape = is_start || (xi == exi && nyi == eyi);
840 if !may_escape || len > escape_cap {
841 continue;
842 }
843 }
844 let mut cost = len
845 + if dir == DIR_H {
846 options.bend_penalty
847 } else {
848 0.0
849 };
850 if let Some(occ) = occ {
851 if occ
852 .v_edge
853 .get(&edge)
854 .is_some_and(|s| has_foreign(s, s_key, e_key))
855 {
856 cost += len * options.overlap_factor;
857 }
858 if occ
859 .h_vertex
860 .get(&(nyi * nx + xi))
861 .is_some_and(|s| has_foreign(s, s_key, e_key))
862 {
863 cost += options.crossing_penalty;
864 }
865 }
866 let next = state_of(xi, nyi, DIR_V);
867 let ng = g + cost;
868 if scratch.generation[next] != generation || ng < scratch.g_score[next] {
869 scratch.g_score[next] = ng;
870 scratch.came_from[next] = current as i32;
871 scratch.generation[next] = generation;
872 let h = ((ex - xs[xi]).abs() + (ey - ys[nyi]).abs()) * HEURISTIC_WEIGHT;
873 scratch.heap.push(next, ng + h);
874 }
875 }
876 }
877
878 None
879}
880
881fn mark_occupancy(
885 occ: &mut Occupancy,
886 xs: &[f64],
887 ys: &[f64],
888 pts: &[Position],
889 s_key: AnchorKey,
890 e_key: AnchorKey,
891) {
892 let nx = xs.len();
893 let ny = ys.len();
894 for w in pts.windows(2) {
895 let (a, b) = (w[0], w[1]);
896 if (a.y - b.y).abs() < EPS && (a.x - b.x).abs() >= EPS {
897 let Some(yi) = index_of(ys, a.y) else {
898 continue;
899 };
900 let (Some(i1), Some(i2)) = (index_of(xs, a.x.min(b.x)), index_of(xs, a.x.max(b.x)))
901 else {
902 continue;
903 };
904 for e in i1..i2 {
905 add_occ(&mut occ.h_edge, yi * (nx - 1) + e, s_key, e_key);
906 }
907 for v in (i1 + 1)..i2 {
908 add_occ(&mut occ.h_vertex, yi * nx + v, s_key, e_key);
909 }
910 } else if (a.x - b.x).abs() < EPS && (a.y - b.y).abs() >= EPS {
911 let Some(xi) = index_of(xs, a.x) else {
912 continue;
913 };
914 let (Some(i1), Some(i2)) = (index_of(ys, a.y.min(b.y)), index_of(ys, a.y.max(b.y)))
915 else {
916 continue;
917 };
918 for e in i1..i2 {
919 add_occ(&mut occ.v_edge, xi * (ny - 1) + e, s_key, e_key);
920 }
921 for v in (i1 + 1)..i2 {
922 add_occ(&mut occ.v_vertex, v * nx + xi, s_key, e_key);
923 }
924 }
925 }
926}
927
928fn reconstruct(
929 xs: &[f64],
930 ys: &[f64],
931 nx: usize,
932 scratch: &AStarScratch,
933 generation: i32,
934 end: usize,
935) -> Vec<Position> {
936 let mut pts = Vec::new();
937 let mut cur = end as i32;
938 while cur >= 0 && scratch.generation[cur as usize] == generation {
939 let state = cur as usize;
940 let cell = state / 3;
941 let xi = cell % nx;
942 let yi = cell / nx;
943 pts.push(Position::new(xs[xi], ys[yi]));
944 cur = scratch.came_from[state];
945 }
946 pts.reverse();
947 simplify(&pts)
948}
949
950fn simplify(pts: &[Position]) -> Vec<Position> {
952 let mut out: Vec<Position> = Vec::with_capacity(pts.len());
953 for &p in pts {
954 if let Some(prev) = out.last()
955 && (prev.x - p.x).abs() < EPS
956 && (prev.y - p.y).abs() < EPS
957 {
958 continue;
959 }
960 while out.len() >= 2 {
961 let a = out[out.len() - 2];
962 let b = out[out.len() - 1];
963 let collinear_x = (a.x - b.x).abs() < EPS && (b.x - p.x).abs() < EPS;
964 let collinear_y = (a.y - b.y).abs() < EPS && (b.y - p.y).abs() < EPS;
965 if collinear_x || collinear_y {
966 out.pop();
967 } else {
968 break;
969 }
970 }
971 out.push(p);
972 }
973 out
974}
975
976#[derive(Clone, Copy, PartialEq, Eq, Debug)]
981enum Axis {
982 X,
983 Y,
984}
985
986#[derive(Clone, Copy)]
987struct LaneSegment {
988 route: usize,
990 i: usize,
991 coord: f64,
993 lo: f64,
995 hi: f64,
996 pinned: bool,
998 sort_key: f64,
1000 lo_dir: f64,
1004 hi_dir: f64,
1006}
1007
1008fn lane_nesting_preference(a: &LaneSegment, b: &LaneSegment) -> f64 {
1011 let mut preference = 0.0;
1012 if a.hi < b.hi - EPS {
1013 preference += a.hi_dir;
1014 } else if b.hi < a.hi - EPS {
1015 preference -= b.hi_dir;
1016 }
1017 if a.lo > b.lo + EPS {
1018 preference += a.lo_dir;
1019 } else if b.lo > a.lo + EPS {
1020 preference -= b.lo_dir;
1021 }
1022 preference
1023}
1024
1025fn aggregate_nesting_scores(representatives: &[LaneSegment]) -> Vec<f64> {
1026 representatives
1027 .iter()
1028 .map(|a| {
1029 representatives
1030 .iter()
1031 .map(|b| lane_nesting_preference(a, b))
1032 .sum()
1033 })
1034 .collect()
1035}
1036
1037#[derive(Clone, Copy)]
1038struct LaneOrderKey {
1039 nesting_score: f64,
1040 sort_key: f64,
1041 coord: f64,
1042 stable_key: (usize, usize),
1043}
1044
1045fn compare_lane_order(a: LaneOrderKey, b: LaneOrderKey) -> std::cmp::Ordering {
1046 a.nesting_score
1047 .total_cmp(&b.nesting_score)
1048 .then(a.sort_key.total_cmp(&b.sort_key))
1049 .then(a.coord.total_cmp(&b.coord))
1050 .then(a.stable_key.cmp(&b.stable_key))
1051}
1052
1053struct Shift {
1054 seg: LaneSegment,
1055 axis: Axis,
1056 offset: f64,
1057}
1058
1059fn nudge_overlaps(routes: &mut [Vec<Position>], lane_gap: f64, rects: &[SubwayRect]) {
1070 const MAX_PASSES: usize = 3;
1071 for _ in 0..MAX_PASSES {
1072 let mut v_segs: Vec<LaneSegment> = Vec::new();
1073 let mut h_segs: Vec<LaneSegment> = Vec::new();
1074
1075 for (ri, pts) in routes.iter().enumerate() {
1076 if pts.len() < 2 {
1077 continue;
1078 }
1079 for i in 0..pts.len() - 1 {
1080 let a = pts[i];
1081 let b = pts[i + 1];
1082 let pinned = i == 0 || i == pts.len() - 2;
1083 let prev_pt = if i >= 1 { Some(pts[i - 1]) } else { None };
1084 let next_pt = pts.get(i + 2).copied();
1085 if (a.x - b.x).abs() < EPS && (a.y - b.y).abs() >= EPS {
1086 let prev = prev_pt.map_or(a.x, |p| p.x);
1087 let next = next_pt.map_or(a.x, |p| p.x);
1088 let travel_down = b.y > a.y;
1091 let (lo_nbr, hi_nbr) = if travel_down {
1092 (prev_pt, next_pt)
1093 } else {
1094 (next_pt, prev_pt)
1095 };
1096 v_segs.push(LaneSegment {
1097 route: ri,
1098 i,
1099 coord: a.x,
1100 lo: a.y.min(b.y),
1101 hi: a.y.max(b.y),
1102 pinned,
1103 sort_key: (prev + next) / 2.0,
1104 lo_dir: lo_nbr.map_or(0.0, |p| (p.x - a.x).signum_or_zero()),
1105 hi_dir: hi_nbr.map_or(0.0, |p| (p.x - a.x).signum_or_zero()),
1106 });
1107 } else if (a.y - b.y).abs() < EPS && (a.x - b.x).abs() >= EPS {
1108 let prev = prev_pt.map_or(a.y, |p| p.y);
1109 let next = next_pt.map_or(a.y, |p| p.y);
1110 let travel_right = b.x > a.x;
1111 let (lo_nbr, hi_nbr) = if travel_right {
1112 (prev_pt, next_pt)
1113 } else {
1114 (next_pt, prev_pt)
1115 };
1116 h_segs.push(LaneSegment {
1117 route: ri,
1118 i,
1119 coord: a.y,
1120 lo: a.x.min(b.x),
1121 hi: a.x.max(b.x),
1122 pinned,
1123 sort_key: (prev + next) / 2.0,
1124 lo_dir: lo_nbr.map_or(0.0, |p| (p.y - a.y).signum_or_zero()),
1125 hi_dir: hi_nbr.map_or(0.0, |p| (p.y - a.y).signum_or_zero()),
1126 });
1127 }
1128 }
1129 }
1130
1131 let mut shifts: Vec<Shift> = Vec::new();
1132 collect_shifts(&mut v_segs, Axis::X, &mut shifts, lane_gap, rects, routes);
1133 collect_shifts(&mut h_segs, Axis::Y, &mut shifts, lane_gap, rects, routes);
1134
1135 if shifts.is_empty() {
1136 break;
1137 }
1138
1139 for Shift { seg, axis, offset } in shifts {
1140 for k in [seg.i, seg.i + 1] {
1141 let p = &mut routes[seg.route][k];
1142 match axis {
1143 Axis::X => p.x += offset,
1144 Axis::Y => p.y += offset,
1145 }
1146 }
1147 }
1148 }
1149}
1150
1151trait SignumOrZero {
1152 fn signum_or_zero(self) -> f64;
1153}
1154impl SignumOrZero for f64 {
1155 fn signum_or_zero(self) -> f64 {
1157 if self == 0.0 { 0.0 } else { self.signum() }
1158 }
1159}
1160
1161fn collect_shifts(
1165 segs: &mut [LaneSegment],
1166 axis: Axis,
1167 out: &mut Vec<Shift>,
1168 lane_gap: f64,
1169 rects: &[SubwayRect],
1170 routes: &[Vec<Position>],
1171) {
1172 if segs.len() < 2 {
1173 return;
1174 }
1175 segs.sort_by(|a, b| {
1176 a.coord
1177 .partial_cmp(&b.coord)
1178 .unwrap_or(std::cmp::Ordering::Equal)
1179 .then((a.route, a.i).cmp(&(b.route, b.i)))
1180 });
1181
1182 let mut corridor: Vec<LaneSegment> = Vec::new();
1183 let mut corridor_max = f64::NEG_INFINITY;
1184 for seg in segs.iter() {
1185 if !corridor.is_empty() && seg.coord - corridor_max > lane_gap - EPS {
1186 if corridor.len() > 1 {
1187 cluster_by_overlap(&mut corridor, axis, out, lane_gap, rects, routes);
1188 }
1189 corridor.clear();
1190 corridor_max = f64::NEG_INFINITY;
1191 }
1192 corridor.push(*seg);
1193 corridor_max = corridor_max.max(seg.coord);
1194 }
1195 if corridor.len() > 1 {
1196 cluster_by_overlap(&mut corridor, axis, out, lane_gap, rects, routes);
1197 }
1198}
1199
1200fn cluster_by_overlap(
1202 corridor: &mut [LaneSegment],
1203 axis: Axis,
1204 out: &mut Vec<Shift>,
1205 lane_gap: f64,
1206 rects: &[SubwayRect],
1207 routes: &[Vec<Position>],
1208) {
1209 corridor.sort_by(|a, b| {
1210 a.lo.partial_cmp(&b.lo)
1211 .unwrap_or(std::cmp::Ordering::Equal)
1212 .then((a.route, a.i).cmp(&(b.route, b.i)))
1213 });
1214
1215 let mut cluster: Vec<LaneSegment> = Vec::new();
1216 let mut cluster_hi = f64::NEG_INFINITY;
1217 for seg in corridor.iter() {
1218 if !cluster.is_empty() && seg.lo < cluster_hi - EPS {
1221 cluster.push(*seg);
1222 cluster_hi = cluster_hi.max(seg.hi);
1223 } else {
1224 if cluster.len() > 1 {
1225 assign_lanes(&cluster, axis, out, lane_gap, rects, routes);
1226 }
1227 cluster.clear();
1228 cluster.push(*seg);
1229 cluster_hi = seg.hi;
1230 }
1231 }
1232 if cluster.len() > 1 {
1233 assign_lanes(&cluster, axis, out, lane_gap, rects, routes);
1234 }
1235}
1236
1237fn lane_blocked(seg: &LaneSegment, axis: Axis, target: f64, rects: &[SubwayRect]) -> bool {
1239 rects.iter().any(|r| match axis {
1240 Axis::X => {
1241 target > r.x + 1.0
1242 && target < r.x + r.w - 1.0
1243 && seg.hi > r.y + 1.0
1244 && seg.lo < r.y + r.h - 1.0
1245 }
1246 Axis::Y => {
1247 target > r.y + 1.0
1248 && target < r.y + r.h - 1.0
1249 && seg.hi > r.x + 1.0
1250 && seg.lo < r.x + r.w - 1.0
1251 }
1252 })
1253}
1254
1255fn assign_lanes(
1256 cluster: &[LaneSegment],
1257 axis: Axis,
1258 out: &mut Vec<Shift>,
1259 lane_gap: f64,
1260 rects: &[SubwayRect],
1261 routes: &[Vec<Position>],
1262) {
1263 let n = cluster.len();
1267 let mut parent: Vec<usize> = (0..n).collect();
1268 fn find(parent: &mut [usize], mut i: usize) -> usize {
1269 while parent[i] != i {
1270 parent[i] = parent[parent[i]];
1271 i = parent[i];
1272 }
1273 i
1274 }
1275 let mut by_key: HashMap<(bool, AnchorKey), usize> = HashMap::new();
1276 for i in 0..n {
1277 let pts = &routes[cluster[i].route];
1278 let Some((&first, &last)) = pts.first().zip(pts.last()) else {
1279 continue;
1280 };
1281 for key in [(false, anchor_key(first)), (true, anchor_key(last))] {
1282 match by_key.get(&key) {
1283 None => {
1284 by_key.insert(key, i);
1285 }
1286 Some(&seen) => {
1287 let a = find(&mut parent, seen);
1288 let b = find(&mut parent, i);
1289 if a != b {
1290 parent[b] = a;
1291 }
1292 }
1293 }
1294 }
1295 }
1296 let mut unit_map: HashMap<usize, Vec<LaneSegment>> = HashMap::new();
1297 let mut unit_order: Vec<usize> = Vec::new();
1300 for (i, seg) in cluster.iter().enumerate() {
1301 let root = find(&mut parent, i);
1302 let unit = unit_map.entry(root).or_insert_with(|| {
1303 unit_order.push(root);
1304 Vec::new()
1305 });
1306 unit.push(*seg);
1307 }
1308
1309 struct LaneUnit {
1310 segs: Vec<LaneSegment>,
1311 pinned: bool,
1312 coord: f64,
1313 sort_key: f64,
1314 rep: LaneSegment,
1317 }
1318 let units: Vec<LaneUnit> = unit_order
1319 .iter()
1320 .map(|root| {
1321 let segs = unit_map[root].clone();
1322 let mut rep = segs[0];
1323 for s in &segs {
1324 if s.hi - s.lo > rep.hi - rep.lo {
1325 rep = *s;
1326 }
1327 }
1328 LaneUnit {
1329 pinned: segs.iter().any(|s| s.pinned),
1330 coord: segs.iter().map(|s| s.coord).sum::<f64>() / segs.len() as f64,
1331 sort_key: segs.iter().map(|s| s.sort_key).sum::<f64>() / segs.len() as f64,
1332 rep,
1333 segs,
1334 }
1335 })
1336 .collect();
1337
1338 let push_shift = |seg: &LaneSegment, target: f64, out: &mut Vec<Shift>| {
1342 let want = target - seg.coord;
1343 if want.abs() <= EPS / 2.0 {
1344 return;
1345 }
1346 for f in [1.0, 0.75, 0.5, 0.25] {
1347 let t = seg.coord + want * f;
1348 if !lane_blocked(seg, axis, t, rects) {
1349 out.push(Shift {
1350 seg: *seg,
1351 axis,
1352 offset: want * f,
1353 });
1354 return;
1355 }
1356 }
1357 };
1358
1359 let pinned_units: Vec<&LaneUnit> = units.iter().filter(|u| u.pinned).collect();
1362 for u in &pinned_units {
1363 let anchored: Vec<&LaneSegment> = u.segs.iter().filter(|s| s.pinned).collect();
1364 let line = anchored.iter().map(|s| s.coord).sum::<f64>() / anchored.len() as f64;
1365 for seg in &u.segs {
1366 if !seg.pinned {
1367 push_shift(seg, line, out);
1368 }
1369 }
1370 }
1371
1372 let movable_units: Vec<&LaneUnit> = units.iter().filter(|unit| !unit.pinned).collect();
1377 let representatives: Vec<_> = movable_units.iter().map(|unit| unit.rep).collect();
1378 let nesting_scores = aggregate_nesting_scores(&representatives);
1379 let mut movable: Vec<_> = movable_units.into_iter().zip(nesting_scores).collect();
1380 movable.sort_by(|(a, a_score), (b, b_score)| {
1381 compare_lane_order(
1382 LaneOrderKey {
1383 nesting_score: *a_score,
1384 sort_key: a.sort_key,
1385 coord: a.coord,
1386 stable_key: (a.rep.route, a.rep.i),
1387 },
1388 LaneOrderKey {
1389 nesting_score: *b_score,
1390 sort_key: b.sort_key,
1391 coord: b.coord,
1392 stable_key: (b.rep.route, b.rep.i),
1393 },
1394 )
1395 });
1396 let movable: Vec<_> = movable.into_iter().map(|(unit, _)| unit).collect();
1397 if movable.is_empty() {
1398 return;
1399 }
1400
1401 if !pinned_units.is_empty() {
1402 let center = pinned_units.iter().map(|u| u.coord).sum::<f64>() / pinned_units.len() as f64;
1404 for (k, u) in movable.iter().enumerate() {
1405 let lane = (k / 2) as f64 + 1.0;
1406 let side = if k % 2 == 0 { 1.0 } else { -1.0 };
1407 let target = center + side * lane * lane_gap;
1408 for seg in &u.segs {
1409 push_shift(seg, target, out);
1410 }
1411 }
1412 return;
1413 }
1414
1415 let n = movable.len();
1416 let center = movable.iter().map(|u| u.coord).sum::<f64>() / n as f64;
1417
1418 let mut range_lo = f64::INFINITY;
1424 let mut range_hi = f64::NEG_INFINITY;
1425 for u in &movable {
1426 for s in &u.segs {
1427 range_lo = range_lo.min(s.lo);
1428 range_hi = range_hi.max(s.hi);
1429 }
1430 }
1431 const PAD: f64 = 2.0;
1432 let mut band_lo = f64::NEG_INFINITY;
1433 let mut band_hi = f64::INFINITY;
1434 for r in rects {
1435 let (r_lo, r_hi, s_lo, s_hi) = match axis {
1436 Axis::X => (r.x, r.x + r.w, r.y, r.y + r.h),
1437 Axis::Y => (r.y, r.y + r.h, r.x, r.x + r.w),
1438 };
1439 if s_hi <= range_lo + 1.0 || s_lo >= range_hi - 1.0 {
1440 continue;
1441 }
1442 if r_hi <= center {
1443 band_lo = band_lo.max(r_hi);
1444 } else if r_lo >= center {
1445 band_hi = band_hi.min(r_lo);
1446 }
1447 }
1450
1451 let span = (n as f64 - 1.0) * lane_gap;
1452 let mut spacing = lane_gap;
1453 let mut start = center - span / 2.0;
1454 let lo = band_lo + PAD;
1455 let hi = band_hi - PAD;
1456 if lo.is_finite() && hi.is_finite() {
1457 let width = hi - lo;
1458 if width <= 0.0 {
1459 spacing = 0.0;
1460 start = center;
1461 } else {
1462 spacing = if n > 1 {
1463 lane_gap.min(width / (n as f64 - 1.0))
1464 } else {
1465 0.0
1466 };
1467 start = center - (spacing * (n as f64 - 1.0)) / 2.0;
1468 start = start.max(lo).min(hi - spacing * (n as f64 - 1.0));
1469 }
1470 } else if lo.is_finite() {
1471 start = start.max(lo);
1472 } else if hi.is_finite() {
1473 start = start.min(hi - span);
1474 }
1475
1476 for (k, u) in movable.iter().enumerate() {
1477 let target = start + k as f64 * spacing;
1478 for seg in &u.segs {
1479 let offset = target - seg.coord;
1480 if offset.abs() <= EPS / 2.0 {
1481 continue;
1482 }
1483 if lane_blocked(seg, axis, target, rects) {
1484 continue;
1485 }
1486 out.push(Shift {
1487 seg: *seg,
1488 axis,
1489 offset,
1490 });
1491 }
1492 }
1493}
1494
1495fn dedupe_sorted(mut values: Vec<f64>) -> Vec<f64> {
1500 values.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
1501 let mut out: Vec<f64> = Vec::with_capacity(values.len());
1502 for v in values {
1503 if out.last().is_none_or(|&last| v - last > EPS) {
1504 out.push(v);
1505 }
1506 }
1507 out
1508}
1509
1510fn lower_bound(arr: &[f64], v: f64) -> usize {
1512 arr.partition_point(|&x| x < v)
1513}
1514
1515fn upper_bound(arr: &[f64], v: f64) -> usize {
1517 arr.partition_point(|&x| x <= v)
1518}
1519
1520fn index_of(arr: &[f64], v: f64) -> Option<usize> {
1522 let i = lower_bound(arr, v - EPS);
1523 if i < arr.len() && (arr[i] - v).abs() <= EPS {
1524 Some(i)
1525 } else {
1526 None
1527 }
1528}
1529
1530#[derive(Default)]
1533struct MinHeap {
1534 items: Vec<(f64, usize)>,
1535}
1536
1537impl MinHeap {
1538 fn clear(&mut self) {
1539 self.items.clear();
1540 }
1541
1542 fn less(a: (f64, usize), b: (f64, usize)) -> bool {
1543 match a.0.partial_cmp(&b.0) {
1544 Some(std::cmp::Ordering::Less) => true,
1545 Some(std::cmp::Ordering::Equal) => a.1 < b.1,
1546 _ => false,
1547 }
1548 }
1549
1550 fn push(&mut self, item: usize, score: f64) {
1551 self.items.push((score, item));
1552 let mut i = self.items.len() - 1;
1553 while i > 0 {
1554 let parent = (i - 1) / 2;
1555 if !Self::less(self.items[i], self.items[parent]) {
1556 break;
1557 }
1558 self.items.swap(i, parent);
1559 i = parent;
1560 }
1561 }
1562
1563 fn pop(&mut self) -> Option<usize> {
1564 if self.items.is_empty() {
1565 return None;
1566 }
1567 let top = self.items[0].1;
1568 let last = self.items.pop().unwrap();
1569 if !self.items.is_empty() {
1570 self.items[0] = last;
1571 let mut i = 0;
1572 loop {
1573 let (l, r) = (i * 2 + 1, i * 2 + 2);
1574 let mut smallest = i;
1575 if l < self.items.len() && Self::less(self.items[l], self.items[smallest]) {
1576 smallest = l;
1577 }
1578 if r < self.items.len() && Self::less(self.items[r], self.items[smallest]) {
1579 smallest = r;
1580 }
1581 if smallest == i {
1582 break;
1583 }
1584 self.items.swap(i, smallest);
1585 i = smallest;
1586 }
1587 }
1588 Some(top)
1589 }
1590}
1591
1592#[cfg(test)]
1593mod tests {
1594 use super::*;
1595
1596 fn p(x: f64, y: f64) -> Position {
1597 Position::new(x, y)
1598 }
1599
1600 fn assert_orthogonal(route: &[Position]) {
1602 for w in route.windows(2) {
1603 let dx = (w[0].x - w[1].x).abs();
1604 let dy = (w[0].y - w[1].y).abs();
1605 assert!(
1606 dx < EPS || dy < EPS,
1607 "diagonal segment {:?} → {:?}",
1608 w[0],
1609 w[1]
1610 );
1611 }
1612 }
1613
1614 fn crosses_interior(route: &[Position], r: SubwayRect) -> bool {
1616 let pad = 1.0;
1617 route.windows(2).any(|w| {
1618 let (a, b) = (w[0], w[1]);
1619 a.x.min(b.x) < r.x + r.w - pad
1620 && a.x.max(b.x) > r.x + pad
1621 && a.y.min(b.y) < r.y + r.h - pad
1622 && a.y.max(b.y) > r.y + pad
1623 })
1624 }
1625
1626 #[test]
1627 fn routes_are_orthogonal_and_touch_both_anchors() {
1628 let rects = [
1629 SubwayRect {
1630 x: 0.0,
1631 y: 0.0,
1632 w: 100.0,
1633 h: 60.0,
1634 },
1635 SubwayRect {
1636 x: 300.0,
1637 y: 200.0,
1638 w: 100.0,
1639 h: 60.0,
1640 },
1641 ];
1642 let conns = [SubwayConnection {
1643 start: p(100.0, 30.0),
1644 end: p(300.0, 230.0),
1645 start_rect: Some(0),
1646 end_rect: Some(1),
1647 }];
1648 let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1649 assert_eq!(routes.len(), 1);
1650 let r = &routes[0];
1651 assert!(r.len() >= 2);
1652 assert_eq!(r[0], conns[0].start);
1653 assert_eq!(*r.last().unwrap(), conns[0].end);
1654 assert_orthogonal(r);
1655 }
1656
1657 #[test]
1658 fn route_goes_around_a_blocking_node() {
1659 let rects = [
1661 SubwayRect {
1662 x: 0.0,
1663 y: 0.0,
1664 w: 80.0,
1665 h: 40.0,
1666 },
1667 SubwayRect {
1668 x: 150.0,
1669 y: -60.0,
1670 w: 60.0,
1671 h: 160.0,
1672 },
1673 SubwayRect {
1674 x: 300.0,
1675 y: 0.0,
1676 w: 80.0,
1677 h: 40.0,
1678 },
1679 ];
1680 let conns = [SubwayConnection {
1681 start: p(80.0, 20.0),
1682 end: p(300.0, 20.0),
1683 start_rect: Some(0),
1684 end_rect: Some(2),
1685 }];
1686 let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1687 let r = &routes[0];
1688 assert_orthogonal(r);
1689 assert!(
1690 !crosses_interior(r, rects[1]),
1691 "route tunnels the wall: {r:?}"
1692 );
1693 assert!(r.len() > 2, "expected a detour, got {r:?}");
1695 }
1696
1697 #[test]
1698 fn parallel_wires_do_not_share_a_corridor() {
1699 let rects = [
1702 SubwayRect {
1703 x: 0.0,
1704 y: 0.0,
1705 w: 80.0,
1706 h: 40.0,
1707 },
1708 SubwayRect {
1709 x: 400.0,
1710 y: 300.0,
1711 w: 80.0,
1712 h: 40.0,
1713 },
1714 SubwayRect {
1715 x: 0.0,
1716 y: 100.0,
1717 w: 80.0,
1718 h: 40.0,
1719 },
1720 SubwayRect {
1721 x: 400.0,
1722 y: 400.0,
1723 w: 80.0,
1724 h: 40.0,
1725 },
1726 ];
1727 let conns = [
1728 SubwayConnection {
1729 start: p(80.0, 20.0),
1730 end: p(400.0, 320.0),
1731 start_rect: Some(0),
1732 end_rect: Some(1),
1733 },
1734 SubwayConnection {
1735 start: p(80.0, 120.0),
1736 end: p(400.0, 420.0),
1737 start_rect: Some(2),
1738 end_rect: Some(3),
1739 },
1740 ];
1741 let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1742
1743 let verticals = |r: &Vec<Position>| -> Vec<(f64, f64, f64)> {
1746 r.windows(2)
1747 .filter(|w| (w[0].x - w[1].x).abs() < EPS && (w[0].y - w[1].y).abs() >= EPS)
1748 .map(|w| (w[0].x, w[0].y.min(w[1].y), w[0].y.max(w[1].y)))
1749 .collect()
1750 };
1751 for a in verticals(&routes[0]) {
1752 for b in verticals(&routes[1]) {
1753 let same_corridor = (a.0 - b.0).abs() < EPS;
1754 let overlaps = a.1 < b.2 - EPS && b.1 < a.2 - EPS;
1755 assert!(
1756 !(same_corridor && overlaps),
1757 "vertical runs overlap: {a:?} vs {b:?}"
1758 );
1759 }
1760 }
1761 }
1762
1763 #[test]
1764 fn wires_from_one_pin_share_their_trunk() {
1765 let rects = [
1768 SubwayRect {
1769 x: 0.0,
1770 y: 0.0,
1771 w: 80.0,
1772 h: 120.0,
1773 },
1774 SubwayRect {
1775 x: 300.0,
1776 y: 0.0,
1777 w: 80.0,
1778 h: 40.0,
1779 },
1780 SubwayRect {
1781 x: 300.0,
1782 y: 200.0,
1783 w: 80.0,
1784 h: 40.0,
1785 },
1786 ];
1787 let start = p(80.0, 60.0);
1788 let conns = [
1789 SubwayConnection {
1790 start,
1791 end: p(300.0, 20.0),
1792 start_rect: Some(0),
1793 end_rect: Some(1),
1794 },
1795 SubwayConnection {
1796 start,
1797 end: p(300.0, 220.0),
1798 start_rect: Some(0),
1799 end_rect: Some(2),
1800 },
1801 ];
1802 let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1803 for r in &routes {
1804 assert_eq!(r[0], start, "route must start at the shared pin");
1805 assert_orthogonal(r);
1806 }
1807 assert!(
1809 (routes[0][1].x - routes[1][1].x).abs() < EPS,
1810 "trunk split: {:?} vs {:?}",
1811 routes[0][1],
1812 routes[1][1]
1813 );
1814 }
1815
1816 #[test]
1817 fn missing_rects_still_route() {
1818 let conns = [SubwayConnection {
1820 start: p(0.0, 0.0),
1821 end: p(200.0, 100.0),
1822 start_rect: None,
1823 end_rect: None,
1824 }];
1825 let routes = compute_subway_routes(&[], &conns, &SubwayOptions::default());
1826 assert_eq!(routes.len(), 1);
1827 assert_orthogonal(&routes[0]);
1828 assert_eq!(routes[0][0], conns[0].start);
1829 assert_eq!(*routes[0].last().unwrap(), conns[0].end);
1830 }
1831
1832 #[test]
1833 fn solving_is_deterministic() {
1834 let rects = [
1835 SubwayRect {
1836 x: 0.0,
1837 y: 0.0,
1838 w: 80.0,
1839 h: 40.0,
1840 },
1841 SubwayRect {
1842 x: 200.0,
1843 y: 90.0,
1844 w: 80.0,
1845 h: 40.0,
1846 },
1847 SubwayRect {
1848 x: 120.0,
1849 y: -40.0,
1850 w: 40.0,
1851 h: 200.0,
1852 },
1853 ];
1854 let conns = [
1855 SubwayConnection {
1856 start: p(80.0, 20.0),
1857 end: p(200.0, 110.0),
1858 start_rect: Some(0),
1859 end_rect: Some(1),
1860 },
1861 SubwayConnection {
1862 start: p(80.0, 30.0),
1863 end: p(200.0, 100.0),
1864 start_rect: Some(0),
1865 end_rect: Some(1),
1866 },
1867 ];
1868 let a = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1869 let b = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1870 assert_eq!(a, b);
1871 }
1872
1873 #[test]
1874 fn simplify_drops_duplicates_and_collinear_points() {
1875 let pts = [
1876 p(0.0, 0.0),
1877 p(0.0, 0.0),
1878 p(10.0, 0.0),
1879 p(20.0, 0.0),
1880 p(20.0, 10.0),
1881 ];
1882 assert_eq!(
1883 simplify(&pts),
1884 vec![p(0.0, 0.0), p(20.0, 0.0), p(20.0, 10.0)]
1885 );
1886 }
1887
1888 #[test]
1889 fn route_intersects_rect_detects_near_misses() {
1890 let route = [p(0.0, 0.0), p(100.0, 0.0), p(100.0, 100.0)];
1891 let far = SubwayRect {
1892 x: 200.0,
1893 y: 200.0,
1894 w: 10.0,
1895 h: 10.0,
1896 };
1897 let near = SubwayRect {
1898 x: 50.0,
1899 y: 5.0,
1900 w: 10.0,
1901 h: 10.0,
1902 };
1903 assert!(!route_intersects_rect(&route, far, 4.0));
1904 assert!(route_intersects_rect(&route, near, 8.0));
1905 }
1906
1907 #[test]
1908 fn aggregate_nesting_order_resolves_pairwise_preference_cycle() {
1909 let segment = |route, lo, hi, lo_dir, hi_dir| LaneSegment {
1910 route,
1911 i: 0,
1912 coord: 10.0,
1913 lo,
1914 hi,
1915 pinned: false,
1916 sort_key: 0.0,
1917 lo_dir,
1918 hi_dir,
1919 };
1920 let a = segment(0, 1.0, 3.0, -1.0, 1.0);
1923 let b = segment(1, 0.0, 3.0, -1.0, -1.0);
1924 let c = segment(2, 1.0, 4.0, 0.0, -1.0);
1925 assert!(lane_nesting_preference(&a, &b) < 0.0);
1926 assert!(lane_nesting_preference(&b, &c) < 0.0);
1927 assert!(lane_nesting_preference(&c, &a) < 0.0);
1928
1929 let permutations = [
1930 vec![a, b, c],
1931 vec![a, c, b],
1932 vec![b, a, c],
1933 vec![b, c, a],
1934 vec![c, a, b],
1935 vec![c, b, a],
1936 ];
1937 for representatives in permutations {
1938 let scores = aggregate_nesting_scores(&representatives);
1939 let mut ranked: Vec<_> = representatives.into_iter().zip(scores).collect();
1940 ranked.sort_by(|(a, a_score), (b, b_score)| {
1941 compare_lane_order(
1942 LaneOrderKey {
1943 nesting_score: *a_score,
1944 sort_key: a.sort_key,
1945 coord: a.coord,
1946 stable_key: (a.route, a.i),
1947 },
1948 LaneOrderKey {
1949 nesting_score: *b_score,
1950 sort_key: b.sort_key,
1951 coord: b.coord,
1952 stable_key: (b.route, b.i),
1953 },
1954 )
1955 });
1956 assert_eq!(
1957 ranked
1958 .into_iter()
1959 .map(|(segment, _)| segment.route)
1960 .collect::<Vec<_>>(),
1961 vec![0, 1, 2]
1962 );
1963 }
1964 }
1965
1966 #[test]
1967 fn oversized_grid_falls_back_to_elbows() {
1968 let rects = [
1969 SubwayRect {
1970 x: 0.0,
1971 y: 0.0,
1972 w: 80.0,
1973 h: 40.0,
1974 },
1975 SubwayRect {
1976 x: 300.0,
1977 y: 0.0,
1978 w: 80.0,
1979 h: 40.0,
1980 },
1981 ];
1982 let conns = [SubwayConnection {
1983 start: p(80.0, 20.0),
1984 end: p(300.0, 20.0),
1985 start_rect: Some(0),
1986 end_rect: Some(1),
1987 }];
1988 let opts = SubwayOptions {
1989 max_grid_cells: 1,
1990 ..Default::default()
1991 };
1992 let routes = compute_subway_routes(&rects, &conns, &opts);
1993 assert_orthogonal(&routes[0]);
1994 assert_eq!(routes[0][0], conns[0].start);
1995 assert_eq!(*routes[0].last().unwrap(), conns[0].end);
1996 }
1997}