geop_core_math/convex_hull/
mod.rs

1pub mod gjk;
2
3use crate::{scalars::Scalar, vector::Vector};
4
5/// A convex hull represented by its defining point set (e.g. the control
6/// points of a NURBS curve or surface), in `N`-dimensional space.
7///
8/// The hull is never computed explicitly — overlap and containment queries
9/// operate directly on the point set via [`gjk`].  By the convex-hull
10/// property of B-spline / NURBS bases, every point on a curve or surface
11/// patch lies within the convex hull of its (dehomogenized) control points.
12#[derive(Debug, Clone)]
13pub struct ConvexHull<S: Scalar, const N: usize> {
14    pub points: Vec<Vector<S, N>>,
15}
16
17impl<S: Scalar, const N: usize> ConvexHull<S, N> {
18    pub fn new(points: Vec<Vector<S, N>>) -> Self {
19        Self { points }
20    }
21
22    /// The average of this hull's defining points — a representative
23    /// position for the region it bounds, used e.g. to detect near-duplicate
24    /// solutions at a caller-chosen distance tolerance (see
25    /// `curve_surface_intersect`'s dedup check, which can't rely solely on
26    /// `could_overlap` since that bottoms out in each `Scalar`'s own
27    /// built-in equality tolerance rather than the search's own epsilon).
28    pub fn centroid(&self) -> Vector<S, N> {
29        let mut sum = Vector::<S, N>::zero();
30        for p in &self.points {
31            sum = sum.add(p);
32        }
33        sum.prod_scalar(S::ONE.div(S::from_i64(self.points.len() as i64)).unwrap())
34    }
35
36    /// True if `self` and `other` could overlap (intersect or touch).
37    pub fn could_overlap(&self, other: &Self) -> bool {
38        gjk::could_overlap(&self.points, &other.points)
39    }
40
41    /// Negation of [`Self::could_overlap`].
42    pub fn definitely_no_overlap(&self, other: &Self) -> bool {
43        gjk::definitely_no_overlap(&self.points, &other.points)
44    }
45
46    /// True if `point` could lie within this convex hull.
47    pub fn could_contain(&self, point: &Vector<S, N>) -> bool {
48        gjk::could_overlap(&self.points, std::slice::from_ref(point))
49    }
50
51    /// Negation of [`Self::could_contain`].
52    pub fn definitely_not_contains(&self, point: &Vector<S, N>) -> bool {
53        !self.could_contain(point)
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::ConvexHull;
60    use crate::{
61        for_all_scalars,
62        scalars::Scalar,
63        vector::{Vector2, Vector3},
64    };
65
66    fn v3<S: Scalar>(x: f64, y: f64, z: f64) -> Vector3<S> {
67        Vector3::from_array([S::from_f64(x), S::from_f64(y), S::from_f64(z)])
68    }
69
70    fn v2<S: Scalar>(x: f64, y: f64) -> Vector2<S> {
71        Vector2::from_array([S::from_f64(x), S::from_f64(y)])
72    }
73
74    fn unit_square<S: Scalar>() -> ConvexHull<S, 3> {
75        ConvexHull::new(vec![
76            v3(0., 0., 0.),
77            v3(1., 0., 0.),
78            v3(0., 1., 0.),
79            v3(1., 1., 0.),
80        ])
81    }
82
83    fn check_contains_interior_point<S: Scalar>() {
84        let hull = unit_square::<S>();
85        assert!(hull.could_contain(&v3(0.5, 0.5, 0.)));
86    }
87    #[test]
88    fn contains_interior_point() {
89        for_all_scalars!(check_contains_interior_point);
90    }
91
92    fn check_excludes_exterior_point<S: Scalar>() {
93        let hull = unit_square::<S>();
94        assert!(hull.definitely_not_contains(&v3(2., 2., 0.)));
95    }
96    #[test]
97    fn excludes_exterior_point() {
98        for_all_scalars!(check_excludes_exterior_point);
99    }
100
101    fn check_overlapping_hulls<S: Scalar>() {
102        let a = unit_square::<S>();
103        let b = ConvexHull::new(vec![
104            v3(0.5, 0.5, 0.),
105            v3(1.5, 0.5, 0.),
106            v3(0.5, 1.5, 0.),
107            v3(1.5, 1.5, 0.),
108        ]);
109        assert!(a.could_overlap(&b));
110        assert!(!a.definitely_no_overlap(&b));
111    }
112    #[test]
113    fn overlapping_hulls() {
114        for_all_scalars!(check_overlapping_hulls);
115    }
116
117    fn check_separated_hulls<S: Scalar>() {
118        let a = unit_square::<S>();
119        let b = ConvexHull::new(vec![
120            v3(10., 10., 0.),
121            v3(11., 10., 0.),
122            v3(10., 11., 0.),
123            v3(11., 11., 0.),
124        ]);
125        assert!(a.definitely_no_overlap(&b));
126        assert!(!a.could_overlap(&b));
127    }
128    #[test]
129    fn separated_hulls() {
130        for_all_scalars!(check_separated_hulls);
131    }
132
133    /// The same containment/overlap checks, natively in 2-D (no `z=0`
134    /// embedding needed) — confirms `ConvexHull` genuinely works at `N=2`.
135    fn unit_square_2d<S: Scalar>() -> ConvexHull<S, 2> {
136        ConvexHull::new(vec![v2(0., 0.), v2(1., 0.), v2(0., 1.), v2(1., 1.)])
137    }
138
139    fn check_contains_interior_point_2d<S: Scalar>() {
140        let hull = unit_square_2d::<S>();
141        assert!(hull.could_contain(&v2(0.5, 0.5)));
142    }
143    #[test]
144    fn contains_interior_point_2d() {
145        for_all_scalars!(check_contains_interior_point_2d);
146    }
147
148    fn check_excludes_exterior_point_2d<S: Scalar>() {
149        let hull = unit_square_2d::<S>();
150        assert!(hull.definitely_not_contains(&v2(2., 2.)));
151    }
152    #[test]
153    fn excludes_exterior_point_2d() {
154        for_all_scalars!(check_excludes_exterior_point_2d);
155    }
156}
geop_core_math/convex_hull/mod.rs

geop_core_math/convex_hull/
mod.rs
