algebraeon_geometry/
simplex.rs

1use super::*;
2use crate::{
3    affine_subspace::EmbeddedAffineSubspace, ambient_space::AffineSpace,
4    oriented_simplex::OrientedSimplex, vector::Vector,
5};
6use itertools::Itertools;
7
8#[derive(Clone)]
9pub struct Simplex<'f, FS: OrderedRingSignature + FieldSignature> {
10    ambient_space: AffineSpace<'f, FS>,
11    // points must be ordered w.r.t the ordering on vectors
12    // points must be non-degenerate
13    // points must belong to the ambient_space
14    points: Vec<Vector<'f, FS>>,
15}
16
17impl<'f, FS: OrderedRingSignature + FieldSignature> std::fmt::Debug for Simplex<'f, FS> {
18    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
19        f.debug_struct("Simplex")
20            .field("points", &self.points)
21            .finish()
22    }
23}
24
25impl<'f, FS: OrderedRingSignature + FieldSignature> PartialEq for Simplex<'f, FS> {
26    fn eq(&self, other: &Self) -> bool {
27        self.ambient_space == other.ambient_space && self.points == other.points
28    }
29}
30
31impl<'f, FS: OrderedRingSignature + FieldSignature> Eq for Simplex<'f, FS> {}
32
33impl<'f, FS: OrderedRingSignature + FieldSignature> Hash for Simplex<'f, FS>
34where
35    FS::Set: Hash,
36{
37    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
38        self.points.hash(state);
39    }
40}
41
42impl<'f, FS: OrderedRingSignature + FieldSignature> Simplex<'f, FS>
43where
44    AffineSpace<'f, FS>: Clone,
45{
46    fn new(
47        ambient_space: AffineSpace<'f, FS>,
48        mut points: Vec<Vector<'f, FS>>,
49    ) -> Result<Self, &'static str> {
50        for point in &points {
51            assert_eq!(ambient_space, point.ambient_space());
52        }
53        points.sort_unstable();
54        if ambient_space
55            .borrow()
56            .are_points_affine_independent(points.iter().collect())
57        {
58            Ok(Self {
59                ambient_space,
60                points,
61            })
62        } else {
63            Err("Can't make a simplex using degenerate points")
64        }
65    }
66}
67
68impl<'f, FS: OrderedRingSignature + FieldSignature> AffineSpace<'f, FS>
69where
70    AffineSpace<'f, FS>: Clone,
71{
72    pub fn simplex(&self, points: Vec<Vector<'f, FS>>) -> Result<Simplex<'f, FS>, &'static str> {
73        Simplex::new(*self, points)
74    }
75}
76
77impl<'f, FS: OrderedRingSignature + FieldSignature> Simplex<'f, FS>
78where
79    AffineSpace<'f, FS>: Clone,
80{
81    pub fn ambient_space(&self) -> AffineSpace<'f, FS> {
82        self.ambient_space
83    }
84
85    pub fn n(&self) -> usize {
86        self.points.len()
87    }
88
89    pub fn points(&self) -> &Vec<Vector<'f, FS>> {
90        &self.points
91    }
92
93    pub fn into_points(self) -> Vec<Vector<'f, FS>> {
94        self.points
95    }
96
97    pub fn point(&self, i: usize) -> &Vector<'f, FS> {
98        &self.points[i]
99    }
100
101    pub fn skeleton(&self, skel_n: isize) -> Vec<Self> {
102        if skel_n < 0 {
103            vec![]
104        } else {
105            let skel_n = skel_n as usize;
106            let mut parts = vec![];
107            for subset in (0..self.points.len()).combinations(skel_n) {
108                let part = Self::new(
109                    self.ambient_space,
110                    subset.into_iter().map(|i| self.points[i].clone()).collect(),
111                )
112                .unwrap();
113                parts.push(part);
114            }
115            parts
116        }
117    }
118
119    pub fn vertices(&self) -> Vec<Self> {
120        self.skeleton(1)
121    }
122
123    pub fn edges(&self) -> Vec<Self> {
124        self.skeleton(2)
125    }
126
127    pub fn faces(&self) -> Vec<Self> {
128        self.skeleton(3)
129    }
130
131    pub fn ridges(&self) -> Vec<Self> {
132        self.skeleton(self.points.len() as isize - 2)
133    }
134
135    pub fn facets(&self) -> Vec<Self> {
136        self.skeleton(self.points.len() as isize - 1)
137    }
138
139    pub fn facet(&self, k: usize) -> Self {
140        assert!(k <= self.points.len());
141        Self::new(self.ambient_space, {
142            let mut facet_points = self.points.clone();
143            facet_points.remove(k);
144            facet_points
145        })
146        .unwrap()
147    }
148
149    pub fn sub_simplices(&self) -> Vec<Self> {
150        self.points()
151            .clone()
152            .into_iter()
153            .powerset()
154            .map(|sub_points| Self::new(self.ambient_space, sub_points).unwrap())
155            .collect()
156    }
157
158    pub fn sub_simplices_not_null(&self) -> Vec<Self> {
159        self.sub_simplices()
160            .into_iter()
161            .filter(|spx| spx.n() != 0)
162            .collect()
163    }
164
165    pub fn proper_sub_simplices_not_null(&self) -> Vec<Self> {
166        self.sub_simplices()
167            .into_iter()
168            .filter(|spx| spx.n() != 0 && spx.n() != self.n())
169            .collect()
170    }
171
172    pub fn sub_simplex(&self, pts: Vec<usize>) -> Self {
173        Self::new(
174            self.ambient_space(),
175            pts.iter().map(|idx| self.points[*idx].clone()).collect(),
176        )
177        .unwrap()
178    }
179
180    pub fn oriented_facet(&self, k: usize) -> OrientedSimplex<'f, FS> {
181        //return the oriented facet of self with negative side on the outside and positive side on the inside
182        assert!(k <= self.points.len());
183        let mut facet_points = self.points.clone();
184        let other_pt = facet_points.remove(k);
185        OrientedSimplex::new_with_positive_point(self.ambient_space, facet_points, &other_pt)
186            .unwrap()
187    }
188
189    pub fn oriented_facets(&self) -> Vec<OrientedSimplex<'f, FS>> {
190        assert_eq!(self.ambient_space.borrow().affine_dimension(), self.n());
191        (0..self.n()).map(|k| self.oriented_facet(k)).collect()
192    }
193
194    pub fn into_affine_span(self) -> (EmbeddedAffineSubspace<'f, FS>, Vec<Vector<'f, FS>>) {
195        EmbeddedAffineSubspace::new_affine_independent_span(self.ambient_space, self.into_points())
196            .unwrap()
197    }
198}
199
200#[cfg(test)]
201mod tests {
202    use super::*;
203    use algebraeon_nzq::Rational;
204
205    #[test]
206    fn make_simplex() {
207        let space = AffineSpace::new_linear(Rational::structure_ref(), 2);
208        let v1 = space.vector([1, 1]);
209        let v2 = space.vector([1, 0]);
210        let v3 = space.vector([0, 1]);
211        let s = Simplex::new(space, vec![v1, v2, v3]);
212        assert!(s.is_ok());
213
214        let space = AffineSpace::new_linear(Rational::structure_ref(), 2);
215        let v1 = space.vector([0, 0]);
216        let v2 = space.vector([1, 0]);
217        let v3 = space.vector([2, 0]);
218        let s = Simplex::new(space, vec![v1, v2, v3]);
219        assert!(s.is_err());
220    }
221
222    #[test]
223    fn simplex_skeleton() {
224        let space = AffineSpace::new_linear(Rational::structure_ref(), 2);
225        let v1 = space.vector([1, 1]);
226        let v2 = space.vector([1, 0]);
227        let v3 = space.vector([0, 1]);
228        let s = Simplex::new(space, vec![v1, v2, v3]).unwrap();
229
230        assert_eq!(s.skeleton(-2).len(), 0);
231        assert_eq!(s.skeleton(-1).len(), 0);
232        assert_eq!(s.skeleton(0).len(), 1);
233        assert_eq!(s.vertices().len(), 3);
234        assert_eq!(s.edges().len(), 3);
235        assert_eq!(s.faces().len(), 1);
236        assert_eq!(s.skeleton(4).len(), 0);
237    }
238}
algebraeon_geometry/simplex.rs

algebraeon_geometry/
simplex.rs
