algebraeon_geometry/
minkowski_sum.rs

1use crate::{
2    ambient_space::common_space,
3    partial_simplicial_complex::PartialSimplicialComplex,
4    simplex_collection::{InteriorOrBoundarySimplexCollection, LabelledSimplexCollection},
5    simplicial_disjoint_union::SimplicialDisjointUnion,
6};
7use algebraeon_rings::structure::{FieldSignature, OrderedRingSignature};
8use itertools::Itertools;
9use rayon::iter::{IntoParallelIterator, ParallelIterator};
10use std::hash::Hash;
11
12pub trait MinkowskiSumRaw<Other> {
13    type Output;
14    fn minkowski_sum_raw(&self, other: &Other) -> Self::Output;
15}
16
17pub trait MinkowskiSum<Other> {
18    type Output;
19    fn minkowski_sum(&self, other: &Other) -> Self::Output;
20}
21
22impl<'f, FS: OrderedRingSignature + FieldSignature>
23    MinkowskiSumRaw<PartialSimplicialComplex<'f, FS>> for PartialSimplicialComplex<'f, FS>
24where
25    FS::Set: Hash,
26{
27    type Output = SimplicialDisjointUnion<'f, FS>;
28
29    fn minkowski_sum_raw(&self, other: &PartialSimplicialComplex<'f, FS>) -> Self::Output {
30        let space = common_space(self.ambient_space(), other.ambient_space()).unwrap();
31
32        self.simplexes()
33            .into_iter()
34            .cartesian_product(other.simplexes().into_iter().collect::<Vec<_>>())
35            .collect::<Vec<_>>()
36            .into_par_iter()
37            .map(|(self_spx, other_spx)| {
38                let mut points = vec![];
39                for p in self_spx.points() {
40                    for q in other_spx.points() {
41                        points.push(p + q);
42                    }
43                }
44                space
45                    .convex_hull(points)
46                    .to_simplicial_complex()
47                    .interior()
48                    .into_simplicial_disjoint_union()
49            })
50            .reduce(
51                || space.empty_subset().into_simplicial_disjoint_union(),
52                |left, right| left.union_raw(&right),
53            )
54    }
55}
56
57impl<'f, FS: OrderedRingSignature + FieldSignature> MinkowskiSum<PartialSimplicialComplex<'f, FS>>
58    for PartialSimplicialComplex<'f, FS>
59where
60    FS::Set: Hash,
61{
62    type Output = PartialSimplicialComplex<'f, FS>;
63
64    fn minkowski_sum(&self, other: &PartialSimplicialComplex<'f, FS>) -> Self::Output {
65        self.minkowski_sum_raw(other)
66            .refine_into_partial_simplicial_complex()
67            .simplify()
68    }
69}
algebraeon_geometry/minkowski_sum.rs

algebraeon_geometry/
minkowski_sum.rs
