Tue, 06 Dec 2022 08:29:13 +0200
cargo-d alias generation with a cargo-d script
5 | 1 | /*! |
2 | This module provides various sets and traits for them. | |
3 | */ | |
4 | ||
0 | 5 | use std::ops::{RangeFull,RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive}; |
6 | use std::marker::PhantomData; | |
7 | use crate::types::*; | |
5 | 8 | use crate::loc::Loc; |
9 | use crate::euclidean::Dot; | |
0 | 10 | use serde::Serialize; |
11 | ||
5 | 12 | mod cube; |
13 | pub use cube::Cube; | |
0 | 14 | |
15 | /// Trait for arbitrary sets. The parameter `U` is the element type. | |
16 | pub trait Set<U> where U : ?Sized { | |
5 | 17 | /// Check for element containment |
0 | 18 | fn contains(&self, item : &U) -> bool; |
19 | } | |
20 | ||
5 | 21 | /// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets: |
22 | /// greatest lower bound and least upper bound. | |
0 | 23 | pub trait SetOrd : Sized { |
24 | /// Returns the smallest set of same class contain both parameters. | |
25 | fn common(&self, other : &Self) -> Self; | |
26 | ||
27 | /// Returns the greatest set of same class contaied by n both parameter sets. | |
28 | fn intersect(&self, other : &Self) -> Option<Self>; | |
29 | } | |
30 | ||
31 | impl<U, const N : usize> Set<Loc<U, N>> | |
32 | for Cube<U,N> | |
33 | where U : Num + PartialOrd + Sized { | |
34 | fn contains(&self, item : &Loc<U, N>) -> bool { | |
35 | self.0.iter().zip(item.iter()).all(|(s, x)| s.contains(x)) | |
36 | } | |
37 | } | |
38 | ||
39 | impl<U> Set<U> for RangeFull { | |
40 | fn contains(&self, _item : &U) -> bool { true } | |
41 | } | |
42 | ||
43 | macro_rules! impl_ranges { | |
44 | ($($range:ident),*) => { $( | |
45 | impl<U,Idx> Set<U> | |
46 | for $range<Idx> | |
47 | where Idx : PartialOrd<U>, U : PartialOrd<Idx> + ?Sized, Idx : PartialOrd { | |
48 | #[inline] | |
49 | fn contains(&self, item : &U) -> bool { $range::contains(&self, item) } | |
50 | } | |
51 | )* } | |
52 | } | |
53 | ||
54 | impl_ranges!(RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive); | |
55 | ||
5 | 56 | /// Halfspaces described by an orthogonal vector and an offset. |
57 | /// | |
58 | /// The halfspace is $H = \\{ t v + a \mid a^⊤ v = 0 \\}$, where $v$ is the orthogonal | |
59 | /// vector and $t$ the offset. | |
60 | /// | |
61 | /// `U` is the element type, `F` the floating point number type, and `A` the type of the | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
62 | /// orthogonal (dual) vectors. They need implement [`Dot<U, F>`]. |
0 | 63 | #[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)] |
5 | 64 | pub struct Halfspace<A, F, U> where A : Dot<U, F>, F : Float { |
0 | 65 | pub orthogonal : A, |
66 | pub offset : F, | |
67 | _phantom : PhantomData<U>, | |
68 | } | |
69 | ||
70 | impl<A,F,U> Halfspace<A,F,U> where A : Dot<U,F>, F : Float { | |
71 | #[inline] | |
72 | pub fn new(orthogonal : A, offset : F) -> Self { | |
73 | Halfspace{ orthogonal : orthogonal, offset : offset, _phantom : PhantomData } | |
74 | } | |
75 | } | |
76 | ||
5 | 77 | /// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`. |
78 | pub trait SpannedHalfspace<F, U> where F : Float { | |
79 | /// Type of the orthogonal vector describing the halfspace. | |
80 | type A : Dot<U, F>; | |
81 | /// Returns the halfspace spanned by this set. | |
0 | 82 | fn spanned_halfspace(&self) -> Halfspace<Self::A, F, U>; |
83 | } | |
84 | ||
85 | // TODO: Gram-Schmidt for higher N. | |
86 | impl<F : Float> SpannedHalfspace<F,Loc<F, 1>> for [Loc<F, 1>; 2] { | |
87 | type A = Loc<F, 1>; | |
88 | fn spanned_halfspace(&self) -> Halfspace<Self::A, F, Loc<F, 1>> { | |
89 | let (x0, x1) = (self[0], self[1]); | |
90 | Halfspace::new(x1-x0, x0[0]) | |
91 | } | |
92 | } | |
93 | ||
94 | // TODO: Gram-Schmidt for higher N. | |
95 | impl<F : Float> SpannedHalfspace<F,Loc<F, 2>> for [Loc<F, 2>; 2] { | |
96 | type A = Loc<F, 2>; | |
97 | fn spanned_halfspace(&self) -> Halfspace<Self::A, F, Loc<F, 2>> { | |
98 | let (x0, x1) = (&self[0], &self[1]); | |
99 | let d = x1 - x0; | |
100 | let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency | |
101 | let offset = x0.dot(&orthog); | |
102 | Halfspace::new(orthog, offset) | |
103 | } | |
104 | } | |
105 | ||
106 | impl<A,U,F> Set<U> for Halfspace<A,F,U> where A : Dot<U,F>, F : Float { | |
107 | #[inline] | |
108 | fn contains(&self, item : &U) -> bool { | |
109 | self.orthogonal.dot(item) >= self.offset | |
110 | } | |
111 | } | |
112 | ||
113 | /// Polygons defined by `N` `Halfspace`s. | |
114 | #[derive(Clone,Copy,Debug,Eq,PartialEq)] | |
115 | pub struct NPolygon<A, F, U, const N : usize>(pub [Halfspace<A,F,U>; N]) where A : Dot<U,F>, F : Float; | |
116 | ||
117 | impl<A,U,F,const N : usize> Set<U> for NPolygon<A,F,U,N> where A : Dot<U,F>, F : Float { | |
118 | fn contains(&self, item : &U) -> bool { | |
119 | self.0.iter().all(|halfspace| halfspace.contains(item)) | |
120 | } | |
121 | } |