rvimage_domain/
polygon.rs

1use crate::result::RvResult;
2use std::mem;
3
4use super::bb::BbF;
5use super::core::{dist_lineseg_point, max_squaredist, TPtF};
6use super::{OutOfBoundsMode, Point, PtF, ShapeF, ShapeI};
7use serde::{Deserialize, Serialize};
8
9fn lineseg_starting(idx: usize, vertices: &[PtF]) -> (PtF, PtF) {
10    if idx < vertices.len() - 1 {
11        (vertices[idx], vertices[idx + 1])
12    } else {
13        (vertices[idx], vertices[0])
14    }
15}
16
17fn intersect_y_axis_parallel(lineseg: &(PtF, PtF), x_value: TPtF) -> Option<PtF> {
18    let (p1, p2) = lineseg;
19    // Check if the line segment is parallel to the x-axis
20    if (p1.x - p2.x).abs() > 1e-8 && p1.x.min(p2.x) < x_value && p1.x.max(p2.x) > x_value {
21        let t = (x_value - p1.x) / (p2.x - p1.x);
22        let y = p1.y + t * (p2.y - p1.y);
23        Some(Point { x: x_value, y })
24    } else {
25        None
26    }
27}
28fn intersect_x_axis_parallel(lineseg: &(PtF, PtF), y_value: TPtF) -> Option<PtF> {
29    let (p1, p2) = lineseg;
30    // Check if the line segment is parallel to the y-axis and cuts y_value
31    if (p1.y - p2.y).abs() > 1e-8 && p1.y.min(p2.y) < y_value && p1.y.max(p2.y) > y_value {
32        let t = (y_value - p1.y) / (p2.y - p1.y);
33        let x = p1.x + t * (p2.x - p1.x);
34        Some(Point { x, y: y_value })
35    } else {
36        None
37    }
38}
39
40#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Default)]
41pub struct Polygon {
42    points: Vec<PtF>, // should NEVER be empty, hence private!
43    enclosing_bb: BbF,
44}
45impl Polygon {
46    #[must_use]
47    pub fn shape_check(self, orig_im_shape: ShapeI, mode: OutOfBoundsMode<TPtF>) -> Option<Self> {
48        let shape_bb = BbF::from_shape_int(orig_im_shape);
49        if shape_bb.contains_bb(self.enclosing_bb) {
50            Some(self)
51        } else {
52            match mode {
53                OutOfBoundsMode::Deny => {
54                    if self.points_iter().all(|p| shape_bb.contains(p)) {
55                        Some(self)
56                    } else {
57                        None
58                    }
59                }
60                OutOfBoundsMode::Resize(min_bb_shape) => {
61                    let shape = ShapeF {
62                        w: <u32 as Into<TPtF>>::into(orig_im_shape.w).max(min_bb_shape.w),
63                        h: <u32 as Into<TPtF>>::into(orig_im_shape.h).max(min_bb_shape.h),
64                    };
65                    let bb = BbF::from_shape(shape);
66                    self.intersect(bb).ok()
67                }
68            }
69        }
70    }
71    #[must_use]
72    pub fn min_enclosing_bb(&self) -> PtF {
73        self.enclosing_bb.min()
74    }
75    #[must_use]
76    pub fn translate(
77        mut self,
78        x: f64,
79        y: f64,
80        shape: ShapeI,
81        oob_mode: OutOfBoundsMode<TPtF>,
82    ) -> Option<Self> {
83        for p in &mut self.points {
84            p.x = (p.x + x).max(0.0);
85            p.y = (p.y + y).max(0.0);
86        }
87        self.shape_check(shape, oob_mode)
88    }
89    pub fn max_squaredist(&self, other: impl Iterator<Item = PtF> + Clone) -> (PtF, PtF, f64) {
90        max_squaredist(self.points_iter(), other)
91    }
92    #[allow(clippy::needless_lifetimes)]
93    pub fn points_iter<'a>(&'a self) -> impl Iterator<Item = PtF> + 'a + Clone {
94        self.points.iter().copied()
95    }
96    #[must_use]
97    pub fn has_overlap(&self, other: &BbF) -> bool {
98        self.enclosing_bb.has_overlap(other)
99            && (other.contains_bb(self.enclosing_bb)
100                || other.points_iter().any(|p| self.contains(p)))
101    }
102    #[must_use]
103    pub fn distance_to_boundary(&self, point: PtF) -> TPtF {
104        self.lineseg_iter()
105            .map(|ls| {
106                let (p1, p2) = ls;
107                dist_lineseg_point(&(p1, p2), point)
108            })
109            .min_by(|x, y| {
110                x.partial_cmp(y)
111                    .expect("this is a bug. NaNs should not appear")
112            })
113            .expect("this is a bug. polygons need multiple line segments")
114    }
115
116    /// Intersects the polygon with a bounding box for rendering and cut with the zoom box.
117    /// Sutherland-Hodgman algorithm where the clipping polygon is a box.
118    /// <https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm>
119    pub fn intersect(self, bb: BbF) -> RvResult<Self> {
120        let mut in_vertices = self.points;
121        let mut out_vertices = vec![];
122        let mut process_point = |select_coord: fn(&PtF) -> f64,
123                                 intersect: fn(&(PtF, PtF), f64) -> Option<PtF>,
124                                 corner,
125                                 cmp: fn(f64, f64) -> bool| {
126            for (idx, v) in in_vertices.iter().enumerate() {
127                if cmp(select_coord(v), select_coord(&corner)) {
128                    // add vertex if inside of box
129                    out_vertices.push(*v);
130                }
131
132                // add intersection
133                let ls = lineseg_starting(idx, &in_vertices);
134                let intersp = intersect(&ls, select_coord(&corner));
135                if let Some(intersp) = intersp {
136                    out_vertices.push(intersp);
137                }
138            }
139            in_vertices = mem::take(&mut out_vertices);
140        };
141        for (corner_idx, corner) in bb.points_iter().enumerate() {
142            if corner_idx == 0 {
143                // intersection with left line segment of bounding box
144                process_point(
145                    |p| p.x,
146                    intersect_y_axis_parallel,
147                    corner,
148                    |x, xleft| x >= xleft,
149                );
150            } else if corner_idx == 1 {
151                // intersection with left btm segment of bounding box
152                process_point(
153                    |p| p.y,
154                    intersect_x_axis_parallel,
155                    corner,
156                    |y, ybtm| y <= ybtm,
157                );
158            } else if corner_idx == 2 {
159                // intersection with left line segment of bounding box
160                process_point(
161                    |p| p.x,
162                    intersect_y_axis_parallel,
163                    corner,
164                    |x, xright| x <= xright,
165                );
166            } else if corner_idx == 3 {
167                // intersection with left btm segment of bounding box
168                process_point(
169                    |p| p.y,
170                    intersect_x_axis_parallel,
171                    corner,
172                    |y, ybtm| y >= ybtm,
173                );
174            }
175        }
176        Self::from_vec(in_vertices.into_iter().collect())
177    }
178    #[allow(clippy::needless_lifetimes)]
179    pub fn lineseg_iter<'a>(&'a self) -> impl Iterator<Item = (PtF, PtF)> + 'a {
180        self.points.iter().enumerate().map(|(i, p1)| {
181            let p2 = if i < self.points.len() - 1 {
182                self.points[i + 1]
183            } else {
184                self.points[0]
185            };
186            ((*p1), p2)
187        })
188    }
189    pub fn contains<P>(&self, point: P) -> bool
190    where
191        P: Into<PtF>,
192    {
193        // we will check the number of cuts from of rays from the point to the top
194        // parallel to the y-axis.
195        //   odd number => inside
196        //   even number => outside
197        let point = point.into();
198        let n_cuts = self
199            .lineseg_iter()
200            .filter(|(p1, p2)| {
201                let p1: PtF = *p1;
202                let p2: PtF = *p2;
203                if let Some(p) = intersect_y_axis_parallel(&(p1, p2), point.x) {
204                    p.y >= point.y
205                } else {
206                    false
207                }
208            })
209            .count();
210        n_cuts % 2 == 1
211    }
212    #[must_use]
213    pub fn is_contained_in_image(&self, shape: ShapeI) -> bool {
214        self.enclosing_bb.is_contained_in_image(shape)
215    }
216    #[must_use]
217    pub fn enclosing_bb(&self) -> BbF {
218        self.enclosing_bb
219    }
220    #[must_use]
221    pub fn points(&self) -> &Vec<PtF> {
222        &self.points
223    }
224    /// We will need this as soon as we support polygons
225    pub fn from_vec(points: Vec<PtF>) -> RvResult<Self> {
226        let enclosing_bb = BbF::from_vec(&points)?;
227        Ok(Self {
228            points,
229            enclosing_bb,
230        })
231    }
232    #[must_use]
233    pub fn rot90_with_image_ntimes(self, shape: ShapeI, n: u8) -> Self {
234        if n == 0 {
235            self
236        } else {
237            Self::from_vec(
238                self.points
239                    .into_iter()
240                    .map(|p| p.rot90_with_image_ntimes(shape, n))
241                    .collect::<Vec<_>>(),
242            )
243            .expect("somehow an empty polgon has been created")
244        }
245    }
246}
247impl From<BbF> for Polygon {
248    fn from(bb: BbF) -> Self {
249        Polygon {
250            points: bb.points_iter().collect(),
251            enclosing_bb: bb,
252        }
253    }
254}
255
256#[test]
257fn test_intersect() {
258    let ls = ((15.0, 15.0).into(), (5.0, 15.0).into());
259    let intersp = intersect_x_axis_parallel(&ls, 8.0);
260    assert!(intersp.is_none());
261    let ls = ((5.0, 15.0).into(), (5.0, 5.0).into());
262    let intersp = intersect_x_axis_parallel(&ls, 8.0);
263    if let Some(ip) = intersp {
264        assert!((ip.x - 5.0).abs() < 1e-8);
265        assert!((ip.y - 8.0).abs() < 1e-8);
266    } else {
267        assert!(false);
268    }
269}
270
271#[test]
272fn test_poly() {
273    let poly = Polygon::from(BbF::from_arr(&[5.0, 5.0, 10.0, 10.0]));
274    assert!(!poly.contains(PtF::from((17.0, 7.0))));
275    assert!(poly.contains(PtF::from((7.0, 7.0))));
276    let bb = BbF::from_arr(&[2.0, 2.0, 33.0, 30.0]);
277    assert!(poly.has_overlap(&bb));
278    let bb = BbF::from_arr(&[6.0, 6.0, 7.0, 7.0]);
279    assert!(poly.has_overlap(&bb));
280    let bb = BbF::from_arr(&[6.0, 6.0, 15.0, 15.0]);
281    assert!(poly.has_overlap(&bb));
282}
283#[test]
284fn test_poly_triangle() {
285    let poly = Polygon::from_vec(vec![(5, 5).into(), (10, 10).into(), (5, 10).into()]).unwrap();
286    assert!(poly.contains(PtF::from((6.0, 9.0))));
287    assert!(!poly.contains(PtF::from((6.0, 5.99))));
288    assert!(poly.contains(PtF::from((6.0, 6.01))));
289}
290#[test]
291fn test_poly_intersect() {
292    let poly = Polygon::from_vec(vec![(5, 5).into(), (15, 15).into(), (5, 15).into()]).unwrap();
293    let bb = BbF::from(&[5.0, 7.0, 10.0, 2.0]);
294    let clipped_poly = poly.clone().intersect(bb).unwrap();
295    let encl_bb = BbF::from(&[5.0, 7.0, 4.0, 2.0]);
296    assert_eq!(clipped_poly.enclosing_bb(), encl_bb);
297    assert_eq!(
298        clipped_poly.points,
299        vec![(7, 7).into(), (9, 9).into(), (5, 9).into(), (5, 7).into()]
300    );
301
302    let bb = BbF::from(&[5.0, 7.0, 2.0, 2.0]);
303    let clipped_poly = poly.intersect(bb);
304    assert_eq!(clipped_poly.unwrap().enclosing_bb(), bb);
305
306    let poly = Polygon::from_vec(vec![(5, 5).into(), (10, 10).into(), (5, 10).into()]).unwrap();
307    let clipped_poly = poly.clone().intersect(BbF::from(&[2.0, 2.0, 20.0, 20.0]));
308    assert_eq!(clipped_poly, Ok(poly));
309}
310
311#[test]
312fn test_min_dist() {
313    let poly = Polygon::from_vec(vec![(5, 5).into(), (15, 15).into(), (5, 15).into()]).unwrap();
314    let p = (5, 5).into();
315    let d = poly.distance_to_boundary(p).abs();
316    assert!(d < 1e-8);
317    let p = (0, 5).into();
318    let d = poly.distance_to_boundary(p).abs();
319    assert!((5.0 - d).abs() < 1e-8);
320    let p = (10, 10).into();
321    let d = poly.distance_to_boundary(p).abs();
322    assert!(d.abs() < 1e-8);
323    let p = (10, 11).into();
324    let d = poly.distance_to_boundary(p).abs();
325    assert!((0.5f64.sqrt() - d).abs() < 1e-8);
326}
rvimage_domain/polygon.rs

rvimage_domain/
polygon.rs
