base/geometry.rs

   1 // Copyright 2020-2021 Ian Jackson and contributors to Otter
   2 // SPDX-License-Identifier: AGPL-3.0-or-later
   3 // There is NO WARRANTY.
   4
   5 use crate::prelude::*;
   6
   7 use std::ops::{Add,Sub,Mul,Neg};
   8
   9 use num_traits::NumCast;
  10
  11 //---------- common types ----------
  12
  13 pub type Coord = i32;
  14
  15 #[derive(Clone,Copy,Serialize,Deserialize,Hash)]
  16 #[derive(Eq,PartialEq,Ord,PartialOrd)]
  17 #[serde(transparent)]
  18 pub struct PosC<T>{ pub coords: [T; 2] }
  19 pub type Pos = PosC<Coord>;
  20
  21 #[derive(Clone,Copy,Serialize,Deserialize,Hash)]
  22 #[derive(Eq,PartialEq,Ord,PartialOrd)]
  23 #[serde(transparent)]
  24 pub struct RectC<T>{ pub corners: [PosC<T>; 2] }
  25 pub type Rect = RectC<Coord>;
  26
  27 // ---------- CheckedArith ----------
  28
  29 #[derive(Error,Clone,Copy,Debug,Serialize,Deserialize)]
  30 #[error("error parsing Z coordinate")]
  31 pub struct CoordinateOverflow;
  32
  33 pub trait CheckedArith: Copy + Clone + Debug + 'static {
  34   fn checked_add(self, rhs: Self) -> Result<Self, CoordinateOverflow>;
  35   fn checked_sub(self, rhs: Self) -> Result<Self, CoordinateOverflow>;
  36   fn checked_neg(self)            -> Result<Self, CoordinateOverflow>;
  37 }
  38 pub trait CheckedArithMul<RHS: Copy + Clone + Debug + 'static>:
  39                                Copy + Clone + Debug + 'static {
  40   fn checked_mul(self, rhs: RHS) -> Result<Self, CoordinateOverflow>;
  41 }
  42
  43 macro_rules! checked_inherent { {$n:ident($($formal:tt)*) $($actual:tt)*} => {
  44   fn $n(self $($formal)*) -> Result<Self, CoordinateOverflow> {
  45     self.$n($($actual)*).ok_or(CoordinateOverflow)
  46   }
  47 } }
  48
  49 #[allow(clippy::only_used_in_recursion)] // FP nightly (1bfe40d11 2022-03-18
  50 impl CheckedArith for i32 {
  51   checked_inherent!{checked_add(, rhs: Self) rhs}
  52   checked_inherent!{checked_sub(, rhs: Self) rhs}
  53   checked_inherent!{checked_neg(           )    }
  54 }
  55 impl CheckedArithMul<i32> for i32 {
  56   checked_inherent!{checked_mul(, rhs: Self) rhs}
  57 }
  58 impl CheckedArithMul<f64> for i32 {
  59   fn checked_mul(self, rhs: f64) -> Result<Self, CoordinateOverflow> {
  60     let lhs: f64 = self.into();
  61     let out: f64 = lhs.checked_mul(rhs)?;
  62     let out: Self = NumCast::from(out).ok_or(CoordinateOverflow)?;
  63     Ok(out)
  64   }
  65 }
  66
  67 macro_rules! checked_float { {$n:ident($($formal:tt)*) $($modify:tt)*} => {
  68   fn $n(self $($formal)*) -> Result<Self, CoordinateOverflow> {
  69     let out = self $($modify)*;
  70     if out.is_finite() { Ok(out) } else { Err(CoordinateOverflow) }
  71   }
  72 } }
  73
  74 impl CheckedArith for f64 {
  75   checked_float!{checked_add(, rhs: Self)  + rhs }
  76   checked_float!{checked_sub(, rhs: Self)  - rhs }
  77   checked_float!{checked_neg()              .neg()}
  78 }
  79 impl CheckedArithMul<f64> for f64 {
  80   checked_float!{checked_mul(, rhs: Self)  * rhs }
  81 }
  82
  83 pub trait Mean { fn mean(&self, other: &Self) -> Self; }
  84
  85 impl Mean for i32 { fn mean(&self, other: &Self) -> Self {
  86   ((*self as i64 + *other as i64) / 2) as i32
  87 } }
  88 impl Mean for f64 { fn mean(&self, other: &Self) -> Self {
  89   self * 0.5 + other * 0.5
  90 } }
  91
  92 //---------- Pos ----------
  93
  94 pub trait PosPromote {
  95   fn promote(&self) -> PosC<f64>;
  96 }
  97 impl<T> PosPromote for PosC<T> where T: Into<f64> + Copy + Debug {
  98   fn promote(&self) -> PosC<f64> { self.map(|v| v.into()) }
  99 }
 100
 101 #[derive(Error,Debug,Copy,Clone,Serialize,Deserialize)]
 102 pub struct PosCFromIteratorError;
 103 display_as_debug!{PosCFromIteratorError}
 104
 105 #[macro_export]
 106 macro_rules! pos_zip_try_map { {
 107   $( $input:expr ),* => $closure:expr
 108 } => {
 109   PosC::try_from_iter_2(
 110     izip!($( $input .coords(), )*)
 111       .map($closure)
 112   )
 113 } }
 114 #[macro_export]
 115 macro_rules! pos_zip_map { {
 116   $( $input:expr ),* => $closure:expr
 117 } => {
 118   PosC::from_iter_2(
 119     izip!($( $input .coords(), )*)
 120       .map($closure)
 121   )
 122 } }
 123
 124 impl<T> PosC<T> {
 125   pub const fn new(x: T, y: T) -> Self { PosC{ coords: [x,y] } }
 126   pub fn both(v: T) -> Self where T: Copy { PosC::new(v,v) }
 127   pub fn zero() -> Self where T: num_traits::Zero + Copy {
 128     PosC::both(<T as num_traits::Zero>::zero())
 129   }
 130
 131   pub fn coords(self) -> impl ExactSizeIterator<Item=T> + FusedIterator {
 132     self.coords.into_iter()
 133   }
 134
 135   #[throws(CoordinateOverflow)]
 136   pub fn len2(self) -> f64 where PosC<T>: PosPromote {
 137     self.promote().coords()
 138       .try_fold(0., |b, c| {
 139         let c2 = c.checked_mul(c)?;
 140         b.checked_add(c2)
 141       })?
 142   }
 143
 144   #[throws(CoordinateOverflow)]
 145   pub fn len(self) -> f64 where PosC<T>: PosPromote {
 146     let d2 = self.len2()?;
 147     let d = d2.sqrt();
 148     if !d.is_finite() { throw!(CoordinateOverflow) }
 149     d
 150   }
 151 }
 152 impl<T> PosC<T> where T: Copy {
 153   pub fn x(self) -> T { self.coords[0] }
 154   pub fn y(self) -> T { self.coords[1] }
 155 }
 156
 157 #[allow(clippy::should_implement_trait)] // this one is fallible, which is a bit odd
 158 impl<T> PosC<T> {
 159   #[throws(PosCFromIteratorError)]
 160   pub fn from_iter<I: Iterator<Item=T>>(i: I) -> Self { PosC{ coords:
 161     i
 162       .collect::<ArrayVec<_,2>>()
 163       .into_inner()
 164       .map_err(|_| PosCFromIteratorError)?
 165   }}
 166 }
 167
 168 impl<T> PosC<T> where T: Debug {
 169   pub fn from_iter_2<I: Iterator<Item=T>>(i: I) -> Self { PosC{ coords:
 170     i
 171       .collect::<ArrayVec<_,2>>()
 172       .into_inner()
 173       .unwrap()
 174   }}
 175 }
 176
 177 impl<T> Debug for PosC<T> where T: Debug + Copy {
 178   #[throws(fmt::Error)]
 179   fn fmt(&self, f: &mut Formatter) {
 180     write!(f, "[{:?},{:?}]", self.x(), self.y())?;
 181   }
 182 }
 183
 184 impl<T:Debug> PosC<T> {
 185   /// Panics if the iterator doesn't yield exactly 2 elements
 186   #[throws(E)]
 187   pub fn try_from_iter_2<
 188     E: Debug,
 189     I: Iterator<Item=Result<T,E>>
 190   >(i: I) -> Self { PosC{ coords:
 191     i
 192       .collect::<Result<ArrayVec<_,2>,E>>()?
 193       .into_inner().unwrap()
 194   }}
 195 }
 196
 197 impl<T:CheckedArith> Add<PosC<T>> for PosC<T> {
 198   type Output = Result<Self, CoordinateOverflow>;
 199   #[throws(CoordinateOverflow)]
 200   fn add(self, rhs: PosC<T>) -> PosC<T> {
 201     pos_zip_try_map!( self, rhs => |(a,b)| a.checked_add(b) )?
 202   }
 203 }
 204
 205 impl<T:CheckedArith> Sub<PosC<T>> for PosC<T> {
 206   type Output = Result<Self, CoordinateOverflow>;
 207   #[throws(CoordinateOverflow)]
 208   fn sub(self, rhs: PosC<T>) -> PosC<T> {
 209     pos_zip_try_map!( self, rhs => |(a,b)| a.checked_sub(b) )?
 210   }
 211 }
 212
 213 impl<S:Copy+Debug+Clone+'static,T:CheckedArithMul<S>> Mul<S> for PosC<T> {
 214   type Output = Result<Self, CoordinateOverflow>;
 215   #[throws(CoordinateOverflow)]
 216   fn mul(self, rhs: S) -> PosC<T> {
 217     pos_zip_try_map!( self => |a| a.checked_mul(rhs) )?
 218   }
 219 }
 220
 221 impl<T:CheckedArith> Neg for PosC<T> {
 222   type Output = Result<Self, CoordinateOverflow>;
 223   #[throws(CoordinateOverflow)]
 224   fn neg(self) -> Self {
 225     pos_zip_try_map!( self => |a| a.checked_neg() )?
 226   }
 227 }
 228
 229 impl<T:Copy+Clone+Debug> PosC<T> {
 230   pub fn map<U:Copy+Clone+Debug, F: FnMut(T) -> U>(self, f: F) -> PosC<U> {
 231     pos_zip_map!( self => f )
 232   }
 233 }
 234
 235 impl<T:Copy+Clone+Debug> PosC<T> {
 236   pub fn try_map<E:Debug, U:Copy+Clone+Debug, F: FnMut(T) -> Result<U,E>>
 237     (self, f: F) -> Result<PosC<U>,E>
 238   {
 239     pos_zip_try_map!( self => f )
 240   }
 241 }
 242
 243 impl<T> Mean for PosC<T> where T: Mean + Debug + Copy {
 244   fn mean(&self, other: &Self) -> Self where T: Mean {
 245     pos_zip_map!( self, other => |(a,b)| a.mean(&b) )
 246   }
 247 }
 248
 249 // ---------- Rect ----------
 250
 251 impl<T> RectC<T> where T: Copy {
 252   pub fn tl(&self) -> PosC<T> { self.corners[0] }
 253   pub fn br(&self) -> PosC<T> { self.corners[1] }
 254 }
 255
 256 impl<T> Debug for RectC<T> where T: Debug + Copy {
 257   #[throws(fmt::Error)]
 258   fn fmt(&self, f: &mut Formatter) {
 259     write!(f, "Rect[{:?},{:?}]", self.tl(), self.br())?;
 260   }
 261 }
 262
 263 impl<T> RectC<T> {
 264   pub fn contains(&self, p: PosC<T>) -> bool where T: PartialOrd + Copy {
 265     (0..2).all(|i| {
 266       p.coords[i] >= self.tl().coords[i] &&
 267       p.coords[i] <= self.br().coords[i]
 268     })
 269   }
 270
 271   pub fn overlaps(&self, other: &RectC<T>) -> bool where T: PartialOrd + Copy {
 272     ! (0..2).any(|i| (
 273       other.br().coords[i] < self .tl().coords[i] ||
 274       self .br().coords[i] < other.tl().coords[i]
 275     ))
 276   }
 277
 278   pub fn empty() -> Self where T: num_traits::Zero + num_traits::One + Copy {
 279     RectC{ corners: [
 280       PosC::both( <T as num_traits::One >::one()  ),
 281       PosC::both( <T as num_traits::Zero>::zero() ),
 282     ]}
 283   }
 284 }
 285
 286 impl<T> RectC<T> where T: Mean + Debug + Copy {
 287   pub fn middle(&self) -> PosC<T> {
 288     Mean::mean(&self.tl(),
 289                &self.br())
 290   }
 291 }
 292
 293 impl<T> RectC<T> where T: CheckedArith + Debug + Copy {
 294   #[throws(CoordinateOverflow)]
 295   pub fn size(&self) -> PosC<T> {
 296     (self.br() - self.tl())?
 297   }
 298 }
 299
 300 #[test]
 301 fn empty_area() {
 302   let empty = Rect::empty();
 303   for x in -3..3 { for y in -3..3 {
 304     dbg!(empty,x,y);
 305     assert!(! empty.contains(PosC::new(x,y)));
 306   } }
 307 }
 308
 309 // ---------- Region ----------
 310
 311 #[derive(Clone,Debug,Serialize,Deserialize)]
 312 #[derive(Ord,PartialOrd,Eq,PartialEq)]
 313 pub enum RegionC<T:Copy> {
 314   Rect(RectC<T>),
 315 }
 316 pub type Region = RegionC<Coord>;
 317
 318 impl<T:Copy> RegionC<T> {
 319   pub fn contains(&self, pos: PosC<T>) -> bool where T: PartialOrd {
 320     use RegionC::*;
 321     match &self {
 322       Rect(a) => a.contains(pos),
 323     }
 324   }
 325
 326   pub fn overlaps(&self, other: &RegionC<T>) -> bool where T: PartialOrd {
 327     use RegionC::*;
 328     match (self, other) {
 329       (Rect(a), Rect(b)) => a.overlaps(b)
 330     }
 331   }
 332
 333   pub fn empty() -> Self where T: Copy + num_traits::Zero + num_traits::One {
 334     RegionC::Rect(RectC::empty())
 335   }
 336
 337 }