Line data Source code
1 : //! Routes: straight when clear, around one obstacle, through a
2 : //! corridor, the fallback when boxed in, port sides, and determinism.
3 :
4 : use super::{Connector, Options, Point, Port, Rect, Route, Router, Side};
5 :
6 86 : fn rect(x: f32, y: f32, w: f32, h: f32) -> Rect {
7 86 : Rect::from_min_size([x, y], w, h)
8 86 : }
9 :
10 59 : fn right(x: f32, y: f32) -> Port {
11 59 : Port::new([x, y], Side::Right)
12 59 : }
13 :
14 59 : fn left(x: f32, y: f32) -> Port {
15 59 : Port::new([x, y], Side::Left)
16 59 : }
17 :
18 17 : fn router(obstacles: &[Rect]) -> Router {
19 17 : Router::new(Options::default()).with_obstacles(obstacles.iter().copied())
20 17 : }
21 :
22 : /// Every segment is horizontal or vertical.
23 53 : fn assert_orthogonal(route: &Route) {
24 141 : for w in route.points.windows(2) {
25 141 : assert!(
26 141 : w[0].x == w[1].x || w[0].y == w[1].y,
27 : "a slanted segment: {:?}",
28 : route.points
29 : );
30 : }
31 53 : }
32 :
33 : /// No segment enters an obstacle's inside, except within `slack` of
34 : /// the route's own ports.
35 52 : fn assert_clear(route: &Route, obstacles: &[Rect]) {
36 120483 : let inside = |o: &Rect, p: Point| {
37 120483 : p.x > o.min.x + 0.01 && p.x < o.max.x - 0.01 && p.y > o.min.y + 0.01 && p.y < o.max.y - 0.01
38 120483 : };
39 138 : for w in route.points.windows(2) {
40 4554 : for k in 0..=32 {
41 4554 : let t = k as f32 / 32.0;
42 4554 : let p = Point::new(
43 4554 : w[0].x + (w[1].x - w[0].x) * t,
44 4554 : w[0].y + (w[1].y - w[0].y) * t,
45 : );
46 120483 : for o in obstacles {
47 120483 : assert!(!inside(o, p), "{p:?} is inside {o:?}: {:?}", route.points);
48 : }
49 : }
50 : }
51 52 : }
52 :
53 : #[test]
54 1 : fn a_clear_line_is_one_straight_segment() {
55 1 : let nodes = [rect(0.0, 0.0, 100.0, 60.0), rect(300.0, 0.0, 100.0, 60.0)];
56 1 : let wire = Connector::new(right(100.0, 30.0), left(300.0, 30.0));
57 1 : let route = router(&nodes).route(&wire);
58 1 : assert!(route.routed);
59 1 : assert_eq!(route.points, vec![wire.from.at, wire.to.at]);
60 1 : assert_eq!(route.bends(), 0);
61 1 : assert_eq!(route.length(), 200.0);
62 1 : }
63 :
64 : #[test]
65 1 : fn offset_ports_take_two_bends() {
66 1 : let nodes = [rect(0.0, 0.0, 100.0, 60.0), rect(300.0, 100.0, 100.0, 60.0)];
67 1 : let wire = Connector::new(right(100.0, 30.0), left(300.0, 130.0));
68 1 : let route = router(&nodes).route(&wire);
69 1 : assert!(route.routed);
70 1 : assert_eq!(route.bends(), 2);
71 1 : assert_orthogonal(&route);
72 1 : assert_clear(&route, &nodes);
73 : // Out to the right, in from the left.
74 1 : assert!(route.points[1].x > wire.from.at.x);
75 1 : assert!(route.points[route.points.len() - 2].x < wire.to.at.x);
76 1 : }
77 :
78 : #[test]
79 1 : fn a_node_in_the_way_is_gone_around() {
80 1 : let nodes = [
81 1 : rect(0.0, 0.0, 100.0, 60.0),
82 1 : rect(400.0, 0.0, 100.0, 60.0),
83 1 : rect(200.0, -40.0, 100.0, 140.0),
84 1 : ];
85 1 : let wire = Connector::new(right(100.0, 30.0), left(400.0, 30.0));
86 1 : let route = router(&nodes).route(&wire);
87 1 : assert!(route.routed);
88 1 : assert_orthogonal(&route);
89 1 : assert_clear(&route, &nodes);
90 1 : assert_eq!(route.bends(), 4);
91 : // At the margin's distance, above or below the wall.
92 1 : let margin = Options::default().margin;
93 1 : assert!(
94 1 : route
95 1 : .points
96 1 : .iter()
97 3 : .any(|p| p.y == -40.0 - margin || p.y == 100.0 + margin),
98 : "{:?}",
99 : route.points
100 : );
101 1 : }
102 :
103 : #[test]
104 1 : fn a_corridor_between_two_nodes_is_taken() {
105 : // A wall with a gap: the route goes through the gap rather than
106 : // around the whole wall.
107 1 : let nodes = [
108 1 : rect(0.0, 0.0, 100.0, 60.0),
109 1 : rect(600.0, 400.0, 100.0, 60.0),
110 1 : rect(250.0, -1000.0, 100.0, 1200.0),
111 1 : rect(250.0, 260.0, 100.0, 1000.0),
112 1 : ];
113 1 : let wire = Connector::new(right(100.0, 30.0), left(600.0, 430.0));
114 1 : let route = router(&nodes).route(&wire);
115 1 : assert!(route.routed);
116 1 : assert_orthogonal(&route);
117 1 : assert_clear(&route, &nodes);
118 1 : let through = route
119 1 : .points
120 1 : .windows(2)
121 3 : .any(|w| w[0].y == w[1].y && w[0].y > 200.0 && w[0].y < 260.0);
122 1 : assert!(through, "not through the gap: {:?}", route.points);
123 1 : assert!(route.length() < 1200.0);
124 1 : }
125 :
126 : #[test]
127 1 : fn a_backward_wire_goes_around_its_own_nodes() {
128 : // The input is left of the output: out right, around, in from the
129 : // left, never through either node.
130 1 : let nodes = [rect(300.0, 0.0, 100.0, 60.0), rect(0.0, 0.0, 100.0, 60.0)];
131 1 : let wire = Connector::new(right(400.0, 30.0), left(0.0, 30.0));
132 1 : let route = router(&nodes).route(&wire);
133 1 : assert!(route.routed);
134 1 : assert_orthogonal(&route);
135 1 : assert_clear(&route, &nodes);
136 1 : assert!(route.points[1].x > 400.0);
137 1 : assert!(route.points[route.points.len() - 2].x < 0.0);
138 1 : }
139 :
140 : #[test]
141 1 : fn top_and_bottom_ports_leave_vertically() {
142 1 : let nodes = [rect(0.0, 0.0, 100.0, 60.0), rect(0.0, 200.0, 100.0, 60.0)];
143 1 : let wire = Connector::new(
144 1 : Port::new([50.0, 60.0], Side::Bottom),
145 1 : Port::new([50.0, 200.0], Side::Top),
146 : );
147 1 : let route = router(&nodes).route(&wire);
148 1 : assert!(route.routed);
149 1 : assert_eq!(route.points, vec![wire.from.at, wire.to.at]);
150 1 : }
151 :
152 : #[test]
153 1 : fn a_boxed_in_port_falls_back_to_one_elbow() {
154 : // The second node is walled in on every side.
155 1 : let target = rect(400.0, 0.0, 100.0, 60.0);
156 1 : let nodes = [
157 1 : rect(0.0, 0.0, 100.0, 60.0),
158 1 : target,
159 1 : rect(340.0, -60.0, 220.0, 40.0),
160 1 : rect(340.0, 80.0, 220.0, 40.0),
161 1 : rect(340.0, -60.0, 40.0, 180.0),
162 1 : rect(520.0, -60.0, 40.0, 180.0),
163 1 : ];
164 1 : let wire = Connector::new(right(100.0, 30.0), left(400.0, 50.0));
165 1 : let route = router(&nodes).route(&wire);
166 1 : assert!(!route.routed);
167 1 : assert_orthogonal(&route);
168 1 : assert_eq!(route.points.first(), Some(&wire.from.at));
169 1 : assert_eq!(route.points.last(), Some(&wire.to.at));
170 : // Out, one elbow halfway, in: the stubs merge into its arms.
171 1 : assert_eq!(route.bends(), 2);
172 1 : assert_eq!(route.points[1].x, 250.0);
173 1 : }
174 :
175 : #[test]
176 1 : fn a_coordinate_that_is_not_finite_falls_back_to_a_segment() {
177 1 : let wire = Connector::new(right(f32::NAN, 0.0), left(10.0, 0.0));
178 1 : let route = router(&[]).route(&wire);
179 1 : assert!(!route.routed);
180 1 : assert_eq!(route.points.len(), 2);
181 1 : }
182 :
183 : #[test]
184 1 : fn routes_are_deterministic() {
185 1 : let (nodes, wires) = rows_and_columns();
186 1 : let mut a = router(&nodes);
187 1 : let first = a.route_all(&wires);
188 1 : let again = a.route_all(&wires);
189 1 : let fresh = router(&nodes).route_all(&wires);
190 1 : assert_eq!(first, again);
191 1 : assert_eq!(first, fresh);
192 24 : for r in &first {
193 24 : assert!(r.routed);
194 24 : assert_orthogonal(r);
195 24 : assert_clear(r, &nodes);
196 : }
197 1 : }
198 :
199 : #[test]
200 1 : fn wires_sharing_a_channel_are_spread_apart() {
201 1 : let (nodes, wires) = rows_and_columns();
202 1 : let routes = router(&nodes).route_all(&wires);
203 24 : for (i, ri) in routes.iter().enumerate() {
204 276 : for rj in &routes[i + 1..] {
205 276 : for a in inner_segments(ri) {
206 198 : for b in inner_segments(rj) {
207 153 : assert!(!overlap(a, b), "{a:?} on top of {b:?}");
208 : }
209 : }
210 : }
211 : }
212 24 : for r in &routes {
213 24 : assert_orthogonal(r);
214 24 : assert_clear(r, &nodes);
215 24 : }
216 1 : }
217 :
218 : /// A route's segments that may move: not those at its ports.
219 474 : fn inner_segments(r: &Route) -> Vec<(Point, Point)> {
220 474 : let n = r.points.len();
221 474 : (1..n.saturating_sub(2))
222 474 : .map(|k| (r.points[k], r.points[k + 1]))
223 474 : .collect()
224 474 : }
225 :
226 : /// Whether two segments lie on one line and share a stretch of it.
227 153 : fn overlap(a: (Point, Point), b: (Point, Point)) -> bool {
228 918 : let horizontal = |s: (Point, Point)| s.0.y == s.1.y;
229 153 : if horizontal(a) != horizontal(b) {
230 0 : return false;
231 153 : }
232 : // Along the segments, and across.
233 612 : let uv = |p: Point| {
234 612 : if horizontal(a) {
235 0 : (p.x, p.y)
236 : } else {
237 612 : (p.y, p.x)
238 : }
239 612 : };
240 153 : let ((a0, va), (a1, _)) = (uv(a.0), uv(a.1));
241 153 : let ((b0, vb), (b1, _)) = (uv(b.0), uv(b.1));
242 153 : if (va - vb).abs() > 1e-3 {
243 153 : return false;
244 0 : }
245 0 : let lo = a0.min(a1).max(b0.min(b1));
246 0 : let hi = a0.max(a1).min(b0.max(b1));
247 0 : hi - lo > 1e-3
248 153 : }
249 :
250 : /// Six rows of five nodes, each node wired to one in the next column.
251 2 : fn rows_and_columns() -> (Vec<Rect>, Vec<Connector>) {
252 2 : let nodes: Vec<Rect> = (0..6)
253 60 : .flat_map(|r| (0..5).map(move |c| rect(c as f32 * 240.0, r as f32 * 130.0, 180.0, 70.0)))
254 2 : .collect();
255 2 : let wires: Vec<Connector> = (0..6)
256 12 : .flat_map(|r| {
257 48 : (0..4).map(move |c| {
258 48 : let y = r as f32 * 130.0;
259 48 : let to_row = (r + c) % 6;
260 48 : Connector::new(
261 48 : right(c as f32 * 240.0 + 180.0, y + 35.0),
262 48 : left((c + 1) as f32 * 240.0, to_row as f32 * 130.0 + 35.0),
263 : )
264 48 : })
265 12 : })
266 2 : .collect();
267 2 : (nodes, wires)
268 2 : }
269 :
270 : #[test]
271 1 : fn a_batch_routes_like_single_calls() {
272 1 : let nodes = [
273 1 : rect(0.0, 0.0, 100.0, 60.0),
274 1 : rect(0.0, 120.0, 100.0, 60.0),
275 1 : rect(300.0, 60.0, 100.0, 60.0),
276 1 : ];
277 1 : let wires = [
278 1 : Connector::new(right(100.0, 30.0), left(300.0, 80.0)),
279 1 : Connector::new(right(100.0, 150.0), left(300.0, 100.0)),
280 1 : ];
281 1 : let mut r = router(&nodes);
282 1 : let batch = r.route_all(&wires);
283 2 : for (w, b) in wires.iter().zip(&batch) {
284 2 : let one = r.route(w);
285 2 : assert!(one.routed && b.routed);
286 2 : assert_eq!(one.bends(), b.bends());
287 2 : assert_eq!(one.length(), b.length());
288 : }
289 1 : }
290 :
291 : #[test]
292 1 : fn the_fingerprint_follows_the_layout() {
293 1 : let nodes = [rect(0.0, 0.0, 100.0, 60.0)];
294 1 : let wires = [Connector::new(right(100.0, 30.0), left(300.0, 30.0))];
295 1 : let r = router(&nodes);
296 1 : let key = r.fingerprint(&wires);
297 1 : assert_eq!(key, router(&nodes).fingerprint(&wires));
298 1 : assert_ne!(
299 : key,
300 1 : router(&[rect(0.0, 0.0, 100.0, 61.0)]).fingerprint(&wires)
301 : );
302 1 : let moved = [Connector::new(right(100.0, 31.0), left(300.0, 30.0))];
303 1 : assert_ne!(key, r.fingerprint(&moved));
304 1 : let mut wider = router(&nodes);
305 1 : wider.set_options(Options {
306 1 : margin: 20.0,
307 1 : ..Options::default()
308 1 : });
309 1 : assert_ne!(key, wider.fingerprint(&wires));
310 1 : }
311 :
312 : #[test]
313 1 : fn invalid_obstacles_are_ignored() {
314 1 : let bad = Rect {
315 1 : min: Point::new(10.0, 10.0),
316 1 : max: Point::new(f32::INFINITY, 0.0),
317 1 : };
318 1 : let r = router(&[bad]);
319 1 : assert!(r.obstacles().is_empty());
320 1 : }
|
