biji_ui/utils/polygon/
mod.rs

1use std::cmp::Ordering;
2
3use leptos::prelude::*;
4
5pub fn make_hull(points: &[(f64, f64)]) -> Vec<(f64, f64)> {
6    let mut points = points.to_vec();
7    points.sort_by(|a, b| point_comparator(a, b));
8    make_hull_presorted(&points)
9}
10
11pub fn point_comparator(a: &(f64, f64), b: &(f64, f64)) -> Ordering {
12    if a.0 < b.0 {
13        Ordering::Less
14    } else if a.0 > b.0 {
15        Ordering::Greater
16    } else if a.1 < b.1 {
17        Ordering::Less
18    } else if a.1 > b.1 {
19        Ordering::Greater
20    } else {
21        Ordering::Equal
22    }
23}
24
25pub type ElPoints = (Signal<f64>, Signal<f64>, Signal<f64>, Signal<f64>);
26
27pub fn get_points_from_el((top, right, bottom, left): &ElPoints) -> Vec<(f64, f64)> {
28    vec![
29        (left.get(), top.get()),
30        (right.get(), top.get()),
31        (right.get(), bottom.get()),
32        (left.get(), bottom.get()),
33    ]
34}
35
36pub fn make_hull_from_elements(els: &[ElPoints]) -> Vec<(f64, f64)> {
37    let points = els
38        .iter()
39        .flat_map(|el| get_points_from_el(el))
40        .collect::<Vec<(f64, f64)>>();
41    make_hull(&points)
42}
43
44/// Returns the convex hull, assuming that each points[i] <= points[i + 1]. Runs in O(n) time.
45pub fn make_hull_presorted(points: &[(f64, f64)]) -> Vec<(f64, f64)> {
46    let mut lower: Vec<(f64, f64)> = Vec::new();
47    for p in points {
48        while lower.len() >= 2 {
49            let last = lower.len() - 1;
50            let second_last = lower.len() - 2;
51            let v1 = (
52                lower[last].0 - lower[second_last].0,
53                lower[last].1 - lower[second_last].1,
54            );
55            let v2 = (p.0 - lower[last].0, p.1 - lower[last].1);
56            if v1.0 * v2.1 - v1.1 * v2.0 < 0.0 {
57                lower.pop();
58            } else {
59                break;
60            }
61        }
62        lower.push(*p);
63    }
64    let mut upper: Vec<(f64, f64)> = Vec::new();
65    for p in points.iter().rev() {
66        while upper.len() >= 2 {
67            let last = upper.len() - 1;
68            let second_last = upper.len() - 2;
69            let v1 = (
70                upper[last].0 - upper[second_last].0,
71                upper[last].1 - upper[second_last].1,
72            );
73            let v2 = (p.0 - upper[last].0, p.1 - upper[last].1);
74            if v1.0 * v2.1 - v1.1 * v2.0 < 0.0 {
75                upper.pop();
76            } else {
77                break;
78            }
79        }
80        upper.push(*p);
81    }
82    lower.pop();
83    upper.pop();
84    lower.extend(upper);
85    lower
86}
87
88pub fn point_in_polygon(point: (f64, f64), polygon: &[(f64, f64)]) -> bool {
89    let mut result = false;
90    for i in 0..polygon.len() {
91        let j = (i + 1) % polygon.len();
92        let xi = polygon[i].0;
93        let yi = polygon[i].1;
94        let xj = polygon[j].0;
95        let yj = polygon[j].1;
96
97        if (yi > point.1) != (yj > point.1) && point.0 < (xj - xi) * (point.1 - yi) / (yj - yi) + xi
98        {
99            result = !result;
100        }
101    }
102    result
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108
109    #[test]
110    fn test_make_hull() {
111        let points = vec![
112            (0.0, 0.0),
113            (0.0, 4.0),
114            (-4.0, 0.0),
115            (5.0, 0.0),
116            (0.0, -6.0),
117            (1.0, 0.0),
118        ];
119        let hull = make_hull(&points);
120        assert_eq!(hull, vec![(-4.0, 0.0), (0.0, -6.0), (5.0, 0.0), (0.0, 4.0)]);
121    }
122
123    #[test]
124    fn test_point_in_polygon() {
125        let polygon = vec![(0.0, 0.0), (0.0, 4.0), (4.0, 4.0), (4.0, 0.0)];
126        assert_eq!(point_in_polygon((2.0, 2.0), &polygon), true);
127        assert_eq!(point_in_polygon((0.0, 0.0), &polygon), true);
128        assert_eq!(point_in_polygon((1.0, 1.0), &polygon), true);
129        assert_eq!(point_in_polygon((1.1, 3.9), &polygon), true);
130        assert_eq!(point_in_polygon((3.9, 1.1), &polygon), true);
131        assert_eq!(point_in_polygon((-0.1, 0.0), &polygon), false);
132        assert_eq!(point_in_polygon((0.0, 4.0), &polygon), false);
133        assert_eq!(point_in_polygon((4.0, 2.0), &polygon), false);
134        assert_eq!(point_in_polygon((2.0, 4.0), &polygon), false);
135        assert_eq!(point_in_polygon((2.0, 2.0), &vec![]), false);
136    }
137}
biji_ui/utils/polygon/mod.rs

biji_ui/utils/polygon/
mod.rs
