Mercurial > repos > alg_tools / file comparison

comparison: src/sets.rs

src/sets.rs

branch
dev
changeset 124
6aa955ad8122
parent 75
e9f4550cfa18
child 131
8264d72aa347
child 133
2b13f8a0c8ba
equal deleted inserted replaced
122:495448cca603 124:6aa955ad8122
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 crate::euclidean::Euclidean;
6 use crate::instance::{Instance, Space};
7 use crate::loc::Loc;
6 use crate::types::*; 8 use crate::types::*;
7 use crate::loc::Loc;
8 use crate::euclidean::Euclidean;
9 use crate::instance::{Space, Instance};
10 use serde::Serialize; 9 use serde::Serialize;
10 use std::ops::{Range, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive};
11 11
12 pub 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 : Space { 16 pub trait Set<U>
17 where
18 U: Space,
19 {
17 /// Check for element containment 20 /// Check for element containment
18 fn contains<I : Instance<U>>(&self, item : I) -> bool; 21 fn contains<I: Instance<U>>(&self, item: I) -> bool;
19 } 22 }
20 23
21 /// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets: 24 /// Additional ordering (besides [`PartialOrd`]) of a subfamily of sets:
22 /// greatest lower bound and least upper bound. 25 /// greatest lower bound and least upper bound.
23 pub trait SetOrd : Sized { 26 pub trait SetOrd: Sized {
24 /// Returns the smallest set of same class contain both parameters. 27 /// Returns the smallest set of same class contain both parameters.
25 fn common(&self, other : &Self) -> Self; 28 fn common(&self, other: &Self) -> Self;
26 29
27 /// Returns the greatest set of same class contaied by n both parameter sets. 30 /// Returns the greatest set of same class contaied by n both parameter sets.
28 fn intersect(&self, other : &Self) -> Option<Self>; 31 fn intersect(&self, other: &Self) -> Option<Self>;
29 } 32 }
30 33
31 impl<U, const N : usize> Set<Loc<U, N>> 34 impl<U, const N: usize> Set<Loc<N, U>> for Cube<N, U>
32 for Cube<U,N> 35 where
33 where U : Num + PartialOrd + Sized { 36 U: Num + PartialOrd + Sized,
34 fn contains<I : Instance<Loc<U, N>>>(&self, item : I) -> bool { 37 {
35 self.0.iter().zip(item.ref_instance().iter()).all(|(s, x)| s.contains(x)) 38 fn contains<I: Instance<Loc<N, U>>>(&self, item: I) -> bool {
39 self.0
40 .iter()
41 .zip(item.ref_instance().iter())
42 .all(|(s, x)| s.contains(x))
36 } 43 }
37 } 44 }
38 45
39 impl<U : Space> Set<U> for RangeFull { 46 impl<U: Space> Set<U> for RangeFull {
40 fn contains<I : Instance<U>>(&self, _item : I) -> bool { true } 47 fn contains<I: Instance<U>>(&self, _item: I) -> bool {
48 true
49 }
41 } 50 }
42 51
43 macro_rules! impl_ranges { 52 macro_rules! impl_ranges {
44 ($($range:ident),*) => { $( 53 ($($range:ident),*) => { $(
45 impl<U,Idx> Set<U> for $range<Idx> 54 impl<U,Idx> Set<U> for $range<Idx>
54 } 63 }
55 } 64 }
56 )* } 65 )* }
57 } 66 }
58 67
59 impl_ranges!(RangeFrom,Range,RangeInclusive,RangeTo,RangeToInclusive); 68 impl_ranges!(RangeFrom, Range, RangeInclusive, RangeTo, RangeToInclusive);
60 69
61 /// Halfspaces described by an orthogonal vector and an offset. 70 /// Halfspaces described by an orthogonal vector and an offset.
62 /// 71 ///
63 /// The halfspace is $H = \\{ t v + a \mid a^⊤ v = 0 \\}$, where $v$ is the orthogonal 72 /// The halfspace is $H = \\{ t v + a \mid a^⊤ v = 0 \\}$, where $v$ is the orthogonal
64 /// vector and $t$ the offset. 73 /// vector and $t$ the offset.
65 #[derive(Clone,Copy,Debug,Serialize,Eq,PartialEq)] 74 #[derive(Clone, Copy, Debug, Serialize, Eq, PartialEq)]
66 pub struct Halfspace<A, F> where A : Euclidean<F>, F : Float { 75 pub struct Halfspace<A, F>
67 pub orthogonal : A, 76 where
68 pub offset : F, 77 A: Euclidean<F>,
78 F: Float,
79 {
80 pub orthogonal: A,
81 pub offset: F,
69 } 82 }
70 83
71 impl<A,F> Halfspace<A,F> where A : Euclidean<F>, F : Float { 84 impl<A, F> Halfspace<A, F>
85 where
86 A: Euclidean<F>,
87 F: Float,
88 {
72 #[inline] 89 #[inline]
73 pub fn new(orthogonal : A, offset : F) -> Self { 90 pub fn new(orthogonal: A, offset: F) -> Self {
74 Halfspace{ orthogonal : orthogonal, offset : offset } 91 Halfspace {
92 orthogonal: orthogonal,
93 offset: offset,
94 }
75 } 95 }
76 } 96 }
77 97
78 /// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`. 98 /// Trait for generating a halfspace spanned by another set `Self` of elements of type `U`.
79 pub trait SpannedHalfspace<F> where F : Float { 99 pub trait SpannedHalfspace<F>
100 where
101 F: Float,
102 {
80 /// Type of the orthogonal vector describing the halfspace. 103 /// Type of the orthogonal vector describing the halfspace.
81 type A : Euclidean<F>; 104 type A: Euclidean<F>;
82 /// Returns the halfspace spanned by this set. 105 /// Returns the halfspace spanned by this set.
83 fn spanned_halfspace(&self) -> Halfspace<Self::A, F>; 106 fn spanned_halfspace(&self) -> Halfspace<Self::A, F>;
84 } 107 }
85 108
86 // TODO: Gram-Schmidt for higher N. 109 // TODO: Gram-Schmidt for higher N.
87 impl<F : Float> SpannedHalfspace<F> for [Loc<F, 1>; 2] { 110 impl<F: Float> SpannedHalfspace<F> for [Loc<1, F>; 2] {
88 type A = Loc<F, 1>; 111 type A = Loc<1, F>;
89 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> { 112 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
90 let (x0, x1) = (self[0], self[1]); 113 let (x0, x1) = (self[0], self[1]);
91 Halfspace::new(x1-x0, x0[0]) 114 Halfspace::new(x1 - x0, x0[0])
92 } 115 }
93 } 116 }
94 117
95 // TODO: Gram-Schmidt for higher N. 118 // TODO: Gram-Schmidt for higher N.
96 impl<F : Float> SpannedHalfspace<F> for [Loc<F, 2>; 2] { 119 impl<F: Float> SpannedHalfspace<F> for [Loc<2, F>; 2] {
97 type A = Loc<F, 2>; 120 type A = Loc<2, F>;
98 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> { 121 fn spanned_halfspace(&self) -> Halfspace<Self::A, F> {
99 let (x0, x1) = (&self[0], &self[1]); 122 let (x0, x1) = (&self[0], &self[1]);
100 let d = x1 - x0; 123 let d = x1 - x0;
101 let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency 124 let orthog = loc![d[1], -d[0]]; // We don't normalise for efficiency
102 let offset = x0.dot(&orthog); 125 let offset = x0.dot(&orthog);
103 Halfspace::new(orthog, offset) 126 Halfspace::new(orthog, offset)
104 } 127 }
105 } 128 }
106 129
107 impl<A,F> Set<A> for Halfspace<A,F> 130 impl<A, F> Set<A> for Halfspace<A, F>
108 where 131 where
109 A : Euclidean<F>, 132 A: Euclidean<F>,
110 F : Float, 133 F: Float,
111 { 134 {
112 #[inline] 135 #[inline]
113 fn contains<I : Instance<A>>(&self, item : I) -> bool { 136 fn contains<I: Instance<A>>(&self, item: I) -> bool {
114 self.orthogonal.dot(item) >= self.offset 137 self.orthogonal.dot(item) >= self.offset
115 } 138 }
116 } 139 }
117 140
118 /// Polygons defined by `N` `Halfspace`s. 141 /// Polygons defined by `N` `Halfspace`s.
119 #[derive(Clone,Copy,Debug,Eq,PartialEq)] 142 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
120 pub struct NPolygon<A, F, const N : usize>(pub [Halfspace<A,F>; N]) 143 pub struct NPolygon<A, const N: usize, F = f64>(pub [Halfspace<A, F>; N])
121 where A : Euclidean<F>, F : Float; 144 where
145 A: Euclidean<F>,
146 F: Float;
122 147
123 impl<A,F,const N : usize> Set<A> for NPolygon<A,F,N> 148 impl<A, F, const N: usize> Set<A> for NPolygon<A, N, F>
124 where 149 where
125 A : Euclidean<F>, 150 A: Euclidean<F>,
126 F : Float, 151 F: Float,
127 { 152 {
128 fn contains<I : Instance<A>>(&self, item : I) -> bool { 153 fn contains<I: Instance<A>>(&self, item: I) -> bool {
129 let r = item.ref_instance(); 154 let r = item.ref_instance();
130 self.0.iter().all(|halfspace| halfspace.contains(r)) 155 self.0.iter().all(|halfspace| halfspace.contains(r))
131 } 156 }
132 } 157 }

Mercurial Repository: alg_tools

mercurial