geo/algorithm/kernels/
mod.rs

1use num_traits::Zero;
2use std::cmp::Ordering;
3
4use crate::{coord, Coord, CoordNum};
5
6#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
7pub enum Orientation {
8    CounterClockwise,
9    Clockwise,
10    Collinear,
11}
12
13impl Orientation {
14    /// Helper to convert orientation-2d into an ordering.
15    #[inline]
16    pub(crate) fn as_ordering(&self) -> Ordering {
17        match self {
18            Orientation::CounterClockwise => Ordering::Less,
19            Orientation::Clockwise => Ordering::Greater,
20            Orientation::Collinear => Ordering::Equal,
21        }
22    }
23}
24
25/// Kernel trait to provide predicates to operate on
26/// different scalar types.
27pub trait Kernel<T: CoordNum> {
28    /// Gives the orientation of 3 2-dimensional points:
29    /// ccw, cw or collinear (None)
30    fn orient2d(p: Coord<T>, q: Coord<T>, r: Coord<T>) -> Orientation {
31        let res = (q.x - p.x) * (r.y - q.y) - (q.y - p.y) * (r.x - q.x);
32        if res > Zero::zero() {
33            Orientation::CounterClockwise
34        } else if res < Zero::zero() {
35            Orientation::Clockwise
36        } else {
37            Orientation::Collinear
38        }
39    }
40
41    fn square_euclidean_distance(p: Coord<T>, q: Coord<T>) -> T {
42        (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y)
43    }
44
45    /// Compute the sign of the dot product of `u` and `v` using
46    /// robust predicates. The output is `CounterClockwise` if
47    /// the sign is positive, `Clockwise` if negative, and
48    /// `Collinear` if zero.
49    fn dot_product_sign(u: Coord<T>, v: Coord<T>) -> Orientation {
50        let zero = Coord::zero();
51        let vdash = coord! {
52            x: T::zero() - v.y,
53            y: v.x,
54        };
55        Self::orient2d(zero, u, vdash)
56    }
57}
58
59/// Marker trait to assign Kernel for scalars
60pub trait HasKernel: CoordNum {
61    type Ker: Kernel<Self>;
62}
63
64// Helper macro to implement `HasKernel` on a a scalar type
65// `T` (first arg.) by assigning the second arg. It expects
66// the second arg. to be a type that takes one generic
67// parameter that is `T`.
68macro_rules! has_kernel {
69    ($t:ident, $k:ident) => {
70        impl $crate::HasKernel for $t {
71            type Ker = $k;
72        }
73    };
74}
75
76pub mod robust;
77pub use self::robust::RobustKernel;
78has_kernel!(f64, RobustKernel);
79has_kernel!(f32, RobustKernel);
80
81pub mod simple;
82pub use self::simple::SimpleKernel;
83
84has_kernel!(i64, SimpleKernel);
85has_kernel!(i32, SimpleKernel);
86has_kernel!(i16, SimpleKernel);
87has_kernel!(isize, SimpleKernel);
88
89#[cfg(has_i128)]
90has_kernel!(i128, SimpleKernel);
geo/algorithm/kernels/mod.rs

geo/algorithm/kernels/
mod.rs
