Line data Source code
1 : //! Nudging: routes found one by one share the grid's lines, so wires
2 : //! through one channel are drawn on top of each other. Afterwards,
3 : //! segments of different routes that lie on one line and overlap are
4 : //! spread apart across it, `spacing` apart and centred on the line.
5 : //!
6 : //! A segment moves as a whole, across its own direction: its two
7 : //! neighbours are perpendicular to it, so they only grow or shrink and
8 : //! the route stays orthogonal. A route's first and last segments are
9 : //! left in place, since they hold its ports. The spread is at most the
10 : //! margin (half of it on each side of the line), so a nudged segment
11 : //! keeps at least half the margin away from the obstacles.
12 : //!
13 : //! Within a group, segments are ordered so the spreading adds as few
14 : //! crossings as it can. Take vertical segments, ordered left to right:
15 : //! each has a top end and a bottom end, where it turns left or right.
16 : //! A segment turning left at both ends goes left of one turning right
17 : //! at both; between two turning the same way at the top, the one whose
18 : //! top is lower goes on that side (so its turn does not cut the other
19 : //! one), and between two turning the same way at the bottom, the one
20 : //! whose bottom is higher goes on that side. Horizontal segments are
21 : //! ordered the same way with the axes swapped. Ties keep the
22 : //! connectors' order.
23 :
24 : use super::Route;
25 : use super::geom::{EPS, Point};
26 :
27 : /// A segment eligible for nudging.
28 : #[derive(Clone, Copy, Debug)]
29 : struct Seg {
30 : /// The route and the index of the segment's first point.
31 : route: usize,
32 : k: usize,
33 : horizontal: bool,
34 : /// Its line: `y` when horizontal, else `x`.
35 : at: f32,
36 : lo: f32,
37 : hi: f32,
38 : /// Its place across the line, smallest first.
39 : key: (f32, f32),
40 : }
41 :
42 : /// Spreads overlapping collinear segments of `routes` apart.
43 21 : pub(crate) fn nudge(routes: &mut [Route], spacing: f32, margin: f32) {
44 21 : if spacing <= 0.0 || !spacing.is_finite() {
45 0 : return;
46 21 : }
47 21 : let mut segs = segments(routes);
48 318 : segs.sort_by(|a, b| {
49 318 : a.horizontal
50 318 : .cmp(&b.horizontal)
51 318 : .then(a.at.total_cmp(&b.at))
52 318 : .then(a.lo.total_cmp(&b.lo))
53 318 : .then(a.route.cmp(&b.route))
54 318 : .then(a.k.cmp(&b.k))
55 318 : });
56 : // Shifts, decided on the routes as found, then applied.
57 21 : let mut shifts: Vec<(usize, usize, bool, f32)> = Vec::new();
58 21 : let mut start = 0;
59 57 : while start < segs.len() {
60 : // A group: one line, and each segment overlapping the span of
61 : // those before it.
62 36 : let first = segs[start];
63 36 : let mut end = start + 1;
64 36 : let mut hi = first.hi;
65 101 : while end < segs.len() {
66 85 : let s = segs[end];
67 85 : if s.horizontal != first.horizontal || (s.at - first.at).abs() > EPS || s.lo >= hi - EPS
68 : {
69 20 : break;
70 65 : }
71 65 : hi = hi.max(s.hi);
72 65 : end += 1;
73 : }
74 36 : let group = &mut segs[start..end];
75 36 : start = end;
76 36 : let routes_in = {
77 36 : let mut r: Vec<usize> = group.iter().map(|s| s.route).collect();
78 36 : r.dedup();
79 36 : r.len()
80 : };
81 36 : if group.len() < 2 || routes_in < 2 {
82 22 : continue;
83 14 : }
84 159 : group.sort_by(|a, b| {
85 159 : a.key
86 159 : .0
87 159 : .total_cmp(&b.key.0)
88 159 : .then(a.key.1.total_cmp(&b.key.1))
89 159 : .then(a.route.cmp(&b.route))
90 159 : });
91 14 : let n = group.len() as f32;
92 14 : let step = spacing.min(margin.max(0.0) / (n - 1.0));
93 79 : for (m, s) in group.iter().enumerate() {
94 79 : let off = (m as f32 - (n - 1.0) / 2.0) * step;
95 79 : if off != 0.0 {
96 78 : shifts.push((s.route, s.k, s.horizontal, off));
97 78 : }
98 : }
99 : }
100 78 : for (r, k, horizontal, off) in shifts {
101 78 : let points = &mut routes[r].points;
102 156 : for p in &mut points[k..k + 2] {
103 156 : if horizontal {
104 0 : p.y += off;
105 156 : } else {
106 156 : p.x += off;
107 156 : }
108 : }
109 : }
110 21 : }
111 :
112 : /// The routes' segments that may move: not a route's first or last,
113 : /// and only of routes found around the obstacles.
114 21 : fn segments(routes: &[Route]) -> Vec<Seg> {
115 21 : let mut out = Vec::new();
116 121 : for (r, route) in routes.iter().enumerate() {
117 121 : if !route.routed {
118 2 : continue;
119 119 : }
120 119 : let p = &route.points;
121 119 : for k in 1..p.len().saturating_sub(2) {
122 101 : let (a, b) = (p[k], p[k + 1]);
123 101 : let (before, after) = (p[k - 1], p[k + 2]);
124 101 : let horizontal = (a.y - b.y).abs() <= EPS;
125 : // Along the segment `u`, across it `v`.
126 606 : let uv = |p: Point| if horizontal { (p.x, p.y) } else { (p.y, p.x) };
127 101 : let ((ua, va), (ub, _)) = (uv(a), uv(b));
128 : // Which way it turns at an end: -1 toward smaller `v`.
129 202 : let turn = |end: Point, next: Point| (uv(next).1 - uv(end).1).signum();
130 101 : let (ta, tb) = (turn(a, before), turn(b, after));
131 : // The first end (smaller `u`) and the second.
132 101 : let ((u1, t1), (u2, t2)) = if ua <= ub {
133 69 : ((ua, ta), (ub, tb))
134 : } else {
135 32 : ((ub, tb), (ua, ta))
136 : };
137 101 : out.push(Seg {
138 101 : route: r,
139 101 : k,
140 101 : horizontal,
141 101 : at: va,
142 101 : lo: u1,
143 101 : hi: u2,
144 101 : key: (t1 + t2, t1 * u1 - t2 * u2),
145 101 : });
146 : }
147 : }
148 21 : out
149 21 : }
150 :
151 : #[cfg(test)]
152 : mod tests {
153 : use super::*;
154 :
155 11 : fn route(points: &[[f32; 2]]) -> Route {
156 : Route {
157 40 : points: points.iter().map(|&p| Point::from(p)).collect(),
158 : routed: true,
159 : }
160 11 : }
161 :
162 : #[test]
163 1 : fn two_wires_down_one_channel_are_spread_apart() {
164 : // Both go down x = 50 between y = 0 and y = 100.
165 1 : let mut routes = vec![
166 1 : route(&[[0.0, 0.0], [50.0, 0.0], [50.0, 100.0], [100.0, 100.0]]),
167 1 : route(&[[0.0, 20.0], [50.0, 20.0], [50.0, 120.0], [100.0, 120.0]]),
168 : ];
169 1 : nudge(&mut routes, 6.0, 12.0);
170 1 : let x0 = routes[0].points[1].x;
171 1 : let x1 = routes[1].points[1].x;
172 : // The second turns in lower at the top and out lower at the
173 : // bottom: on the left, it crosses neither turn of the first.
174 1 : assert_eq!(x0 - x1, 6.0);
175 1 : assert_eq!(x0 + x1, 100.0, "centred on the line");
176 2 : for r in &routes {
177 2 : assert_eq!(r.points[1].x, r.points[2].x, "still vertical");
178 2 : assert_eq!(r.points[0], Point::new(0.0, r.points[0].y));
179 : }
180 1 : }
181 :
182 : #[test]
183 1 : fn the_spread_is_at_most_the_margin() {
184 1 : let mut routes: Vec<Route> = (0..5)
185 5 : .map(|i| {
186 5 : let y = i as f32 * 10.0;
187 5 : route(&[[0.0, y], [50.0, y], [50.0, y + 100.0], [100.0, y + 100.0]])
188 5 : })
189 1 : .collect();
190 1 : nudge(&mut routes, 6.0, 8.0);
191 5 : let xs: Vec<f32> = routes.iter().map(|r| r.points[1].x).collect();
192 1 : let (lo, hi) = xs
193 1 : .iter()
194 5 : .fold((f32::MAX, f32::MIN), |(l, h), &x| (l.min(x), h.max(x)));
195 1 : assert!(hi - lo <= 8.0 + 1e-4, "{xs:?}");
196 1 : }
197 :
198 : #[test]
199 1 : fn segments_that_do_not_overlap_stay() {
200 1 : let mut routes = vec![
201 1 : route(&[[0.0, 0.0], [50.0, 0.0], [50.0, 40.0], [100.0, 40.0]]),
202 1 : route(&[[0.0, 60.0], [50.0, 60.0], [50.0, 100.0], [100.0, 100.0]]),
203 : ];
204 1 : let before = routes.clone();
205 1 : nudge(&mut routes, 6.0, 12.0);
206 1 : assert_eq!(routes, before);
207 1 : }
208 :
209 : #[test]
210 1 : fn ports_never_move() {
211 1 : let mut routes = vec![
212 1 : route(&[[0.0, 0.0], [100.0, 0.0]]),
213 1 : route(&[[0.0, 0.0], [100.0, 0.0]]),
214 : ];
215 1 : let before = routes.clone();
216 1 : nudge(&mut routes, 6.0, 12.0);
217 1 : assert_eq!(routes, before);
218 1 : }
219 : }
|
