Mercurial > repos > alg_tools / file comparison

comparison: src/sets.rs

src/sets.rs

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

Mercurial Repository: alg_tools

mercurial