symtropy_math/
hyperbox.rs

1// Copyright (C) 2024-2026 Tristan Stoltz / Luminous Dynamics
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Commercial licensing: see COMMERCIAL_LICENSE.md at repository root
4//! D-dimensional axis-aligned box (hyperbox / tesseract).
5//!
6//! The support function is O(D) — simply `sign(d[i]) * half_extents[i]` per axis.
7//! This is dramatically faster than `ConvexHull::hyperbox()` which is O(2^D)
8//! because it iterates over all vertices. For D=4, that's O(4) vs O(16).
9
10use crate::point::Point;
11use crate::shape::Shape;
12use nalgebra::SVector;
13
14/// D-dimensional axis-aligned box centered at the origin.
15///
16/// `half_extents[i]` is the half-width along axis `i`.
17/// Total size along axis `i` = `2 * half_extents[i]`.
18#[derive(Clone, Copy, Debug)]
19pub struct HyperBox<const D: usize> {
20    pub half_extents: [f64; D],
21}
22
23impl<const D: usize> HyperBox<D> {
24    /// Create a box with the given half-extents per axis.
25    pub fn new(half_extents: [f64; D]) -> Self {
26        Self { half_extents }
27    }
28
29    /// Create a uniform cube (all axes equal).
30    pub fn cube(half_extent: f64) -> Self {
31        Self {
32            half_extents: [half_extent; D],
33        }
34    }
35
36    /// Volume of the hyperbox: product of (2 * half_extent_i) for all axes.
37    pub fn volume(&self) -> f64 {
38        self.half_extents.iter().map(|h| 2.0 * h).product()
39    }
40
41    /// Whether a local-space point is inside the box.
42    pub fn contains_local(&self, point: &Point<D>) -> bool {
43        (0..D).all(|i| point.coord(i).abs() <= self.half_extents[i])
44    }
45}
46
47impl<const D: usize> Shape<D> for HyperBox<D> {
48    /// Support function: `support(d)[i] = sign(d[i]) * half_extents[i]`.
49    ///
50    /// O(D) — no vertex enumeration. For a 4D tesseract, this is 4 operations
51    /// instead of 16 (the vertex count of a tesseract).
52    fn support(&self, direction: &SVector<f64, D>) -> SVector<f64, D> {
53        SVector::from_fn(|i, _| {
54            if direction[i] >= 0.0 {
55                self.half_extents[i]
56            } else {
57                -self.half_extents[i]
58            }
59        })
60    }
61
62    fn bounding_sphere(&self) -> (Point<D>, f64) {
63        let radius = self.half_extents.iter().map(|h| h * h).sum::<f64>().sqrt();
64        (Point::origin(), radius)
65    }
66
67    fn as_any(&self) -> &dyn std::any::Any {
68        self
69    }
70
71    fn clone_box(&self) -> Box<dyn Shape<D>> {
72        Box::new(*self)
73    }
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn support_axis_aligned() {
82        let b = HyperBox::<3>::new([2.0, 3.0, 1.0]);
83        let dir = SVector::from([1.0, 0.0, 0.0]);
84        let sp = b.support(&dir);
85        assert!((sp[0] - 2.0).abs() < 1e-12);
86        assert!((sp[1] - 3.0).abs() < 1e-12); // tie goes to positive
87        assert!((sp[2] - 1.0).abs() < 1e-12);
88    }
89
90    #[test]
91    fn support_negative() {
92        let b = HyperBox::<3>::cube(1.0);
93        let dir = SVector::from([-1.0, -1.0, -1.0]);
94        let sp = b.support(&dir);
95        assert!((sp[0] - (-1.0)).abs() < 1e-12);
96        assert!((sp[1] - (-1.0)).abs() < 1e-12);
97        assert!((sp[2] - (-1.0)).abs() < 1e-12);
98    }
99
100    #[test]
101    fn support_dot_matches_convex_hull() {
102        use crate::convex_hull::ConvexHull;
103
104        let hb = HyperBox::<3>::new([2.0, 1.0, 3.0]);
105        let ch = ConvexHull::<3>::hyperbox([2.0, 1.0, 3.0]);
106
107        // Support points may differ when d[i]==0 (any sign is valid).
108        // What matters: dot(support, direction) must be equal (both maximize it).
109        let dirs = [
110            SVector::from([1.0, 0.0, 0.0]),
111            SVector::from([0.0, -1.0, 0.0]),
112            SVector::from([1.0, 1.0, 1.0]),
113            SVector::from([-0.5, 0.3, 0.8]),
114            SVector::from([0.7, -0.7, 0.1]),
115        ];
116        for dir in &dirs {
117            let dot_hb = hb.support(dir).dot(dir);
118            let dot_ch = ch.support(dir).dot(dir);
119            assert!(
120                (dot_hb - dot_ch).abs() < 1e-10,
121                "support·dir differs for {:?}: hb={dot_hb}, ch={dot_ch}",
122                dir
123            );
124        }
125    }
126
127    #[test]
128    fn bounding_sphere_radius() {
129        let b = HyperBox::<3>::new([3.0, 4.0, 0.0]);
130        let (_, radius) = b.bounding_sphere();
131        assert!((radius - 5.0).abs() < 1e-12); // sqrt(9+16+0) = 5
132    }
133
134    #[test]
135    fn volume() {
136        let b = HyperBox::<3>::new([1.0, 2.0, 3.0]);
137        assert!((b.volume() - 48.0).abs() < 1e-12); // 2*4*6
138    }
139
140    #[test]
141    fn contains_local() {
142        let b = HyperBox::<3>::cube(1.0);
143        assert!(b.contains_local(&Point::origin()));
144        assert!(b.contains_local(&Point::new([0.5, 0.5, 0.5])));
145        assert!(!b.contains_local(&Point::new([1.5, 0.0, 0.0])));
146    }
147
148    #[test]
149    fn tesseract_4d() {
150        let b = HyperBox::<4>::cube(1.0);
151        let dir = SVector::from([1.0, 1.0, 1.0, 1.0]);
152        let sp = b.support(&dir);
153        for i in 0..4 {
154            assert!((sp[i] - 1.0).abs() < 1e-12);
155        }
156        let (_, radius) = b.bounding_sphere();
157        assert!((radius - 2.0).abs() < 1e-12); // sqrt(4) = 2
158    }
159
160    #[test]
161    fn hyperbox_2d() {
162        let b = HyperBox::<2>::new([3.0, 1.0]);
163        let dir = SVector::from([1.0, -1.0]);
164        let sp = b.support(&dir);
165        assert!((sp[0] - 3.0).abs() < 1e-12);
166        assert!((sp[1] - (-1.0)).abs() < 1e-12);
167    }
168
169    #[test]
170    fn cube_is_uniform() {
171        let b = HyperBox::<3>::cube(2.5);
172        assert!((b.half_extents[0] - 2.5).abs() < 1e-12);
173        assert!((b.half_extents[1] - 2.5).abs() < 1e-12);
174        assert!((b.half_extents[2] - 2.5).abs() < 1e-12);
175    }
176}
symtropy_math/hyperbox.rs

symtropy_math/
hyperbox.rs
