Line data Source code
1 : //! Orthogonal connector routing around rectangular obstacles: right-angled routes between ports on the sides of
2 : //! boxes, with few bends, and routes that share a channel spread apart.
3 : //!
4 : //! Vendored from ortho-router 0.1.0 (https://crates.io/crates/ortho-router, part of
5 : //! https://github.com/quazardous/egui-pop), MIT license (`LICENSE-MIT`, NOTICE). Changed: the crate root is this
6 : //! module, its tests are `tests.rs`.
7 : #![forbid(unsafe_code)]
8 : #![warn(missing_docs)]
9 :
10 : mod geom;
11 : mod grid;
12 : mod nudge;
13 :
14 : pub use geom::{Point, Rect, Side};
15 :
16 : use geom::EPS;
17 : use grid::{Grid, Search};
18 :
19 : /// A connector's end: a point on a node's edge and the side it leaves
20 : /// from.
21 : #[derive(Clone, Copy, Debug, PartialEq)]
22 : pub struct Port {
23 : /// Where the connector starts or ends, normally on its node's edge.
24 : pub at: Point,
25 : /// The side of the node the port is on: the connector leaves (or
26 : /// comes in) at a right angle to it.
27 : pub side: Side,
28 : }
29 :
30 : impl Port {
31 : /// A port at `at` on the `side` of its node.
32 124 : pub fn new(at: impl Into<Point>, side: Side) -> Port {
33 124 : Port {
34 124 : at: at.into(),
35 124 : side,
36 124 : }
37 124 : }
38 : }
39 :
40 : /// A connector to route, from one port to another.
41 : #[derive(Clone, Copy, Debug, PartialEq)]
42 : pub struct Connector {
43 : /// Where it starts.
44 : pub from: Port,
45 : /// Where it ends.
46 : pub to: Port,
47 : }
48 :
49 : impl Connector {
50 : /// A connector from `from` to `to`.
51 62 : pub fn new(from: Port, to: Port) -> Connector {
52 62 : Connector { from, to }
53 62 : }
54 : }
55 :
56 : /// How routes are drawn. The distances are in the caller's units.
57 : #[derive(Clone, Copy, Debug, PartialEq)]
58 : pub struct Options {
59 : /// How far routes keep from obstacles (default 12). It is also the
60 : /// length of the straight stub a route leaves a port with.
61 : pub margin: f32,
62 : /// What a bend costs, as a length (default 40): the higher, the
63 : /// fewer bends at the price of longer routes.
64 : pub bend_penalty: f32,
65 : /// How far apart [`Router::route_all`] spreads wires that share a
66 : /// channel (default 6; 0 leaves them on top of each other). A group
67 : /// spreads over the margin at most, so with many wires in one
68 : /// channel they come closer than this.
69 : pub spacing: f32,
70 : }
71 :
72 : impl Default for Options {
73 38 : fn default() -> Options {
74 38 : Options {
75 38 : margin: 12.0,
76 38 : bend_penalty: 40.0,
77 38 : spacing: 6.0,
78 38 : }
79 38 : }
80 : }
81 :
82 : /// A routed connector: a polyline of horizontal and vertical segments.
83 : #[derive(Clone, Debug, Default, PartialEq)]
84 : pub struct Route {
85 : /// Its vertices, from the first port to the second, without
86 : /// repeated or collinear points.
87 : pub points: Vec<Point>,
88 : /// `false` when no way around the obstacles was found: `points` is
89 : /// then the fallback, a stub out of each port joined by a single
90 : /// elbow (orthogonal, but it may cross obstacles). A connector with
91 : /// a coordinate that is not finite falls back to the straight
92 : /// segment between its ports.
93 : pub routed: bool,
94 : }
95 :
96 : impl Route {
97 : /// How many times it turns.
98 8 : pub fn bends(&self) -> usize {
99 8 : self.points.len().saturating_sub(2)
100 8 : }
101 :
102 : /// Its length.
103 6 : pub fn length(&self) -> f32 {
104 6 : self.points
105 6 : .windows(2)
106 18 : .map(|w| (w[1].x - w[0].x).abs() + (w[1].y - w[0].y).abs())
107 6 : .sum()
108 6 : }
109 : }
110 :
111 : /// Routes connectors around obstacles.
112 : ///
113 : /// Keep one between frames: it keeps the obstacles and the search's
114 : /// buffers. Its output depends only on its obstacles, its options and
115 : /// the connectors, so a caller can cache routes under
116 : /// [`fingerprint`](Router::fingerprint).
117 : #[derive(Clone, Debug, Default)]
118 : pub struct Router {
119 : obstacles: Vec<Rect>,
120 : options: Options,
121 : search: Search,
122 : }
123 :
124 : impl Router {
125 : /// A router with these options and no obstacles.
126 19 : pub fn new(options: Options) -> Router {
127 19 : Router {
128 19 : options,
129 19 : ..Router::default()
130 19 : }
131 19 : }
132 :
133 : /// The router with these obstacles.
134 19 : pub fn with_obstacles(mut self, obstacles: impl IntoIterator<Item = Rect>) -> Router {
135 19 : self.set_obstacles(obstacles);
136 19 : self
137 19 : }
138 :
139 : /// Replaces the obstacles, typically the nodes' rectangles. A
140 : /// rectangle that is not [valid](Rect::is_valid) is ignored.
141 19 : pub fn set_obstacles(&mut self, obstacles: impl IntoIterator<Item = Rect>) {
142 19 : self.obstacles.clear();
143 19 : self.obstacles
144 19 : .extend(obstacles.into_iter().filter(Rect::is_valid));
145 19 : }
146 :
147 : /// The obstacles.
148 1 : pub fn obstacles(&self) -> &[Rect] {
149 1 : &self.obstacles
150 1 : }
151 :
152 : /// The options.
153 0 : pub fn options(&self) -> &Options {
154 0 : &self.options
155 0 : }
156 :
157 : /// Replaces the options.
158 1 : pub fn set_options(&mut self, options: Options) {
159 1 : self.options = options;
160 1 : }
161 :
162 : /// Routes one connector.
163 10 : pub fn route(&mut self, connector: &Connector) -> Route {
164 10 : self.route_all(std::slice::from_ref(connector))
165 10 : .pop()
166 10 : .unwrap_or_default()
167 10 : }
168 :
169 : /// Routes connectors, in order: the routes match `connectors`.
170 : ///
171 : /// The connectors share one grid, built from the obstacles and every
172 : /// connector's ports, so routing many at once costs little more than
173 : /// routing one. Then wires sharing a channel are spread
174 : /// [`spacing`](Options::spacing) apart: their segments on one line
175 : /// move across it, the segments at the ports excepted.
176 17 : pub fn route_all(&mut self, connectors: &[Connector]) -> Vec<Route> {
177 17 : let margin = self.options.margin.max(0.0);
178 17 : let bend = self.options.bend_penalty.max(0.0);
179 155 : let grown: Vec<Rect> = self.obstacles.iter().map(|o| o.expand(margin)).collect();
180 17 : let stubs: Vec<Point> = connectors
181 17 : .iter()
182 110 : .flat_map(|c| [stub(&c.from, margin), stub(&c.to, margin)])
183 220 : .filter(|p| p.is_finite())
184 17 : .collect();
185 17 : let grid = Grid::build(&grown, &stubs);
186 17 : let mut routes: Vec<Route> = connectors
187 17 : .iter()
188 110 : .map(|c| route_in(&grid, &mut self.search, c, margin, bend))
189 17 : .collect();
190 17 : nudge::nudge(&mut routes, self.options.spacing, margin);
191 17 : routes
192 17 : }
193 :
194 : /// A hash of the obstacles, the options and `connectors`: the same
195 : /// value, the same routes. Stable across runs and platforms (FNV-1a
196 : /// over the coordinates' bits), so it can key a cache.
197 5 : pub fn fingerprint(&self, connectors: &[Connector]) -> u64 {
198 5 : let mut h = Fnv::default();
199 5 : h.f32(self.options.margin);
200 5 : h.f32(self.options.bend_penalty);
201 5 : h.f32(self.options.spacing);
202 5 : h.u64(self.obstacles.len() as u64);
203 5 : for o in &self.obstacles {
204 20 : for v in [o.min.x, o.min.y, o.max.x, o.max.y] {
205 20 : h.f32(v);
206 20 : }
207 : }
208 5 : h.u64(connectors.len() as u64);
209 5 : for c in connectors {
210 10 : for p in [c.from, c.to] {
211 10 : h.f32(p.at.x);
212 10 : h.f32(p.at.y);
213 10 : h.u64(p.side as u64);
214 10 : }
215 : }
216 5 : h.0
217 5 : }
218 : }
219 :
220 : /// Where a route leaving `port` turns for the first time at the
221 : /// earliest: `margin` out of the port.
222 438 : fn stub(port: &Port, margin: f32) -> Point {
223 438 : port.at.toward(port.side, margin)
224 438 : }
225 :
226 : /// One connector over the grid, or its fallback.
227 110 : fn route_in(grid: &Grid, search: &mut Search, c: &Connector, margin: f32, bend: f32) -> Route {
228 110 : let (a, b) = (c.from.at, c.to.at);
229 110 : if !a.is_finite() || !b.is_finite() {
230 1 : return Route {
231 1 : points: vec![a, b],
232 1 : routed: false,
233 1 : };
234 109 : }
235 109 : let (sa, sb) = (stub(&c.from, margin), stub(&c.to, margin));
236 109 : let path = grid.vertex(sa).zip(grid.vertex(sb)).and_then(|(va, vb)| {
237 : // The route arrives going into the second port's node.
238 108 : search.find(grid, va, c.from.side, vb, c.to.side.opposite(), bend)
239 108 : });
240 109 : match path {
241 108 : Some(path) => Route {
242 108 : points: simplify(
243 108 : std::iter::once(a)
244 784 : .chain(path.into_iter().map(|v| grid.point(v)))
245 108 : .chain(std::iter::once(b)),
246 : ),
247 : routed: true,
248 : },
249 1 : None => Route {
250 1 : points: simplify(fallback(a, sa, c.from.side, sb, b)),
251 1 : routed: false,
252 1 : },
253 : }
254 110 : }
255 :
256 : /// A stub out of each port joined by one elbow, halfway across.
257 1 : fn fallback(a: Point, sa: Point, side: Side, sb: Point, b: Point) -> [Point; 6] {
258 1 : let (p, q) = if side.is_horizontal() {
259 1 : let x = (sa.x + sb.x) / 2.0;
260 1 : (Point::new(x, sa.y), Point::new(x, sb.y))
261 : } else {
262 0 : let y = (sa.y + sb.y) / 2.0;
263 0 : (Point::new(sa.x, y), Point::new(sb.x, y))
264 : };
265 1 : [a, sa, p, q, sb, b]
266 1 : }
267 :
268 : /// FNV-1a, 64 bits.
269 : struct Fnv(u64);
270 :
271 : impl Default for Fnv {
272 5 : fn default() -> Fnv {
273 5 : Fnv(0xcbf2_9ce4_8422_2325)
274 5 : }
275 : }
276 :
277 : impl Fnv {
278 75 : fn u64(&mut self, v: u64) {
279 600 : for b in v.to_le_bytes() {
280 600 : self.0 ^= u64::from(b);
281 600 : self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
282 600 : }
283 75 : }
284 :
285 55 : fn f32(&mut self, v: f32) {
286 : // -0.0 and 0.0 route the same.
287 55 : self.u64(u64::from((v + 0.0).to_bits()));
288 55 : }
289 : }
290 :
291 : /// The points without repeats and without the middle of three on one
292 : /// line.
293 109 : fn simplify(points: impl IntoIterator<Item = Point>) -> Vec<Point> {
294 109 : let mut out: Vec<Point> = Vec::new();
295 1006 : for p in points {
296 1006 : if out.last().is_some_and(|l| l.near(p)) {
297 0 : continue;
298 1006 : }
299 1006 : if let [.., u, v] = out[..] {
300 788 : let vertical = (u.x - v.x).abs() <= EPS && (v.x - p.x).abs() <= EPS;
301 788 : let horizontal = (u.y - v.y).abs() <= EPS && (v.y - p.y).abs() <= EPS;
302 788 : if vertical || horizontal {
303 612 : out.pop();
304 612 : }
305 218 : }
306 1006 : out.push(p);
307 : }
308 109 : out
309 109 : }
310 :
311 : #[cfg(test)]
312 : mod tests;
|
