src/sets.rs

Sat, 10 Dec 2022 16:23:58 +0200

author
Tuomo Valkonen <tuomov@iki.fi>
date
Sat, 10 Dec 2022 16:23:58 +0200
changeset 21
62bdbff9a288
parent 8
4e09b7829b51
permissions
-rw-r--r--

Add rust-version specification to Cargo.toml

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

mercurial