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
8#[must_use]
9pub fn convex_hull_indices(shape: &SPolygon) -> Vec<usize> {
10    let c_hull = convex_hull_from_points(shape.vertices.clone());
11    let mut indices = vec![];
12    for p in &c_hull {
13        indices.push(shape.vertices.iter().position(|x| x == p).unwrap());
14    }
15    indices
16}
17
18/// Reconstitutes the convex hull of a [`SPolygon`] using its surrogate
19pub fn convex_hull_from_surrogate(s: &SPolygon) -> Result<Vec<Point>> {
20    if let Some(surr) = s.surrogate.as_ref() {
21        Ok(surr
22            .convex_hull_indices
23            .iter()
24            .map(|&i| s.vertices[i])
25            .collect())
26    } else {
27        bail!("no surrogate present")
28    }
29}
30
31/// Filters a set of points to only include those that are part of the convex hull
32#[must_use]
33pub fn convex_hull_from_points(mut points: Vec<Point>) -> Vec<Point> {
34    //https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
35
36    //sort the points by x coordinate
37    points.sort_by_key(|p| OrderedFloat(p.0));
38
39    let mut lower_hull = points
40        .iter()
41        .fold(vec![], |hull, p| grow_convex_hull(hull, *p));
42    let mut upper_hull = points
43        .iter()
44        .rev()
45        .fold(vec![], |hull, p| grow_convex_hull(hull, *p));
46
47    //First and last element of both hull parts are the same point
48    upper_hull.pop();
49    lower_hull.pop();
50
51    lower_hull.append(&mut upper_hull);
52    lower_hull
53}
54
55fn grow_convex_hull(mut h: Vec<Point>, next: Point) -> Vec<Point> {
56    //pop all points from the hull which will be made irrelevant due to the new point
57    while h.len() >= 2 && cross(h[h.len() - 2], h[h.len() - 1], next) <= 0.0 {
58        h.pop();
59    }
60    h.push(next);
61    h
62}
63
64fn cross(a: Point, b: Point, c: Point) -> f32 {
65    (b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0)
66}
jagua_rs/geometry/convex_hull.rs

jagua_rs/geometry/
convex_hull.rs
