jagua_rs/geometry/
convex_hull.rs1use crate::geometry::primitives::Point;
2use crate::geometry::primitives::SPolygon;
3use ordered_float::OrderedFloat;
4
5use anyhow::{Result, bail};
6
7pub fn convex_hull_indices(shape: &SPolygon) -> Vec<usize> {
9 let c_hull = convex_hull_from_points(shape.vertices.clone());
10 let mut indices = vec![];
11 for p in c_hull.iter() {
12 indices.push(shape.vertices.iter().position(|x| x == p).unwrap());
13 }
14 indices
15}
16
17pub fn convex_hull_from_surrogate(s: &SPolygon) -> Result<Vec<Point>> {
19 if let Some(surr) = s.surrogate.as_ref() {
20 Ok(surr
21 .convex_hull_indices
22 .iter()
23 .map(|&i| s.vertices[i])
24 .collect())
25 } else {
26 bail!("no surrogate present")
27 }
28}
29
30pub fn convex_hull_from_points(mut points: Vec<Point>) -> Vec<Point> {
32 points.sort_by_key(|p| OrderedFloat(p.0));
36
37 let mut lower_hull = points
38 .iter()
39 .fold(vec![], |hull, p| grow_convex_hull(hull, *p));
40 let mut upper_hull = points
41 .iter()
42 .rev()
43 .fold(vec![], |hull, p| grow_convex_hull(hull, *p));
44
45 upper_hull.pop();
47 lower_hull.pop();
48
49 lower_hull.append(&mut upper_hull);
50 lower_hull
51}
52
53fn grow_convex_hull(mut h: Vec<Point>, next: Point) -> Vec<Point> {
54 while h.len() >= 2 && cross(h[h.len() - 2], h[h.len() - 1], next) <= 0.0 {
56 h.pop();
57 }
58 h.push(next);
59 h
60}
61
62fn cross(a: Point, b: Point, c: Point) -> f32 {
63 (b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0)
64}