geo/algorithm/convex_hull/
mod.rs

1use crate::geometry::{Coord, LineString, Polygon};
2use crate::kernels::*;
3use crate::GeoNum;
4
5/// Returns the convex hull of a Polygon. The hull is always oriented counter-clockwise.
6///
7/// This implementation uses the QuickHull algorithm,
8/// based on [Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996)](https://dx.doi.org/10.1145%2F235815.235821)
9/// Original paper here: <http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf>
10///
11/// # Examples
12///
13/// ```
14/// use geo::{line_string, polygon};
15/// use geo::ConvexHull;
16///
17/// // an L shape
18/// let poly = polygon![
19///     (x: 0.0, y: 0.0),
20///     (x: 4.0, y: 0.0),
21///     (x: 4.0, y: 1.0),
22///     (x: 1.0, y: 1.0),
23///     (x: 1.0, y: 4.0),
24///     (x: 0.0, y: 4.0),
25///     (x: 0.0, y: 0.0),
26/// ];
27///
28/// // The correct convex hull coordinates
29/// let correct_hull = line_string![
30///     (x: 4.0, y: 0.0),
31///     (x: 4.0, y: 1.0),
32///     (x: 1.0, y: 4.0),
33///     (x: 0.0, y: 4.0),
34///     (x: 0.0, y: 0.0),
35///     (x: 4.0, y: 0.0),
36/// ];
37///
38/// let res = poly.convex_hull();
39/// assert_eq!(res.exterior(), &correct_hull);
40/// ```
41pub trait ConvexHull<'a, T> {
42    type Scalar: GeoNum;
43    fn convex_hull(&'a self) -> Polygon<Self::Scalar>;
44}
45
46use crate::algorithm::CoordsIter;
47use crate::utils::lex_cmp;
48
49impl<'a, T, G> ConvexHull<'a, T> for G
50where
51    T: GeoNum,
52    G: CoordsIter<'a, Scalar = T>,
53{
54    type Scalar = T;
55
56    fn convex_hull(&'a self) -> Polygon<T> {
57        let mut exterior: Vec<_> = self.exterior_coords_iter().collect();
58        Polygon::new(quick_hull(&mut exterior), vec![])
59    }
60}
61
62pub mod qhull;
63pub use qhull::quick_hull;
64
65pub mod graham;
66pub use graham::graham_hull;
67
68// Helper function that outputs the convex hull in the
69// trivial case: input with at most 3 points. It ensures the
70// output is ccw, and does not repeat points unless
71// required.
72fn trivial_hull<T>(points: &mut [Coord<T>], include_on_hull: bool) -> LineString<T>
73where
74    T: GeoNum,
75{
76    assert!(points.len() < 4);
77
78    // Remove repeated points unless collinear points
79    // are to be included.
80    let mut ls: Vec<Coord<T>> = points.to_vec();
81    if !include_on_hull {
82        ls.sort_unstable_by(lex_cmp);
83        if ls.len() == 3 && T::Ker::orient2d(ls[0], ls[1], ls[2]) == Orientation::Collinear {
84            ls.remove(1);
85        }
86    }
87
88    // A linestring with a single point is invalid.
89    if ls.len() == 1 {
90        ls.push(ls[0]);
91    }
92
93    let mut ls = LineString::new(ls);
94    ls.close();
95
96    // Maintain the CCW invariance
97    use super::winding_order::Winding;
98    ls.make_ccw_winding();
99    ls
100}
101
102// Utility function: swap idx to head(0th position), remove
103// head (modifies the slice), and return head as a reference
104fn swap_remove_to_first<'a, T>(slice: &mut &'a mut [T], idx: usize) -> &'a mut T {
105    // temporarily replace `slice` with an empty value
106    let tmp = std::mem::take(slice);
107    tmp.swap(0, idx);
108    let (h, t) = tmp.split_first_mut().unwrap();
109    *slice = t;
110    h
111}
112
113#[cfg(test)]
114mod test;
geo/algorithm/convex_hull/mod.rs

geo/algorithm/convex_hull/
mod.rs
