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 geometry. 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/// assert_eq!(res.interiors(), &[]);
41/// ```
42pub trait ConvexHull<'a, T> {
43    type Scalar: GeoNum;
44    fn convex_hull(&'a self) -> Polygon<Self::Scalar>;
45}
46
47use crate::algorithm::CoordsIter;
48use crate::utils::lex_cmp;
49
50impl<'a, T, G> ConvexHull<'a, T> for G
51where
52    T: GeoNum,
53    G: CoordsIter<Scalar = T>,
54{
55    type Scalar = T;
56
57    fn convex_hull(&'a self) -> Polygon<T> {
58        let mut exterior: Vec<_> = self.exterior_coords_iter().collect();
59        Polygon::new(quick_hull(&mut exterior), vec![])
60    }
61}
62
63pub mod qhull;
64pub use qhull::quick_hull;
65
66pub mod graham;
67pub use graham::graham_hull;
68
69// Helper function that outputs the convex hull in the
70// trivial case: input with at most 3 points. It ensures the
71// output is ccw, and does not repeat points unless
72// required.
73fn trivial_hull<T>(points: &mut [Coord<T>], include_on_hull: bool) -> LineString<T>
74where
75    T: GeoNum,
76{
77    assert!(points.len() < 4);
78
79    // Remove repeated points unless collinear points
80    // are to be included.
81    let mut ls: Vec<Coord<T>> = points.to_vec();
82    if !include_on_hull {
83        ls.sort_unstable_by(lex_cmp);
84        if ls.len() == 3 && T::Ker::orient2d(ls[0], ls[1], ls[2]) == Orientation::Collinear {
85            ls.remove(1);
86        }
87    }
88
89    // A linestring with a single point is invalid.
90    if ls.len() == 1 {
91        ls.push(ls[0]);
92    }
93
94    let mut ls = LineString::new(ls);
95    ls.close();
96
97    // Maintain the CCW invariance
98    use super::winding_order::Winding;
99    ls.make_ccw_winding();
100    ls
101}
102
103/// Utility function for convex hull ops
104///
105/// 1. _swap_ the element at `idx` with the element at `head` (0th position)
106/// 2. remove the _new_ `head` element (modifying the slice)
107/// 3. return a _mutable ref_ to the removed head element
108fn swap_with_first_and_remove<'a, T>(slice: &mut &'a mut [T], idx: usize) -> &'a mut T {
109    // temporarily replace `slice` with an empty value
110    let tmp = std::mem::take(slice);
111    tmp.swap(0, idx);
112    let (h, t) = tmp.split_first_mut().unwrap();
113    *slice = t;
114    h
115}
116
117#[cfg(test)]
118mod test;
geo/algorithm/convex_hull/mod.rs

geo/algorithm/convex_hull/
mod.rs
