equal
deleted
inserted
replaced
71 segment: Line, |
71 segment: Line, |
72 distance_divisor: u32, |
72 distance_divisor: u32, |
73 random_numbers: &mut I, |
73 random_numbers: &mut I, |
74 ) -> Option<Point> { |
74 ) -> Option<Point> { |
75 #[inline] |
75 #[inline] |
76 fn intersect(p: &Point, m: &Point, p1: &Point, p2: &Point) -> bool { |
76 fn intersect(p: Point, m: Point, p1: Point, p2: Point) -> bool { |
77 let t1 = (*m - *p1).cross(*p); |
77 let t1 = (m - p1).cross(p); |
78 let t2 = (*m - *p2).cross(*p); |
78 let t2 = (m - p2).cross(p); |
79 |
79 |
80 (t1 > 0) != (t2 > 0) |
80 (t1 > 0) != (t2 > 0) |
81 } |
81 } |
82 |
82 |
83 #[inline] |
83 #[inline] |
84 fn solve_intersection( |
84 fn solve_intersection( |
85 intersections_box: &Rect, |
85 intersections_box: &Rect, |
86 p: &Point, |
86 p: Point, |
87 m: &Point, |
87 m: Point, |
88 s: &Point, |
88 s: Point, |
89 e: &Point, |
89 e: Point, |
90 ) -> Option<(i32, u32)> { |
90 ) -> Option<(i32, u32)> { |
91 let f = *e - *s; |
91 let f = e - s; |
92 let aqpb = p.cross(f) as i64; |
92 let aqpb = p.cross(f) as i64; |
93 |
93 |
94 if aqpb != 0 { |
94 if aqpb != 0 { |
95 let mut iy = ((((s.x - m.x) as i64 * p.y as i64 + m.y as i64 * p.x as i64) |
95 let mut iy = ((((s.x - m.x) as i64 * p.y as i64 + m.y as i64 * p.x as i64) |
96 * f.y as i64 |
96 * f.y as i64 |
109 } else { |
109 } else { |
110 (iy - s.y) * f.x / f.y + s.x |
110 (iy - s.y) * f.x / f.y + s.x |
111 }; |
111 }; |
112 |
112 |
113 let intersection_point = Point::new(ix, iy); |
113 let intersection_point = Point::new(ix, iy); |
114 let diff_point = *m - intersection_point; |
114 let diff_point = m - intersection_point; |
115 let t = p.dot(diff_point); |
115 let t = p.dot(diff_point); |
116 if diff_point.max_norm() >= std::i16::MAX as i32 { |
116 if diff_point.max_norm() >= std::i16::MAX as i32 { |
117 Some((t, std::i32::MAX as u32)) |
117 Some((t, std::i32::MAX as u32)) |
118 } else { |
118 } else { |
119 let d = diff_point.integral_norm(); |
119 let d = diff_point.integral_norm(); |
186 } |
186 } |
187 |
187 |
188 // now go through all other segments |
188 // now go through all other segments |
189 for s in self.segments_iter() { |
189 for s in self.segments_iter() { |
190 if s != segment { |
190 if s != segment { |
191 if intersect(&p, &mid_point, &s.start, &s.end) { |
191 if intersect(p, mid_point, s.start, s.end) { |
192 if let Some((t, d)) = solve_intersection( |
192 if let Some((t, d)) = solve_intersection( |
193 &self.intersections_box, |
193 &self.intersections_box, |
194 &p, |
194 p, |
195 &mid_point, |
195 mid_point, |
196 &s.start, |
196 s.start, |
197 &s.end, |
197 s.end, |
198 ) { |
198 ) { |
199 if t > 0 { |
199 if t > 0 { |
200 dist_right = min(dist_right, d); |
200 dist_right = min(dist_right, d); |
201 } else { |
201 } else { |
202 dist_left = min(dist_left, d); |
202 dist_left = min(dist_left, d); |
205 } |
205 } |
206 } |
206 } |
207 } |
207 } |
208 |
208 |
209 // go through all points, including fill points |
209 // go through all points, including fill points |
210 for pi in self.iter() { |
210 for pi in self.iter().cloned() { |
211 if *pi != segment.start && *pi != segment.end { |
211 if pi != segment.start && pi != segment.end { |
212 if intersect(&p, &pi, &segment.start, &segment.end) { |
212 if intersect(p, pi, segment.start, segment.end) { |
213 // ray from segment.start |
213 // ray from segment.start |
214 if let Some((t, d)) = solve_intersection( |
214 if let Some((t, d)) = solve_intersection( |
215 &self.intersections_box, |
215 &self.intersections_box, |
216 &p, |
216 p, |
217 &mid_point, |
217 mid_point, |
218 &segment.start, |
218 segment.start, |
219 &pi, |
219 pi, |
220 ) { |
220 ) { |
221 if t > 0 { |
221 if t > 0 { |
222 dist_right = min(dist_right, d); |
222 dist_right = min(dist_right, d); |
223 } else { |
223 } else { |
224 dist_left = min(dist_left, d); |
224 dist_left = min(dist_left, d); |
226 } |
226 } |
227 |
227 |
228 // ray from segment.end |
228 // ray from segment.end |
229 if let Some((t, d)) = solve_intersection( |
229 if let Some((t, d)) = solve_intersection( |
230 &self.intersections_box, |
230 &self.intersections_box, |
231 &p, |
231 p, |
232 &mid_point, |
232 mid_point, |
233 &segment.end, |
233 segment.end, |
234 &pi, |
234 pi, |
235 ) { |
235 ) { |
236 if t > 0 { |
236 if t > 0 { |
237 dist_right = min(dist_right, d); |
237 dist_right = min(dist_right, d); |
238 } else { |
238 } else { |
239 dist_left = min(dist_left, d); |
239 dist_left = min(dist_left, d); |