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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

//! Line segments

use std::marker::PhantomData;

use cgmath::{BaseFloat, BaseNum};
use cgmath::{Point2, Point3};
use cgmath::{Vector2, Vector3};
use cgmath::prelude::*;

use Ray2;
use prelude::*;

/// A generic directed line segment from `origin` to `dest`.
#[derive(Copy, Clone, PartialEq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Line<S, V, P> {
    /// Origin of the line
    pub origin: P,
    /// Endpoint of the line
    pub dest: P,
    phantom_s: PhantomData<S>,
    phantom_v: PhantomData<V>,
}

impl<S: BaseNum, V: VectorSpace<Scalar = S>, P: EuclideanSpace<Scalar = S, Diff = V>>
    Line<S, V, P>
{
    /// Create a new directed line segment from `origin` to `dest`.
    pub fn new(origin: P, dest: P) -> Line<S, V, P> {
        Line {
            origin,
            dest,
            phantom_v: PhantomData,
            phantom_s: PhantomData,
        }
    }
}

/// 2D directed line segment
pub type Line2<S> = Line<S, Vector2<S>, Point2<S>>;

/// 3D directed line segment
pub type Line3<S> = Line<S, Vector3<S>, Point3<S>>;

impl<S: BaseFloat> Discrete<Ray2<S>> for Line2<S> {
    fn intersects(&self, ray: &Ray2<S>) -> bool {
        ray.intersection(self).is_some()
    }
}

impl<S: BaseFloat> Continuous<Ray2<S>> for Line2<S> {
    type Result = Point2<S>;

    fn intersection(&self, ray: &Ray2<S>) -> Option<Self::Result> {
        ray.intersection(self)
    }
}

/// Determines if an intersection between a ray and a line segment is found.
impl<S: BaseFloat> Continuous<Line2<S>> for Ray2<S> {
    type Result = Point2<S>;
    fn intersection(&self, line: &Line2<S>) -> Option<Point2<S>> {
        let ray = self;

        let p = ray.origin;
        let q = line.origin;
        let r = ray.direction;
        let s = Vector2::new(line.dest.x - line.origin.x, line.dest.y - line.origin.y);

        let cross_1 = r.perp_dot(s);
        let qmp = Vector2::new(q.x - p.x, q.y - p.y);
        let cross_2 = qmp.perp_dot(r);

        if cross_1 == S::zero() {
            if cross_2 != S::zero() {
                // parallel
                return None;
            }

            // collinear
            let q2mp = Vector2::new(line.dest.x - p.x, line.dest.y - p.y);
            let dot_1 = qmp.dot(r);
            let dot_2 = q2mp.dot(r);
            if (dot_1 <= S::zero() && dot_2 >= S::zero())
                || (dot_1 >= S::zero() && dot_2 <= S::zero())
            {
                return Some(p);
            } else if dot_1 >= S::zero() && dot_2 >= S::zero() {
                if dot_1 <= dot_2 {
                    return Some(q);
                } else {
                    return Some(line.dest);
                }
            }

            // no overlap exists
            return None;
        }

        let t = qmp.perp_dot(s) / cross_1;
        let u = cross_2 / cross_1;

        if S::zero() <= t && u >= S::zero() && u <= S::one() {
            return Some(Point2::new(p.x + t * r.x, p.y + t * r.y));
        }

        None
    }
}