rgeometry/data/
line.rs

1use super::DirectedEdge;
2use super::LineSegmentView;
3use super::Point;
4use super::Vector;
5use crate::Intersects;
6use crate::{Orientation, PolygonScalar};
7
8///////////////////////////////////////////////////////////////////////////////
9// Line
10
11#[derive(Debug)]
12pub struct Line<'a, T, const N: usize = 2> {
13  pub origin: &'a Point<T, N>,
14  pub direction: Direction<'a, T, N>,
15}
16
17impl<T, const N: usize> Copy for Line<'_, T, N> {}
18impl<T, const N: usize> Clone for Line<'_, T, N> {
19  fn clone(&self) -> Self {
20    *self
21  }
22}
23
24impl<'a, T, const N: usize> Line<'a, T, N> {
25  pub fn new(origin: &'a Point<T, N>, direction: Direction<'a, T, N>) -> Line<'a, T, N> {
26    Line { origin, direction }
27  }
28
29  pub fn new_directed(origin: &'a Point<T, N>, vector: &'a Vector<T, N>) -> Line<'a, T, N> {
30    Line::new(origin, Direction::Vector(vector))
31  }
32
33  pub fn new_through(origin: &'a Point<T, N>, through: &'a Point<T, N>) -> Line<'a, T, N> {
34    Line::new(origin, Direction::Through(through))
35  }
36}
37
38impl<T: PolygonScalar> Line<'_, T> {
39  pub fn intersection_point(&self, other: &Self) -> Option<Point<T>> {
40    let [x1, y1] = self.origin.array.clone();
41    let [x2, y2] = match &self.direction {
42      Direction::Through(pt) => pt.array.clone(),
43      _ => unimplemented!(),
44    };
45    let [x3, y3] = other.origin.array.clone();
46    let [x4, y4] = match &other.direction {
47      Direction::Through(pt) => pt.array.clone(),
48      _ => unimplemented!(),
49    };
50    let denom: T = (x1.clone() - x2.clone()) * (y3.clone() - y4.clone())
51      - (y1.clone() - y2.clone()) * (x3.clone() - x4.clone());
52    if denom == T::from_constant(0) {
53      return None;
54    }
55    let part_a = x1.clone() * y2.clone() - y1.clone() * x2.clone();
56    let part_b = x3.clone() * y4.clone() - y3.clone() * x4.clone();
57    let x_num = part_a.clone() * (x3 - x4) - (x1 - x2) * part_b.clone();
58    let y_num = part_a * (y3 - y4) - (y1 - y2) * part_b;
59    Some(Point::new([x_num / denom.clone(), y_num / denom]))
60  }
61}
62
63///////////////////////////////////////////////////////////////////////////////
64// Line (owned)
65
66#[derive(Debug, Clone)]
67pub struct Line_<T, const N: usize> {
68  pub origin: Point<T, N>,
69  pub direction: Direction_<T, N>,
70}
71
72impl<'a, T, const N: usize> From<&'a Line_<T, N>> for Line<'a, T, N> {
73  fn from(line: &'a Line_<T, N>) -> Line<'a, T, N> {
74    Line {
75      origin: &line.origin,
76      direction: (&line.direction).into(),
77    }
78  }
79}
80
81// impl<'a, T: PolygonScalar> Line<'a, T, 2> {
82//   pub fn intersection_point(&self, other: &Self) -> Option<Point<T, 2>> {
83
84//   }
85// }
86
87///////////////////////////////////////////////////////////////////////////////
88// Direction
89
90#[derive(Debug)]
91pub enum Direction<'a, T, const N: usize> {
92  Vector(&'a Vector<T, N>),
93  Through(&'a Point<T, N>),
94}
95
96impl<T, const N: usize> Copy for Direction<'_, T, N> {}
97impl<T, const N: usize> Clone for Direction<'_, T, N> {
98  fn clone(&self) -> Self {
99    *self
100  }
101}
102
103///////////////////////////////////////////////////////////////////////////////
104// Direction_ (owned)
105
106#[derive(Debug, Clone)]
107pub enum Direction_<T, const N: usize> {
108  Vector(Vector<T, N>),
109  Through(Point<T, N>),
110}
111
112impl<'a, T, const N: usize> From<&'a Direction_<T, N>> for Direction<'a, T, N> {
113  fn from(owned: &'a Direction_<T, N>) -> Direction<'a, T, N> {
114    match owned {
115      Direction_::Vector(v) => Direction::Vector(v),
116      Direction_::Through(p) => Direction::Through(p),
117    }
118  }
119}
120
121///////////////////////////////////////////////////////////////////////////////
122// Line SoS
123
124#[derive(Debug, Clone)]
125pub struct LineSoS<'a, T, const N: usize = 2> {
126  line: Line<'a, T, N>,
127}
128
129impl<'a, T, const N: usize> From<LineSoS<'a, T, N>> for Line<'a, T, N> {
130  fn from(sos: LineSoS<'a, T, N>) -> Line<'a, T, N> {
131    sos.line
132  }
133}
134
135impl<'a, T, const N: usize> From<Line<'a, T, N>> for LineSoS<'a, T, N> {
136  fn from(line: Line<'a, T, N>) -> LineSoS<'a, T, N> {
137    LineSoS { line }
138  }
139}
140
141///////////////////////////////////////////////////////////////////////////////
142// Line SoS Owned
143
144#[derive(Debug, Clone)]
145pub struct LineSoS_<T, const N: usize = 2> {
146  line: Line_<T, N>,
147}
148
149impl<'a, T, const N: usize> From<&'a LineSoS_<T, N>> for LineSoS<'a, T, N> {
150  fn from(line: &'a LineSoS_<T, N>) -> LineSoS<'a, T, N> {
151    LineSoS {
152      line: Line::from(&line.line),
153    }
154  }
155}
156
157impl<T, const N: usize> From<Line_<T, N>> for LineSoS_<T, N> {
158  fn from(line: Line_<T, N>) -> LineSoS_<T, N> {
159    LineSoS_ { line }
160  }
161}
162
163///////////////////////////////////////////////////////////////////////////////
164// Line SoS intersection
165
166pub enum ILineLineSegmentSoS {
167  Crossing,
168}
169
170// Line / LineSegment intersection.
171// If the line is colinear with an endpoint in the linesegment, the endpoint
172// will be considered to be to the left of the line.
173impl<T> Intersects<LineSegmentView<'_, T>> for &LineSoS<'_, T>
174where
175  T: PolygonScalar,
176{
177  type Result = ILineLineSegmentSoS;
178  fn intersect(self, other: LineSegmentView<'_, T>) -> Option<Self::Result> {
179    let b1 = other.min.inner();
180    let b2 = other.max.inner();
181    let origin = &self.line.origin;
182    let l1_to_b1;
183    let l1_to_b2;
184    match &self.line.direction {
185      Direction::Vector(direction) => {
186        l1_to_b1 =
187          Point::orient_along_vector(origin, direction, b1).then(Orientation::CounterClockWise);
188        l1_to_b2 =
189          Point::orient_along_vector(origin, direction, b2).then(Orientation::CounterClockWise);
190      }
191      Direction::Through(through) => {
192        l1_to_b1 = Point::orient(origin, through, b1).then(Orientation::CounterClockWise);
193        l1_to_b2 = Point::orient(origin, through, b2).then(Orientation::CounterClockWise);
194      }
195    }
196    // If b1 and b2 are on opposite sides of the line then there's an intersection.
197    if l1_to_b1 == l1_to_b2.reverse() {
198      Some(ILineLineSegmentSoS::Crossing)
199    } else {
200      None
201    }
202  }
203}
204
205impl<T> Intersects<DirectedEdge<'_, T>> for &LineSoS<'_, T>
206where
207  T: PolygonScalar,
208{
209  type Result = ILineLineSegmentSoS;
210  fn intersect(self, other: DirectedEdge<'_, T>) -> Option<Self::Result> {
211    let line_segment: LineSegmentView<'_, T> = other.into();
212    self.intersect(line_segment)
213  }
214}
215
216///////////////////////////////////////////////////////////////////////////////
217// Half-Line SoS
218
219pub struct HalfLineSoS<'a, T, const N: usize = 2> {
220  line: Line<'a, T, N>,
221}
222
223impl<T, const N: usize> Copy for HalfLineSoS<'_, T, N> {}
224impl<T, const N: usize> Clone for HalfLineSoS<'_, T, N> {
225  fn clone(&self) -> Self {
226    *self
227  }
228}
229
230impl<'a, T, const N: usize> From<LineSoS<'a, T, N>> for HalfLineSoS<'a, T, N> {
231  fn from(sos: LineSoS<'a, T, N>) -> HalfLineSoS<'a, T, N> {
232    HalfLineSoS { line: sos.into() }
233  }
234}
235
236impl<'a, T, const N: usize> From<Line<'a, T, N>> for HalfLineSoS<'a, T, N> {
237  fn from(line: Line<'a, T, N>) -> HalfLineSoS<'a, T, N> {
238    HalfLineSoS { line }
239  }
240}
241
242impl<'a, T, const N: usize> From<HalfLineSoS<'a, T, N>> for LineSoS<'a, T, N> {
243  fn from(ray: HalfLineSoS<'a, T, N>) -> LineSoS<'a, T, N> {
244    ray.line.into()
245  }
246}
247
248impl<'a, T, const N: usize> From<HalfLineSoS<'a, T, N>> for Line<'a, T, N> {
249  fn from(ray: HalfLineSoS<'a, T, N>) -> Line<'a, T, N> {
250    ray.line
251  }
252}
253
254impl<'a, T, const N: usize> HalfLineSoS<'a, T, N> {
255  pub fn new(origin: &'a Point<T, N>, direction: Direction<'a, T, N>) -> HalfLineSoS<'a, T, N> {
256    Line::new(origin, direction).into()
257  }
258
259  pub fn new_directed(origin: &'a Point<T, N>, vector: &'a Vector<T, N>) -> HalfLineSoS<'a, T, N> {
260    Line::new_directed(origin, vector).into()
261  }
262
263  pub fn new_through(origin: &'a Point<T, N>, through: &'a Point<T, N>) -> HalfLineSoS<'a, T, N> {
264    Line::new_through(origin, through).into()
265  }
266}
267
268///////////////////////////////////////////////////////////////////////////////
269// Line SoS intersection
270
271#[derive(Debug, Eq, PartialEq)]
272pub enum IHalfLineLineSegmentSoS {
273  Crossing(Orientation),
274}
275
276// Line / LineSegment intersection.
277// If the line is colinear with an endpoint in the linesegment, the endpoint
278// will be considered to be to the left of the line.
279impl<T> Intersects<LineSegmentView<'_, T>> for &HalfLineSoS<'_, T>
280where
281  T: PolygonScalar,
282{
283  type Result = IHalfLineLineSegmentSoS;
284  fn intersect(self, other: LineSegmentView<'_, T>) -> Option<Self::Result> {
285    let b1 = other.min.inner();
286    let b2 = other.max.inner();
287
288    let origin = &self.line.origin;
289
290    let l1_to_b1 = Point::orient_along_direction(origin, self.line.direction, b1);
291    let l1_to_b2 = Point::orient_along_direction(origin, self.line.direction, b2);
292
293    use IHalfLineLineSegmentSoS::*;
294    use Orientation::*;
295    match (l1_to_b1, l1_to_b2) {
296      // l1 and l2 are parallel and therefore cannot cross.
297      (CoLinear, CoLinear) => None,
298      // b1 is colinear with l1 and there is a crossing if we lean in the direction of b2
299      (CoLinear, _) => {
300        let l2_to_a1 = Point::orient(b1, b2, origin);
301        if l1_to_b2 == l2_to_a1 {
302          Some(Crossing(l1_to_b2))
303        } else {
304          None
305        }
306      }
307      // b2 is colinear with l1 and there is a crossing if we lean in the direction of b1
308      (_, CoLinear) => {
309        let l2_to_a1 = Point::orient(b2, b1, origin);
310        if l1_to_b1 == l2_to_a1 {
311          Some(Crossing(l1_to_b1))
312        } else {
313          None
314        }
315      }
316      _ => {
317        if l1_to_b1 == l1_to_b2.reverse() {
318          // b1 and b2 are on opposite sides of the line.
319          // There is a crossing if l2 is on the origin side of l1.
320          let l2_to_a1 = Point::orient(b1, b2, origin);
321          if l1_to_b1 == l2_to_a1.reverse() {
322            Some(Crossing(CoLinear))
323          } else {
324            None
325          }
326        } else {
327          // b1 and b2 are on the same side of the line.
328          // There is definitely no intersection.
329          None
330        }
331      }
332    }
333  }
334}
335
336// impl<T> Intersects<&DirectedEdgeOwner<T, 2>> for &HalfLineSoS<T, 2>
337// where
338//   T: PolygonScalar,
339// {
340//   type Result = IHalfLineLineSegmentSoS;
341//   fn intersect(self, other: &DirectedEdgeOwner<T, 2>) -> Option<Self::Result> {
342//     let line: LineSegmentView<'_, T, 2> = other.into();
343//     self.intersect(line)
344//   }
345// }
346
347impl<T> Intersects<DirectedEdge<'_, T>> for &HalfLineSoS<'_, T>
348where
349  T: PolygonScalar,
350{
351  type Result = IHalfLineLineSegmentSoS;
352  fn intersect(self, other: DirectedEdge<'_, T>) -> Option<Self::Result> {
353    let line: LineSegmentView<'_, T> = other.into();
354    self.intersect(line)
355  }
356}
357
358#[cfg(test)]
359mod tests {
360  use super::*;
361  use crate::data::{LineSegment, Polygon};
362
363  use proptest::prelude::*;
364  use test_strategy::proptest;
365
366  #[test]
367  fn ray_intersect_unit_1() {
368    let line: LineSegment<i8> = LineSegment::from((-1, 127)..(-5, 48));
369    let direction: Vector<i8, 2> = Vector([1, 0]);
370    let origin = Point::new([79, 108]);
371    let ray = HalfLineSoS::new_directed(&origin, &direction);
372
373    assert_eq!(ray.intersect(line.as_ref()), None);
374  }
375
376  #[test]
377  fn ray_intersect_unit_2() {
378    let line: LineSegment<i8> = LineSegment::from((0, 0)..(-1, 127));
379    let direction: Vector<i8, 2> = Vector([1, 0]);
380    let origin = Point::new([79, 108]);
381    let ray = HalfLineSoS::new_directed(&origin, &direction);
382
383    assert_eq!(ray.intersect(line.as_ref()), None);
384  }
385
386  #[test]
387  fn ray_intersect_unit_3() {
388    let line1: LineSegment<i8> = LineSegment::from((0, 0)..(0, 1));
389    let line2: LineSegment<i8> = LineSegment::from((0, -1)..(0, 0));
390    let direction: Vector<i8, 2> = Vector([1, 0]);
391    let origin = Point::new([-1, 0]);
392    let ray = HalfLineSoS::new_directed(&origin, &direction);
393
394    assert!(ray.intersect(line1.as_ref()).is_some());
395    assert!(ray.intersect(line2.as_ref()).is_some());
396  }
397
398  #[test]
399  fn ray_intersect_unit_4() {
400    use crate::data::PointLocation;
401    let poly = Polygon::new(vec![
402      Point::new([0, -1]),
403      Point::new([0, 0]),
404      Point::new([0, 1]),
405      Point::new([-10, 1]),
406      Point::new([-10, -1]),
407    ])
408    .unwrap();
409
410    let origin = Point::new([-1, 0]);
411    assert_eq!(poly.locate(&origin), PointLocation::Inside);
412
413    let origin = Point::new([0, 0]);
414    assert_eq!(poly.locate(&origin), PointLocation::OnBoundary);
415
416    let origin = Point::new([1, 0]);
417    assert_eq!(poly.locate(&origin), PointLocation::Outside);
418  }
419
420  #[test]
421  fn ray_intersect_unit_5() {
422    let line: LineSegment<i8> = LineSegment::from((0, 0)..(0, 1));
423    let direction: Vector<i8, 2> = Vector([1, 0]);
424    let origin = Point::new([1, 0]);
425    let ray = HalfLineSoS::new_directed(&origin, &direction);
426
427    assert!(ray.intersect(line.as_ref()).is_none());
428  }
429
430  #[test]
431  fn ray_intersect_unit_6() {
432    let line: LineSegment<i8> = LineSegment::from((0, 0)..(0, 1));
433    let direction: Vector<i8, 2> = Vector([1, 0]);
434    let origin = Point::new([1, 0]);
435    let ray = HalfLineSoS::new_directed(&origin, &direction);
436
437    assert!(ray.intersect(line.as_ref()).is_none());
438  }
439
440  #[proptest]
441  fn raw_intersection_count_prop(poly: Polygon<i8>, line: LineSoS_<i8>) {
442    let line: LineSoS<'_, i8> = (&line).into();
443    let mut intersections = 0;
444    for edge in poly.iter_boundary_edges() {
445      if line.intersect(edge).is_some() {
446        intersections += 1;
447      }
448    }
449    prop_assert_eq!(intersections % 2, 0);
450  }
451}
rgeometry/data/line.rs

rgeometry/data/
line.rs
