1use std::collections::BTreeMap;
2use std::f32::consts::{FRAC_PI_4, PI, TAU};
3
4#[derive(Clone, Copy, Debug, PartialEq)]
5pub struct Point {
6 pub x: f32,
7 pub y: f32,
8 pub on: bool,
9}
10
11pub type Contour = Vec<Point>;
12
13#[derive(Clone, Debug, Default, PartialEq)]
14pub struct Shape {
15 pub width: f32,
16 pub height: f32,
17 pub contours: Vec<Contour>,
18}
19
20impl Shape {
21 pub fn new(width: f32, height: f32) -> Self {
22 Self {
23 width,
24 height,
25 contours: Vec::new(),
26 }
27 }
28
29 pub fn add(&mut self, contour: Contour) -> &mut Self {
30 self.contours.push(contour);
31 self
32 }
33
34 pub fn extend(&mut self, contours: Vec<Contour>) -> &mut Self {
35 self.contours.extend(contours);
36 self
37 }
38
39 pub fn polylines(&self) -> Vec<Vec<[f32; 2]>> {
40 self.contours.iter().map(flatten).collect()
41 }
42
43 pub fn parents(&self) -> Vec<Option<usize>> {
44 let lines = self.polylines();
45 let areas: Vec<f32> = lines.iter().map(|line| signed_area(line).abs()).collect();
46 lines
47 .iter()
48 .enumerate()
49 .map(|(index, line)| {
50 let probe = line[0];
51 (0..lines.len())
52 .filter(|other| *other != index && areas[*other] > areas[index])
53 .filter(|other| contains(&lines[*other], probe))
54 .min_by(|a, b| areas[*a].total_cmp(&areas[*b]))
55 })
56 .collect()
57 }
58
59 pub fn depths(&self) -> Vec<usize> {
60 let parents = self.parents();
61 (0..parents.len())
62 .map(|index| {
63 let mut depth = 0;
64 let mut at = parents[index];
65 while let Some(parent) = at {
66 depth += 1;
67 at = parents[parent];
68 }
69 depth
70 })
71 .collect()
72 }
73
74 pub fn oriented(mut self) -> Self {
75 let depths = self.depths();
76 for (contour, depth) in self.contours.iter_mut().zip(depths) {
77 let area = signed_area(&flatten(contour));
78 if (depth % 2 == 0) != (area > 0.0) {
79 reverse(contour);
80 }
81 }
82 self
83 }
84}
85
86fn reverse(contour: &mut Contour) {
87 contour.reverse();
88 if let Some(first) = contour.iter().position(|point| point.on) {
89 contour.rotate_left(first);
90 }
91}
92
93pub fn signed_area(line: &[[f32; 2]]) -> f32 {
94 let mut sum = 0.0;
95 for i in 0..line.len() {
96 let a = line[i];
97 let b = line[(i + 1) % line.len()];
98 sum += a[0] * b[1] - b[0] * a[1];
99 }
100 sum / 2.0
101}
102
103pub fn contains(line: &[[f32; 2]], p: [f32; 2]) -> bool {
104 let mut inside = false;
105 for i in 0..line.len() {
106 let a = line[i];
107 let b = line[(i + 1) % line.len()];
108 if (a[1] > p[1]) != (b[1] > p[1])
109 && p[0] < (b[0] - a[0]) * (p[1] - a[1]) / (b[1] - a[1]) + a[0]
110 {
111 inside = !inside;
112 }
113 }
114 inside
115}
116
117pub fn winding(lines: &[Vec<[f32; 2]>], p: [f32; 2]) -> i32 {
118 let mut total = 0;
119 for line in lines {
120 for i in 0..line.len() {
121 let a = line[i];
122 let b = line[(i + 1) % line.len()];
123 let side = (b[0] - a[0]) * (p[1] - a[1]) - (p[0] - a[0]) * (b[1] - a[1]);
124 if a[1] <= p[1] {
125 if b[1] > p[1] && side > 0.0 {
126 total += 1;
127 }
128 } else if b[1] <= p[1] && side < 0.0 {
129 total -= 1;
130 }
131 }
132 }
133 total
134}
135
136fn on(x: f32, y: f32) -> Point {
137 Point { x, y, on: true }
138}
139
140fn off(x: f32, y: f32) -> Point {
141 Point { x, y, on: false }
142}
143
144pub fn polygon(points: &[[f32; 2]]) -> Contour {
145 points.iter().map(|p| on(p[0], p[1])).collect()
146}
147
148fn arc(contour: &mut Contour, cx: f32, cy: f32, r: f32, from: f32, to: f32) {
149 let steps = (((to - from).abs() / FRAC_PI_4).ceil() as usize).max(1);
150 let step = (to - from) / steps as f32;
151 let reach = r / (step / 2.0).cos();
152 if contour.is_empty() {
153 contour.push(on(cx + r * from.cos(), cy + r * from.sin()));
154 }
155 for i in 0..steps {
156 let a = from + step * i as f32;
157 let mid = a + step / 2.0;
158 let b = a + step;
159 contour.push(off(cx + reach * mid.cos(), cy + reach * mid.sin()));
160 contour.push(on(cx + r * b.cos(), cy + r * b.sin()));
161 }
162}
163
164pub fn circle(cx: f32, cy: f32, r: f32) -> Contour {
165 let mut contour = Vec::new();
166 arc(&mut contour, cx, cy, r, 0.0, TAU);
167 contour.pop();
168 contour
169}
170
171pub fn rounded(x: f32, y: f32, w: f32, h: f32, radii: [f32; 4]) -> Contour {
172 let limit = (w.min(h) / 2.0).max(0.0);
173 let [tl, tr, br, bl] = radii.map(|r| r.clamp(0.0, limit));
174 let mut contour = Vec::new();
175 corner(&mut contour, x + tl, y + tl, tl, PI, 1.5 * PI, [x, y]);
176 corner(
177 &mut contour,
178 x + w - tr,
179 y + tr,
180 tr,
181 1.5 * PI,
182 TAU,
183 [x + w, y],
184 );
185 corner(
186 &mut contour,
187 x + w - br,
188 y + h - br,
189 br,
190 0.0,
191 0.5 * PI,
192 [x + w, y + h],
193 );
194 corner(
195 &mut contour,
196 x + bl,
197 y + h - bl,
198 bl,
199 0.5 * PI,
200 PI,
201 [x, y + h],
202 );
203 contour
204}
205
206fn corner(contour: &mut Contour, cx: f32, cy: f32, r: f32, from: f32, to: f32, sharp: [f32; 2]) {
207 if r <= 0.0 {
208 contour.push(on(sharp[0], sharp[1]));
209 return;
210 }
211 contour.push(on(cx + r * from.cos(), cy + r * from.sin()));
212 let mut tail = vec![on(cx + r * from.cos(), cy + r * from.sin())];
213 arc(&mut tail, cx, cy, r, from, to);
214 contour.extend(tail.into_iter().skip(1));
215}
216
217pub fn rect(x: f32, y: f32, w: f32, h: f32, r: f32) -> Contour {
218 rounded(x, y, w, h, [r; 4])
219}
220
221pub fn pill(cx: f32, cy: f32, w: f32, h: f32) -> Contour {
222 rect(cx - w / 2.0, cy - h / 2.0, w, h, h / 2.0)
223}
224
225pub fn regular(cx: f32, cy: f32, r: f32, sides: usize, turn: f32) -> Contour {
226 (0..sides)
227 .map(|i| {
228 let a = turn + TAU * i as f32 / sides as f32;
229 on(cx + r * a.cos(), cy + r * a.sin())
230 })
231 .collect()
232}
233
234pub fn triangle(cx: f32, cy: f32, r: f32, dir: Dir) -> Contour {
235 let turn = match dir {
236 Dir::Right => 0.0,
237 Dir::Down => 0.5 * PI,
238 Dir::Left => PI,
239 Dir::Up => 1.5 * PI,
240 };
241 regular(cx, cy, r, 3, turn)
242}
243
244pub fn plus(cx: f32, cy: f32, arm: f32, half: f32) -> Contour {
245 polygon(&[
246 [cx - half, cy - arm],
247 [cx + half, cy - arm],
248 [cx + half, cy - half],
249 [cx + arm, cy - half],
250 [cx + arm, cy + half],
251 [cx + half, cy + half],
252 [cx + half, cy + arm],
253 [cx - half, cy + arm],
254 [cx - half, cy + half],
255 [cx - arm, cy + half],
256 [cx - arm, cy - half],
257 [cx - half, cy - half],
258 ])
259}
260
261pub fn cross(cx: f32, cy: f32, arm: f32, half: f32) -> Contour {
262 plus(0.0, 0.0, arm, half)
263 .into_iter()
264 .map(|p| {
265 let (s, c) = FRAC_PI_4.sin_cos();
266 on(cx + p.x * c - p.y * s, cy + p.x * s + p.y * c)
267 })
268 .collect()
269}
270
271#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
272pub enum Dir {
273 Up,
274 Down,
275 Left,
276 Right,
277}
278
279pub fn flatten(contour: &Contour) -> Vec<[f32; 2]> {
280 let mut points = Vec::new();
281 let n = contour.len();
282 let mut i = 0;
283 while i < n {
284 let p = contour[i];
285 if p.on {
286 points.push([p.x, p.y]);
287 i += 1;
288 continue;
289 }
290 let a = contour[(i + n - 1) % n];
291 let b = contour[(i + 1) % n];
292 for step in 1..16 {
293 let t = step as f32 / 16.0;
294 let u = 1.0 - t;
295 points.push([
296 u * u * a.x + 2.0 * u * t * p.x + t * t * b.x,
297 u * u * a.y + 2.0 * u * t * p.y + t * t * b.y,
298 ]);
299 }
300 i += 1;
301 }
302 points
303}
304
305const FONT: &[(char, [&str; 7])] = &[
306 (
307 'A',
308 [
309 ".###.", "#...#", "#...#", "#####", "#...#", "#...#", "#...#",
310 ],
311 ),
312 (
313 'B',
314 [
315 "####.", "#...#", "#...#", "####.", "#...#", "#...#", "####.",
316 ],
317 ),
318 (
319 'C',
320 [
321 ".###.", "#...#", "#....", "#....", "#....", "#...#", ".###.",
322 ],
323 ),
324 (
325 'D',
326 [
327 "####.", "#...#", "#...#", "#...#", "#...#", "#...#", "####.",
328 ],
329 ),
330 (
331 'E',
332 [
333 "#####", "#....", "#....", "####.", "#....", "#....", "#####",
334 ],
335 ),
336 (
337 'F',
338 [
339 "#####", "#....", "#....", "####.", "#....", "#....", "#....",
340 ],
341 ),
342 (
343 'G',
344 [
345 ".###.", "#...#", "#....", "#.###", "#...#", "#...#", ".###.",
346 ],
347 ),
348 (
349 'H',
350 [
351 "#...#", "#...#", "#...#", "#####", "#...#", "#...#", "#...#",
352 ],
353 ),
354 (
355 'I',
356 [
357 "#####", "..#..", "..#..", "..#..", "..#..", "..#..", "#####",
358 ],
359 ),
360 (
361 'J',
362 [
363 "..###", "...#.", "...#.", "...#.", "...#.", "#..#.", ".##..",
364 ],
365 ),
366 (
367 'K',
368 [
369 "#...#", "#..#.", "#.#..", "##...", "#.#..", "#..#.", "#...#",
370 ],
371 ),
372 (
373 'L',
374 [
375 "#....", "#....", "#....", "#....", "#....", "#....", "#####",
376 ],
377 ),
378 (
379 'M',
380 [
381 "#...#", "##.##", "#.#.#", "#.#.#", "#...#", "#...#", "#...#",
382 ],
383 ),
384 (
385 'N',
386 [
387 "#...#", "##..#", "#.#.#", "#..##", "#...#", "#...#", "#...#",
388 ],
389 ),
390 (
391 'O',
392 [
393 ".###.", "#...#", "#...#", "#...#", "#...#", "#...#", ".###.",
394 ],
395 ),
396 (
397 'P',
398 [
399 "####.", "#...#", "#...#", "####.", "#....", "#....", "#....",
400 ],
401 ),
402 (
403 'Q',
404 [
405 ".###.", "#...#", "#...#", "#...#", "#.#.#", "#..#.", ".##.#",
406 ],
407 ),
408 (
409 'R',
410 [
411 "####.", "#...#", "#...#", "####.", "#.#..", "#..#.", "#...#",
412 ],
413 ),
414 (
415 'S',
416 [
417 ".####", "#....", "#....", ".###.", "....#", "....#", "####.",
418 ],
419 ),
420 (
421 'T',
422 [
423 "#####", "..#..", "..#..", "..#..", "..#..", "..#..", "..#..",
424 ],
425 ),
426 (
427 'U',
428 [
429 "#...#", "#...#", "#...#", "#...#", "#...#", "#...#", ".###.",
430 ],
431 ),
432 (
433 'V',
434 [
435 "#...#", "#...#", "#...#", "#...#", "#...#", ".#.#.", "..#..",
436 ],
437 ),
438 (
439 'W',
440 [
441 "#...#", "#...#", "#...#", "#.#.#", "#.#.#", "##.##", "#...#",
442 ],
443 ),
444 (
445 'X',
446 [
447 "#...#", "#...#", ".#.#.", "..#..", ".#.#.", "#...#", "#...#",
448 ],
449 ),
450 (
451 'Y',
452 [
453 "#...#", "#...#", ".#.#.", "..#..", "..#..", "..#..", "..#..",
454 ],
455 ),
456 (
457 'Z',
458 [
459 "#####", "....#", "...#.", "..#..", ".#...", "#....", "#####",
460 ],
461 ),
462 (
463 '0',
464 [
465 ".###.", "#...#", "#..##", "#.#.#", "##..#", "#...#", ".###.",
466 ],
467 ),
468 (
469 '1',
470 [
471 "..#..", ".##..", "..#..", "..#..", "..#..", "..#..", ".###.",
472 ],
473 ),
474 (
475 '2',
476 [
477 ".###.", "#...#", "....#", "...#.", "..#..", ".#...", "#####",
478 ],
479 ),
480 (
481 '3',
482 [
483 "####.", "....#", "....#", ".###.", "....#", "....#", "####.",
484 ],
485 ),
486 (
487 '4',
488 [
489 "...#.", "..##.", ".#.#.", "#..#.", "#####", "...#.", "...#.",
490 ],
491 ),
492 (
493 '5',
494 [
495 "#####", "#....", "####.", "....#", "....#", "#...#", ".###.",
496 ],
497 ),
498 (
499 '6',
500 [
501 ".###.", "#....", "#....", "####.", "#...#", "#...#", ".###.",
502 ],
503 ),
504 (
505 '7',
506 [
507 "#####", "....#", "...#.", "..#..", ".#...", ".#...", ".#...",
508 ],
509 ),
510 (
511 '8',
512 [
513 ".###.", "#...#", "#...#", ".###.", "#...#", "#...#", ".###.",
514 ],
515 ),
516 (
517 '9',
518 [
519 ".###.", "#...#", "#...#", ".####", "....#", "....#", ".###.",
520 ],
521 ),
522 (
523 '+',
524 [
525 ".....", "..#..", "..#..", "#####", "..#..", "..#..", ".....",
526 ],
527 ),
528 (
529 '-',
530 [
531 ".....", ".....", ".....", "#####", ".....", ".....", ".....",
532 ],
533 ),
534 (
535 '*',
536 [
537 ".....", "#.#.#", ".###.", "#####", ".###.", "#.#.#", ".....",
538 ],
539 ),
540 (
541 '/',
542 [
543 "....#", "....#", "...#.", "..#..", ".#...", "#....", "#....",
544 ],
545 ),
546 (
547 '\\',
548 [
549 "#....", "#....", ".#...", "..#..", "...#.", "....#", "....#",
550 ],
551 ),
552 (
553 '.',
554 [
555 ".....", ".....", ".....", ".....", ".....", ".##..", ".##..",
556 ],
557 ),
558 (
559 ',',
560 [
561 ".....", ".....", ".....", ".....", ".##..", "..#..", ".#...",
562 ],
563 ),
564 (
565 ';',
566 [
567 ".....", ".##..", ".##..", ".....", ".##..", "..#..", ".#...",
568 ],
569 ),
570 (
571 '\'',
572 [
573 "..#..", "..#..", ".#...", ".....", ".....", ".....", ".....",
574 ],
575 ),
576 (
577 '`',
578 [
579 ".#...", "..#..", "...#.", ".....", ".....", ".....", ".....",
580 ],
581 ),
582 (
583 '=',
584 [
585 ".....", ".....", "#####", ".....", "#####", ".....", ".....",
586 ],
587 ),
588 (
589 '[',
590 [
591 ".###.", ".#...", ".#...", ".#...", ".#...", ".#...", ".###.",
592 ],
593 ),
594 (
595 ']',
596 [
597 ".###.", "...#.", "...#.", "...#.", "...#.", "...#.", ".###.",
598 ],
599 ),
600 (
601 '?',
602 [
603 ".###.", "#...#", "....#", "...#.", "..#..", ".....", "..#..",
604 ],
605 ),
606];
607
608pub const FONT_COLUMNS: usize = 5;
609pub const FONT_ROWS: usize = 7;
610
611pub fn has_char(c: char) -> bool {
612 FONT.iter().any(|(ch, _)| *ch == c)
613}
614
615fn rows(c: char) -> [&'static str; 7] {
616 FONT.iter()
617 .find(|(ch, _)| *ch == c)
618 .or_else(|| FONT.iter().find(|(ch, _)| *ch == '?'))
619 .map(|(_, rows)| *rows)
620 .unwrap_or(["....."; 7])
621}
622
623pub fn bitmap(text: &str) -> (usize, usize, Vec<bool>) {
624 let chars: Vec<char> = text.chars().collect();
625 let width = if chars.is_empty() {
626 0
627 } else {
628 chars.len() * (FONT_COLUMNS + 1) - 1
629 };
630 let mut cells = vec![false; width * FONT_ROWS];
631 for (index, c) in chars.iter().enumerate() {
632 let rows = rows(*c);
633 for (y, row) in rows.iter().enumerate() {
634 for (x, byte) in row.bytes().enumerate() {
635 if byte == b'#' {
636 cells[y * width + index * (FONT_COLUMNS + 1) + x] = true;
637 }
638 }
639 }
640 }
641 (width, FONT_ROWS, cells)
642}
643
644pub fn trace(width: usize, height: usize, cells: &[bool]) -> Vec<Vec<[i32; 2]>> {
645 let filled = |x: i32, y: i32| -> bool {
646 x >= 0
647 && y >= 0
648 && (x as usize) < width
649 && (y as usize) < height
650 && cells[y as usize * width + x as usize]
651 };
652 let mut segments: Vec<([i32; 2], [i32; 2])> = Vec::new();
653 for j in -1..height as i32 {
654 for i in -1..width as i32 {
655 let tl = filled(i, j);
656 let tr = filled(i + 1, j);
657 let br = filled(i + 1, j + 1);
658 let bl = filled(i, j + 1);
659 let top = [2 * i + 1, 2 * j];
660 let right = [2 * i + 2, 2 * j + 1];
661 let bottom = [2 * i + 1, 2 * j + 2];
662 let left = [2 * i, 2 * j + 1];
663 match (tl, tr, br, bl) {
664 (true, false, true, false) => {
665 segments.push((top, right));
666 segments.push((left, bottom));
667 }
668 (false, true, false, true) => {
669 segments.push((top, left));
670 segments.push((right, bottom));
671 }
672 _ => {
673 let mut ends = Vec::new();
674 if tl != tr {
675 ends.push(top);
676 }
677 if tr != br {
678 ends.push(right);
679 }
680 if br != bl {
681 ends.push(bottom);
682 }
683 if bl != tl {
684 ends.push(left);
685 }
686 if ends.len() == 2 {
687 segments.push((ends[0], ends[1]));
688 }
689 }
690 }
691 }
692 }
693 let mut at: BTreeMap<[i32; 2], Vec<usize>> = BTreeMap::new();
694 for (index, (a, b)) in segments.iter().enumerate() {
695 at.entry(*a).or_default().push(index);
696 at.entry(*b).or_default().push(index);
697 }
698 let mut used = vec![false; segments.len()];
699 let mut loops = Vec::new();
700 for start in 0..segments.len() {
701 if used[start] {
702 continue;
703 }
704 used[start] = true;
705 let (first, mut current) = segments[start];
706 let mut points = vec![first];
707 while current != first {
708 points.push(current);
709 let Some(next) = at[¤t].iter().copied().find(|index| !used[*index]) else {
710 break;
711 };
712 used[next] = true;
713 let (a, b) = segments[next];
714 current = if a == current { b } else { a };
715 }
716 loops.push(simplify(points));
717 }
718 loops
719}
720
721fn simplify(points: Vec<[i32; 2]>) -> Vec<[i32; 2]> {
722 let n = points.len();
723 let mut kept = Vec::new();
724 for i in 0..n {
725 let a = points[(i + n - 1) % n];
726 let b = points[i];
727 let c = points[(i + 1) % n];
728 let cross = (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);
729 if cross != 0 {
730 kept.push(b);
731 }
732 }
733 kept
734}
735
736pub fn label(text: &str, cx: f32, cy: f32, max_w: f32, max_h: f32, max_cell: f32) -> Vec<Contour> {
737 let (width, height, cells) = bitmap(text);
738 if width == 0 {
739 return Vec::new();
740 }
741 let cell = (max_w / width as f32)
742 .min(max_h / height as f32)
743 .min(max_cell);
744 let x0 = cx - width as f32 * cell / 2.0;
745 let y0 = cy - height as f32 * cell / 2.0;
746 trace(width, height, &cells)
747 .into_iter()
748 .map(|points| {
749 points
750 .into_iter()
751 .map(|p| {
752 on(
753 x0 + (p[0] as f32 / 2.0 + 0.5) * cell,
754 y0 + (p[1] as f32 / 2.0 + 0.5) * cell,
755 )
756 })
757 .collect()
758 })
759 .collect()
760}
761
762pub fn label_width(text: &str, cell: f32) -> f32 {
763 let count = text.chars().count();
764 if count == 0 {
765 0.0
766 } else {
767 (count * (FONT_COLUMNS + 1) - 1) as f32 * cell
768 }
769}
770
771pub fn crossings(shape: &Shape) -> usize {
772 let lines = shape.polylines();
773 let mut found = 0;
774 for (ci, a) in lines.iter().enumerate() {
775 for b in lines.iter().skip(ci + 1) {
776 for i in 0..a.len() {
777 let p1 = a[i];
778 let p2 = a[(i + 1) % a.len()];
779 for j in 0..b.len() {
780 let q1 = b[j];
781 let q2 = b[(j + 1) % b.len()];
782 if segments_touch(p1, p2, q1, q2) {
783 found += 1;
784 }
785 }
786 }
787 }
788 }
789 found
790}
791
792fn segments_touch(p1: [f32; 2], p2: [f32; 2], q1: [f32; 2], q2: [f32; 2]) -> bool {
793 let orient = |a: [f32; 2], b: [f32; 2], c: [f32; 2]| {
794 (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
795 };
796 let d1 = orient(q1, q2, p1);
797 let d2 = orient(q1, q2, p2);
798 let d3 = orient(p1, p2, q1);
799 let d4 = orient(p1, p2, q2);
800 ((d1 > 0.0) != (d2 > 0.0) || d1 == 0.0 || d2 == 0.0)
801 && ((d3 > 0.0) != (d4 > 0.0) || d3 == 0.0 || d4 == 0.0)
802 && bounds_overlap(p1, p2, q1, q2)
803}
804
805fn bounds_overlap(p1: [f32; 2], p2: [f32; 2], q1: [f32; 2], q2: [f32; 2]) -> bool {
806 p1[0].min(p2[0]) <= q1[0].max(q2[0])
807 && q1[0].min(q2[0]) <= p1[0].max(p2[0])
808 && p1[1].min(p2[1]) <= q1[1].max(q2[1])
809 && q1[1].min(q2[1]) <= p1[1].max(p2[1])
810}
811
812pub fn min_gap(shape: &Shape) -> f32 {
813 let lines = shape.polylines();
814 let mut gap = f32::INFINITY;
815 for (ci, a) in lines.iter().enumerate() {
816 for b in lines.iter().skip(ci + 1) {
817 for p in a {
818 for j in 0..b.len() {
819 gap = gap.min(point_segment(*p, b[j], b[(j + 1) % b.len()]));
820 }
821 }
822 for p in b {
823 for i in 0..a.len() {
824 gap = gap.min(point_segment(*p, a[i], a[(i + 1) % a.len()]));
825 }
826 }
827 }
828 }
829 gap
830}
831
832fn point_segment(p: [f32; 2], a: [f32; 2], b: [f32; 2]) -> f32 {
833 let v = [b[0] - a[0], b[1] - a[1]];
834 let len2 = v[0] * v[0] + v[1] * v[1];
835 let t = if len2 > 0.0 {
836 (((p[0] - a[0]) * v[0] + (p[1] - a[1]) * v[1]) / len2).clamp(0.0, 1.0)
837 } else {
838 0.0
839 };
840 (p[0] - a[0] - t * v[0]).hypot(p[1] - a[1] - t * v[1])
841}