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