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}