geometry_algorithm/
convex_hull.rs

1//! `convex_hull(&g) -> Ring<G::Point>` — minimal enclosing ring.
2//!
3//! Mirrors `boost::geometry::convex_hull(g, hull)` from
4//! `boost/geometry/algorithms/convex_hull.hpp`. Boost's overload takes
5//! the hull through an out-parameter; the Rust port returns it by value.
6//! The kernel is Andrew's monotone chain
7//! ([`geometry_strategy::MonotoneChain`]), the port's
8//! stand-in for Boost's default Graham-Andrew strategy from
9//! `boost/geometry/strategies/agnostic/hull_graham_andrew.hpp`.
10
11use geometry_strategy::{ConvexHullStrategy, MonotoneChain};
12use geometry_trait::Point;
13
14/// Compute the convex hull of `g` as a clockwise, closed [`Ring`].
15///
16/// The output ring repeats its first vertex at the end (closed) and is
17/// wound clockwise, matching Boost's default output ring from
18/// `boost/geometry/algorithms/convex_hull.hpp`.
19///
20/// [`Ring`]: geometry_model::Ring
21#[must_use]
22pub fn convex_hull<G, P>(g: &G) -> geometry_model::Ring<P, true, true>
23where
24    MonotoneChain: ConvexHullStrategy<G, Output = geometry_model::Ring<P, true, true>>,
25    P: Point,
26{
27    MonotoneChain.convex_hull(g)
28}
29
30#[cfg(test)]
31#[allow(
32    clippy::float_cmp,
33    reason = "Hull corner coordinates are exact literals."
34)]
35mod tests {
36    //! Reference behaviour from
37    //! `boost/geometry/test/algorithms/convex_hull.cpp` — the hull of a
38    //! square-plus-interior point keeps only the four corners; the hull
39    //! of a concave polygon drops its reflex vertex.
40
41    use super::convex_hull;
42    use geometry_cs::Cartesian;
43    use geometry_model::{MultiPoint, Point2D, Polygon, polygon};
44    use geometry_trait::{Point as _, Ring as _};
45
46    type Pt = Point2D<f64, Cartesian>;
47
48    #[test]
49    fn square_plus_interior_point_hull_has_four_corners() {
50        let mp = MultiPoint(alloc::vec![
51            Pt::new(0., 0.),
52            Pt::new(4., 0.),
53            Pt::new(4., 4.),
54            Pt::new(0., 4.),
55            Pt::new(2., 2.),
56        ]);
57        let hull = convex_hull(&mp);
58        // 4 distinct corners + closing duplicate = 5 stored.
59        assert_eq!(hull.points().count(), 5);
60        // Closed: first == last.
61        assert_eq!(
62            hull.0.first().unwrap().get::<0>(),
63            hull.0.last().unwrap().get::<0>()
64        );
65        assert_eq!(
66            hull.0.first().unwrap().get::<1>(),
67            hull.0.last().unwrap().get::<1>()
68        );
69    }
70
71    #[test]
72    fn concave_polygon_hull_drops_reflex_vertex() {
73        // The (2, 1) vertex is a reflex dent in the left edge; the hull
74        // is the enclosing quad.
75        let pg: Polygon<Pt> =
76            polygon![[(0., 0.), (4., 0.), (2., 1.), (4., 4.), (0., 4.), (0., 0.)]];
77        let hull = convex_hull(&pg);
78        // 4 corners + closing duplicate.
79        assert_eq!(hull.points().count(), 5);
80        let has_reflex = hull
81            .0
82            .iter()
83            .any(|p| p.get::<0>() == 2.0 && p.get::<1>() == 1.0);
84        assert!(!has_reflex);
85    }
86}
geometry_algorithm/convex_hull.rs

geometry_algorithm/
convex_hull.rs
