1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

use crate::{CoordNum, Coordinate};
use num_traits::Zero;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
pub enum Orientation {
    CounterClockwise,
    Clockwise,
    Collinear,
}

/// Kernel trait to provide predicates to operate on
/// different scalar types.
pub trait Kernel<T: CoordNum> {
    /// Gives the orientation of 3 2-dimensional points:
    /// ccw, cw or collinear (None)
    fn orient2d(p: Coordinate<T>, q: Coordinate<T>, r: Coordinate<T>) -> Orientation {
        let res = (q.x - p.x) * (r.y - q.y) - (q.y - p.y) * (r.x - q.x);
        if res > Zero::zero() {
            Orientation::CounterClockwise
        } else if res < Zero::zero() {
            Orientation::Clockwise
        } else {
            Orientation::Collinear
        }
    }

    fn square_euclidean_distance(p: Coordinate<T>, q: Coordinate<T>) -> T {
        (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y)
    }

    /// Compute the sign of the dot product of `u` and `v` using
    /// robust predicates. The output is `CounterClockwise` if
    /// the sign is positive, `Clockwise` if negative, and
    /// `Collinear` if zero.
    fn dot_product_sign(u: Coordinate<T>, v: Coordinate<T>) -> Orientation {
        let zero = Coordinate::zero();
        let vdash = Coordinate {
            x: T::zero() - v.y,
            y: v.x,
        };
        Self::orient2d(zero, u, vdash)
    }
}

/// Marker trait to assign Kernel for scalars
pub trait HasKernel: CoordNum {
    type Ker: Kernel<Self>;
}

// Helper macro to implement `HasKernel` on a a scalar type
// `T` (first arg.) by assigning the second arg. It expects
// the second arg. to be a type that takes one generic
// parameter that is `T`.
#[macro_use]
macro_rules! has_kernel {
    ($t:ident, $k:ident) => {
        impl $crate::algorithm::kernels::HasKernel for $t {
            type Ker = $k;
        }
    };
}

pub mod robust;
pub use self::robust::RobustKernel;
has_kernel!(f64, RobustKernel);
has_kernel!(f32, RobustKernel);

pub mod simple;
pub use self::simple::SimpleKernel;

has_kernel!(i64, SimpleKernel);
has_kernel!(i32, SimpleKernel);
has_kernel!(i16, SimpleKernel);
has_kernel!(isize, SimpleKernel);

#[cfg(has_i128)]
has_kernel!(i128, SimpleKernel);