geometry_algorithm/
is_convex.rs

1//! `is_convex(&g) -> bool`.
2//!
3//! Mirrors `boost::geometry::is_convex(g)` from
4//! `boost/geometry/algorithms/is_convex.hpp`. A ring is convex iff every
5//! consecutive cross-product `((b − a) × (c − b))` has the same sign
6//! (zero allowed — collinear interior vertices don't disqualify). A
7//! polygon is convex iff its outer ring is convex AND it has no interior
8//! rings.
9//!
10//! This is Cartesian-only: the cross-product predicate is the same in
11//! every Cartesian coordinate system, and spherical / geographic
12//! convexity is a different algorithm not yet in Boost, so no strategy
13//! layer is needed — Boost itself ships `is_convex` as a plain free
14//! function.
15
16use alloc::vec::Vec;
17
18use geometry_coords::CoordinateScalar;
19use geometry_model::{MultiPolygon, Polygon, Ring};
20use geometry_trait::{Point as PointTrait, Polygon as _, Ring as RingTrait};
21
22/// True iff `g` is convex.
23///
24/// Mirrors `boost::geometry::is_convex(g)` from
25/// `boost/geometry/algorithms/is_convex.hpp`.
26#[must_use]
27pub fn is_convex<G: IsConvex>(g: &G) -> bool {
28    g.is_convex()
29}
30
31/// Per-kind convexity dispatch. Implemented for [`Ring`], [`Polygon`],
32/// and [`MultiPolygon`].
33#[doc(hidden)]
34pub trait IsConvex {
35    /// True iff `self` is convex.
36    fn is_convex(&self) -> bool;
37}
38
39/// Convexity test for a ring: every consecutive cross-product shares one
40/// sign (zero permitted). Uses modular indexing so the closing edge of a
41/// closed ring is checked too.
42fn ring_is_convex<P: PointTrait, const CW: bool, const CL: bool>(ring: &Ring<P, CW, CL>) -> bool {
43    let pts: Vec<&P> = ring.points().collect();
44    let len = pts.len();
45    if len < 3 {
46        return true;
47    }
48
49    let zero = P::Scalar::ZERO;
50    let mut sign: Option<bool> = None; // Some(true) = positive turn
51    for index in 0..len {
52        let prev = pts[index];
53        let curr = pts[(index + 1) % len];
54        let next = pts[(index + 2) % len];
55        let edge_in_x = curr.get::<0>() - prev.get::<0>();
56        let edge_in_y = curr.get::<1>() - prev.get::<1>();
57        let edge_out_x = next.get::<0>() - curr.get::<0>();
58        let edge_out_y = next.get::<1>() - curr.get::<1>();
59        let cross = edge_in_x * edge_out_y - edge_in_y * edge_out_x;
60        if cross == zero {
61            continue;
62        }
63        let positive = cross > zero;
64        match sign {
65            None => sign = Some(positive),
66            Some(previous) if previous != positive => return false,
67            _ => {}
68        }
69    }
70    true
71}
72
73impl<P: PointTrait, const CW: bool, const CL: bool> IsConvex for Ring<P, CW, CL> {
74    fn is_convex(&self) -> bool {
75        ring_is_convex(self)
76    }
77}
78
79impl<P: PointTrait, const CW: bool, const CL: bool> IsConvex for Polygon<P, CW, CL> {
80    fn is_convex(&self) -> bool {
81        self.interiors().count() == 0 && ring_is_convex(self.exterior())
82    }
83}
84
85impl<Pg: IsConvex + geometry_trait::Polygon> IsConvex for MultiPolygon<Pg> {
86    fn is_convex(&self) -> bool {
87        self.0.iter().all(IsConvex::is_convex)
88    }
89}
90
91#[cfg(test)]
92mod tests {
93    //! Reference behaviour from
94    //! `boost/geometry/test/algorithms/is_convex.cpp` — a triangle /
95    //! square is convex; a reflex polygon and any polygon with a hole
96    //! are not.
97
98    use super::is_convex;
99    use geometry_cs::Cartesian;
100    use geometry_model::{Point2D, Polygon, polygon};
101
102    type Pt = Point2D<f64, Cartesian>;
103
104    #[test]
105    fn triangle_is_convex() {
106        let pg: Polygon<Pt> = polygon![[(0., 0.), (4., 0.), (2., 3.), (0., 0.)]];
107        assert!(is_convex(&pg));
108    }
109
110    #[test]
111    fn square_is_convex() {
112        let pg: Polygon<Pt> = polygon![[(0., 0.), (4., 0.), (4., 4.), (0., 4.), (0., 0.)]];
113        assert!(is_convex(&pg));
114    }
115
116    #[test]
117    fn reflex_polygon_is_not_convex() {
118        let pg: Polygon<Pt> =
119            polygon![[(0., 0.), (4., 0.), (2., 1.), (4., 4.), (0., 4.), (0., 0.)]];
120        assert!(!is_convex(&pg));
121    }
122
123    #[test]
124    fn polygon_with_hole_is_not_convex() {
125        let pg: Polygon<Pt> = polygon![
126            [(0., 0.), (4., 0.), (4., 4.), (0., 4.), (0., 0.)],
127            [(1., 1.), (2., 1.), (2., 2.), (1., 2.), (1., 1.)],
128        ];
129        assert!(!is_convex(&pg));
130    }
131}
geometry_algorithm/is_convex.rs

geometry_algorithm/
is_convex.rs
