tidy_tree/
geometry.rs

1use num::Float;
2use std::cmp::{max, min};
3
4pub type Coord = f64;
5
6#[derive(PartialEq, Debug)]
7pub struct Point {
8    pub x: Coord,
9    pub y: Coord,
10}
11
12#[derive(PartialEq, Eq, Debug)]
13pub enum Orientation {
14    ClockWise,
15    CounterClockWise,
16    Colinear,
17}
18
19impl Point {
20    pub fn orientation(p: &Point, q: &Point, r: &Point) -> Orientation {
21        let val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
22
23        if val.abs() < 1e-7 {
24            Orientation::Colinear
25        } else if val > 0. {
26            Orientation::ClockWise
27        } else {
28            Orientation::CounterClockWise
29        }
30    }
31}
32
33#[derive(PartialEq, Debug)]
34pub struct Line {
35    pub from: Point,
36    pub to: Point,
37}
38
39impl Line {
40    fn is_point_on_line_if_colinear(&self, point: &Point) -> bool {
41        let from = &self.from;
42        let to = &self.to;
43
44        point.x >= Float::min(from.x, to.x)
45            && point.x <= Float::max(from.x, to.x)
46            && point.y >= Float::min(from.y, to.y)
47            && point.y <= Float::max(from.y, to.y)
48    }
49
50    pub fn intersect(&self, other: &Self) -> bool {
51        let o1 = Point::orientation(&self.from, &self.to, &other.from);
52        let o2 = Point::orientation(&self.from, &self.to, &other.to);
53        let o3 = Point::orientation(&other.from, &other.to, &self.from);
54        let o4 = Point::orientation(&other.from, &other.to, &self.to);
55        if o1 != o2 && o3 != o4 {
56            return true;
57        }
58
59        if o1 == Orientation::Colinear && self.is_point_on_line_if_colinear(&other.from) {
60            return true;
61        }
62        if o2 == Orientation::Colinear && self.is_point_on_line_if_colinear(&other.to) {
63            return true;
64        }
65        if o3 == Orientation::Colinear && other.is_point_on_line_if_colinear(&self.from) {
66            return true;
67        }
68        if o4 == Orientation::Colinear && other.is_point_on_line_if_colinear(&self.to) {
69            return true;
70        }
71
72        false
73    }
74
75    pub fn connected_to(&self, other: &Self) -> bool {
76        self.from == other.from
77            || self.from == other.to
78            || self.to == other.from
79            || self.to == other.to
80    }
81}
82
83#[cfg(test)]
84mod test {
85    use super::*;
86    #[test]
87    fn orient() {
88        let a = Point { x: 0., y: 0. };
89        let b = Point { x: 1., y: 0. };
90        let c = Point { x: 0., y: 1. };
91        assert_eq!(
92            Point::orientation(&a, &b, &c),
93            Orientation::CounterClockWise
94        );
95        let a = Point { x: 0., y: 0. };
96        let b = Point { x: 0., y: 1. };
97        let c = Point { x: 1., y: 0. };
98        assert_eq!(Point::orientation(&a, &b, &c), Orientation::ClockWise);
99        let a = Point { x: 0., y: 0. };
100        let b = Point { x: 1., y: 1. };
101        let c = Point { x: 4., y: 4. };
102        assert_eq!(Point::orientation(&a, &b, &c), Orientation::Colinear);
103    }
104
105    #[test]
106    fn intersect() {
107        let a = Line {
108            from: Point { x: 0., y: 0. },
109            to: Point { x: 1., y: 0. },
110        };
111        let b = Line {
112            from: Point { x: 1., y: 1. },
113            to: Point { x: 1., y: -1. },
114        };
115        assert!(a.intersect(&b));
116
117        let a = Line {
118            from: Point { x: 0., y: 0. },
119            to: Point { x: 1., y: 0. },
120        };
121        let b = Line {
122            from: Point { x: 2., y: 1. },
123            to: Point { x: 1., y: -1. },
124        };
125        assert!(!a.intersect(&b));
126
127        let a = Line {
128            from: Point { x: 0., y: 0. },
129            to: Point { x: 1., y: 1. },
130        };
131        let b = Line {
132            from: Point { x: 0., y: 1. },
133            to: Point { x: 1., y: 0. },
134        };
135        assert!(a.intersect(&b));
136
137        let a = Line {
138            from: Point { x: 0., y: 0. },
139            to: Point { x: 1., y: 1. },
140        };
141        let b = Line {
142            from: Point { x: 1., y: 1. },
143            to: Point { x: 2., y: 2. },
144        };
145        assert!(a.intersect(&b));
146
147        let a = Line {
148            from: Point { x: 0., y: 0. },
149            to: Point { x: 1., y: 1. },
150        };
151        let b = Line {
152            from: Point { x: 2., y: 2. },
153            to: Point { x: 3., y: 3. },
154        };
155        assert!(!a.intersect(&b));
156    }
157}
tidy_tree/geometry.rs

tidy_tree/
geometry.rs
