jagua_rs/geometry/
convex_hull.rs

1use crate::geometry::primitives::Point;
2use crate::geometry::primitives::SPolygon;
3use ordered_float::OrderedFloat;
4
5use anyhow::{Result, bail};
6
7/// Returns the indices of the points in the [`SPolygon`] that form the convex hull
8pub 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
17/// Reconstitutes the convex hull of a [`SPolygon`] using its surrogate
18pub 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
30/// Filters a set of points to only include those that are part of the convex hull
31pub fn convex_hull_from_points(mut points: Vec<Point>) -> Vec<Point> {
32    //https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
33
34    //sort the points by x coordinate
35    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    //First and last element of both hull parts are the same point
46    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    //pop all points from the hull which will be made irrelevant due to the new point
55    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}
jagua_rs/geometry/convex_hull.rs

jagua_rs/geometry/
convex_hull.rs
