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
87    /// A 0-, 1-, or 2-point input passes through the degenerate guard
88    /// unchanged.
89    #[test]
90    fn hull_of_fewer_than_three_points_is_the_input() {
91        let empty = MultiPoint::<Pt>(alloc::vec![]);
92        assert_eq!(convex_hull(&empty).points().count(), 0);
93        let one = MultiPoint(alloc::vec![Pt::new(3., 4.)]);
94        let hull = convex_hull(&one);
95        assert_eq!(hull.points().count(), 1);
96        assert_eq!(hull.0[0].get::<0>(), 3.0);
97        let two = MultiPoint(alloc::vec![Pt::new(0., 0.), Pt::new(1., 1.)]);
98        assert_eq!(convex_hull(&two).points().count(), 2);
99    }
100
101    /// The hull of a linestring: only its convex corners survive.
102    #[test]
103    fn hull_of_linestring() {
104        use geometry_model::{Linestring, linestring};
105        let ls: Linestring<Pt> = linestring![(0., 0.), (4., 0.), (4., 4.), (2., 2.)];
106        let hull = convex_hull(&ls);
107        // Triangle (0,0)(4,0)(4,4) + closing duplicate = 4 stored.
108        assert_eq!(hull.points().count(), 4);
109    }
110
111    /// The hull of a standalone ring drops its reflex vertex.
112    #[test]
113    fn hull_of_ring() {
114        use geometry_model::Ring;
115        let r: Ring<Pt> = Ring::from_vec(alloc::vec![
116            Pt::new(0., 0.),
117            Pt::new(4., 0.),
118            Pt::new(2., 1.), // reflex vertex — dropped by the hull
119            Pt::new(4., 4.),
120            Pt::new(0., 4.),
121            Pt::new(0., 0.),
122        ]);
123        let hull = convex_hull(&r);
124        assert_eq!(hull.points().count(), 5); // 4 corners + closing dup
125        assert!(
126            !hull
127                .0
128                .iter()
129                .any(|p| p.get::<0>() == 2.0 && p.get::<1>() == 1.0)
130        );
131    }
132
133    /// Only the exterior ring feeds a polygon's hull — interior-ring
134    /// points never appear.
135    #[test]
136    fn hull_of_polygon_ignores_holes() {
137        let pg: Polygon<Pt> = polygon![
138            [(0., 0.), (4., 0.), (4., 4.), (0., 4.), (0., 0.)],
139            [(1., 1.), (2., 1.), (2., 2.), (1., 2.), (1., 1.)],
140        ];
141        let hull = convex_hull(&pg);
142        assert_eq!(hull.points().count(), 5);
143        assert!(
144            !hull
145                .0
146                .iter()
147                .any(|p| p.get::<0>() == 1.0 && p.get::<1>() == 1.0)
148        );
149    }
150}
geometry_algorithm/convex_hull.rs

geometry_algorithm/
convex_hull.rs
