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

#[derive(Debug, Copy, Clone, Default, PartialEq)]
pub struct Point {
    pub x: isize,
    pub y: isize,
}

impl Point {
    pub fn new(x: isize, y: isize) -> Point {
        Point { x, y }
    }

    pub fn split(self) -> (isize, isize) {
        (self.x, self.y)
    }
}

pub struct Line {
    pub a: Point,
    pub b: Point,
}

#[derive(Debug, Copy, Clone, Default, PartialEq)]
pub struct Rect(pub [Point; 4]);

impl Line {
    /// Returns intersect point of two lines
    pub fn intersect(&self, other: &Line) -> Option<Point> {
        let p = self;
        let q = other;

        /* (a, b) is perpendicular to line p */
        let a = -(p.b.y - p.a.y);
        let b = p.b.x - p.a.x;

        /* (c, d) is perpendicular to line q */
        let c = -(q.b.y - q.a.y);
        let d = q.b.x - q.a.x;

        /* e and f are dot products of the respective vectors with p and q */
        let e = a * p.b.x + b * p.b.y;
        let f = c * q.b.x + d * q.b.y;

        /* Now we need to solve:
         *     [a b] [rx]   [e]
         *     [c d] [ry] = [f]
         *
         * We do this by inverting the matrix and applying it to (e, f):
         *       [ d -b] [e]   [rx]
         * 1/det [-c  a] [f] = [ry]
         */
        let det = (a * d) - (b * c);

        match det {
            0 => None,

            det => Some(Point {
                x: (d * e - b * f) / det,
                y: (-c * e + a * f) / det,
            }),
        }
    }
}