rgeometry/data/
line_segment.rs

1use std::cmp::Eq;
2use std::cmp::Ord;
3use std::cmp::Ordering;
4use std::cmp::PartialEq;
5use std::ops::Range;
6use std::ops::RangeInclusive;
7
8use super::Point;
9
10use crate::data::point::PointSoS;
11use crate::Intersects;
12use crate::{Orientation, PolygonScalar, TotalOrd};
13use Orientation::*;
14
15///////////////////////////////////////////////////////////////////////////////
16// EndPoint
17
18#[derive(Debug, Clone, Copy, Eq, PartialEq)]
19pub enum EndPoint<T: TotalOrd> {
20  Exclusive(T),
21  Inclusive(T),
22}
23
24use EndPoint::*;
25
26impl<T: TotalOrd> EndPoint<T> {
27  pub fn inner(&self) -> &T {
28    match self {
29      Exclusive(t) => t,
30      Inclusive(t) => t,
31    }
32  }
33
34  pub fn take(self) -> T {
35    match self {
36      Exclusive(t) => t,
37      Inclusive(t) => t,
38    }
39  }
40
41  pub fn as_ref(&self) -> EndPoint<&T> {
42    match self {
43      Exclusive(t) => Exclusive(t),
44      Inclusive(t) => Inclusive(t),
45    }
46  }
47
48  pub fn is_exclusive(&self) -> bool {
49    match self {
50      Exclusive(_) => true,
51      Inclusive(_) => false,
52    }
53  }
54
55  pub fn is_inclusive(&self) -> bool {
56    !self.is_exclusive()
57  }
58
59  #[must_use]
60  pub fn leftmost(self, other: EndPoint<T>) -> EndPoint<T>
61  where
62    T: Ord,
63  {
64    match self.inner().cmp(other.inner()) {
65      Ordering::Equal => {
66        if self.is_exclusive() {
67          self
68        } else {
69          other
70        }
71      }
72      Ordering::Less => self,
73      Ordering::Greater => other,
74    }
75  }
76
77  #[must_use]
78  pub fn rightmost(self, other: EndPoint<T>) -> EndPoint<T>
79  where
80    T: Ord,
81  {
82    match self.inner().cmp(other.inner()) {
83      Ordering::Equal => {
84        if self.is_exclusive() || other.is_exclusive() {
85          Exclusive(self.take())
86        } else {
87          other
88        }
89      }
90      Ordering::Less => other,
91      Ordering::Greater => self,
92    }
93  }
94}
95
96fn inner_between<T: TotalOrd>(inner: &T, a: EndPoint<&T>, b: EndPoint<&T>) -> bool {
97  let left;
98  let right;
99  if a.inner().total_cmp(b.inner()).is_lt() {
100    left = a;
101    right = b;
102  } else {
103    left = b;
104    right = a;
105  }
106  let lhs = match left {
107    Exclusive(l) => l.total_cmp(inner).is_lt(),
108    Inclusive(l) => l.total_cmp(inner).is_le(),
109  };
110  let rhs = match right {
111    Exclusive(r) => inner.total_cmp(r).is_lt(),
112    Inclusive(r) => inner.total_cmp(r).is_le(),
113  };
114  lhs && rhs
115}
116
117///////////////////////////////////////////////////////////////////////////////
118// LineSegment
119
120#[derive(Debug, Clone, Copy)]
121pub struct LineSegment<T: TotalOrd, const N: usize = 2> {
122  pub min: EndPoint<Point<T, N>>,
123  pub max: EndPoint<Point<T, N>>,
124}
125
126impl<T: TotalOrd, const N: usize> LineSegment<T, N> {
127  pub fn new(a: EndPoint<Point<T, N>>, b: EndPoint<Point<T, N>>) -> LineSegment<T, N>
128  where
129    T: TotalOrd,
130  {
131    if a.inner() < b.inner() {
132      LineSegment { min: a, max: b }
133    } else {
134      LineSegment { min: b, max: a }
135    }
136  }
137
138  pub fn as_ref(&self) -> LineSegmentView<'_, T, N> {
139    LineSegmentView {
140      min: self.min.as_ref(),
141      max: self.max.as_ref(),
142    }
143  }
144}
145impl<T: TotalOrd> LineSegment<T> {
146  pub fn contains(&self, pt: &Point<T>) -> bool
147  where
148    T: PolygonScalar,
149  {
150    self.as_ref().contains(pt)
151  }
152}
153
154impl<T: TotalOrd, const N: usize> From<Range<Point<T, N>>> for LineSegment<T, N> {
155  fn from(range: Range<Point<T, N>>) -> LineSegment<T, N> {
156    LineSegment::new(
157      EndPoint::Inclusive(range.start),
158      EndPoint::Exclusive(range.end),
159    )
160  }
161}
162
163impl<T: TotalOrd> From<Range<(T, T)>> for LineSegment<T> {
164  fn from(range: Range<(T, T)>) -> LineSegment<T> {
165    LineSegment::new(
166      EndPoint::Inclusive(range.start.into()),
167      EndPoint::Exclusive(range.end.into()),
168    )
169  }
170}
171
172impl<T: TotalOrd, const N: usize> From<RangeInclusive<Point<T, N>>> for LineSegment<T, N> {
173  fn from(range: RangeInclusive<Point<T, N>>) -> LineSegment<T, N> {
174    let (start, end) = range.into_inner();
175    LineSegment::new(EndPoint::Inclusive(start), EndPoint::Inclusive(end))
176  }
177}
178
179///////////////////////////////////////////////////////////////////////////////
180// LineSegmentView
181
182#[derive(Debug, PartialEq, Eq)]
183pub struct LineSegmentView<'a, T: TotalOrd, const N: usize = 2> {
184  pub min: EndPoint<&'a Point<T, N>>,
185  pub max: EndPoint<&'a Point<T, N>>,
186}
187
188#[derive(Debug, PartialEq, Eq)]
189pub struct LineSegmentSoS<'a, T: TotalOrd, const N: usize> {
190  pub min: EndPoint<PointSoS<'a, T, N>>,
191  pub max: EndPoint<PointSoS<'a, T, N>>,
192}
193
194impl<T: TotalOrd, const N: usize> Clone for LineSegmentView<'_, T, N> {
195  fn clone(&self) -> Self {
196    *self
197  }
198}
199impl<T: TotalOrd, const N: usize> Copy for LineSegmentView<'_, T, N> {}
200
201impl<'a, T: TotalOrd, const N: usize> LineSegmentView<'a, T, N> {
202  pub fn new(
203    a: EndPoint<&'a Point<T, N>>,
204    b: EndPoint<&'a Point<T, N>>,
205  ) -> LineSegmentView<'a, T, N>
206  where
207    T: TotalOrd,
208  {
209    if a.inner() < b.inner() {
210      LineSegmentView { min: a, max: b }
211    } else {
212      LineSegmentView { min: b, max: a }
213    }
214  }
215}
216
217impl<T: TotalOrd> LineSegmentView<'_, T> {
218  pub fn contains(&self, pt: &Point<T>) -> bool
219  where
220    T: PolygonScalar,
221  {
222    Point::orient(self.min.inner(), self.max.inner(), pt).is_colinear()
223      && inner_between(pt, self.min, self.max)
224  }
225}
226
227impl<'a, T: TotalOrd, const N: usize> From<&'a Range<Point<T, N>>> for LineSegmentView<'a, T, N> {
228  fn from(range: &'a Range<Point<T, N>>) -> LineSegmentView<'a, T, N> {
229    LineSegmentView::new(
230      EndPoint::Inclusive(&range.start),
231      EndPoint::Exclusive(&range.end),
232    )
233  }
234}
235
236impl<'a, T: TotalOrd, const N: usize> From<Range<&'a Point<T, N>>> for LineSegmentView<'a, T, N> {
237  fn from(range: Range<&'a Point<T, N>>) -> LineSegmentView<'a, T, N> {
238    LineSegmentView::new(
239      EndPoint::Inclusive(range.start),
240      EndPoint::Exclusive(range.end),
241    )
242  }
243}
244
245impl<'a, T: TotalOrd, const N: usize> From<&'a RangeInclusive<Point<T, N>>>
246  for LineSegmentView<'a, T, N>
247{
248  fn from(range: &'a RangeInclusive<Point<T, N>>) -> LineSegmentView<'a, T, N> {
249    LineSegmentView::new(
250      EndPoint::Inclusive(range.start()),
251      EndPoint::Inclusive(range.end()),
252    )
253  }
254}
255
256impl<'a, T: TotalOrd, const N: usize> From<&'a LineSegment<T, N>> for LineSegmentView<'a, T, N> {
257  fn from(line: &'a LineSegment<T, N>) -> LineSegmentView<'a, T, N> {
258    line.as_ref()
259  }
260}
261
262///////////////////////////////////////////////////////////////////////////////
263// ILineSegment
264
265#[derive(Debug, Eq, PartialEq)]
266pub enum ILineSegment<'a, T: TotalOrd> {
267  Crossing,                        // Lines touch but are not parallel.
268  Overlap(LineSegmentView<'a, T>), // Lines touch and are parallel.
269}
270
271///////////////////////////////////////////////////////////////////////////////
272// Intersects
273
274impl<'a, T> Intersects for LineSegmentView<'a, T>
275where
276  T: PolygonScalar,
277{
278  type Result = ILineSegment<'a, T>;
279  fn intersect(self, other: LineSegmentView<'a, T>) -> Option<Self::Result> {
280    let a1 = self.min.inner();
281    let a2 = self.max.inner();
282    let b1 = other.min.inner();
283    let b2 = other.max.inner();
284    let l1_to_b1 = Point::orient(a1, a2, b1);
285    let l1_to_b2 = Point::orient(a1, a2, b2);
286    let l2_to_a1 = Point::orient(b1, b2, a1);
287    let l2_to_a2 = Point::orient(b1, b2, a2);
288    // dbg!(
289    //   a1,
290    //   a2,
291    //   b1,
292    //   b2,
293    //   l1_to_b1,
294    //   l1_to_b2,
295    //   l2_to_a1,
296    //   l2_to_a2,
297    //   inner_between(other.min.inner(), self.min.as_ref(), self.max.as_ref()),
298    //   inner_between(other.max.inner(), self.min.as_ref(), self.max.as_ref()),
299    //   inner_between(self.min.inner(), other.min.as_ref(), other.max.as_ref()),
300    //   inner_between(self.max.inner(), other.min.as_ref(), other.max.as_ref()),
301    // );
302    if l1_to_b1 == CoLinear && l1_to_b2 == CoLinear {
303      let c_min = self.min.rightmost(other.min);
304      let c_max = self.max.leftmost(other.max);
305      let order = c_min.inner().cmp(c_max.inner());
306      if order == Ordering::Less
307        || (order == Ordering::Equal && c_max.is_inclusive() && c_min.is_inclusive())
308      {
309        Some(ILineSegment::Overlap(LineSegmentView {
310          min: c_min,
311          max: c_max,
312        }))
313      } else {
314        None
315      }
316    } else if l1_to_b1 == CoLinear {
317      // dbg!(other.0 >= self.0, other.0 <= self.1, other.0.is_closed());
318      if other.min.is_inclusive()
319        && inner_between(other.min.inner(), self.min.as_ref(), self.max.as_ref())
320      {
321        Some(ILineSegment::Crossing)
322      } else {
323        None
324      }
325    } else if l1_to_b2 == CoLinear {
326      if other.max.is_inclusive()
327        && inner_between(other.max.inner(), self.min.as_ref(), self.max.as_ref())
328      {
329        Some(ILineSegment::Crossing)
330      } else {
331        None
332      }
333    } else if l2_to_a1 == CoLinear {
334      if self.min.is_inclusive()
335        && inner_between(self.min.inner(), other.min.as_ref(), other.max.as_ref())
336      {
337        Some(ILineSegment::Crossing)
338      } else {
339        None
340      }
341    } else if l2_to_a2 == CoLinear {
342      if self.max.is_inclusive()
343        && inner_between(self.max.inner(), other.min.as_ref(), other.max.as_ref())
344      {
345        Some(ILineSegment::Crossing)
346      } else {
347        None
348      }
349    } else if l1_to_b1 == l1_to_b2.reverse() && l2_to_a1 == l2_to_a2.reverse() {
350      Some(ILineSegment::Crossing)
351    } else {
352      None
353    }
354  }
355}
356
357impl<'a, T> Intersects for &'a LineSegment<T>
358where
359  T: PolygonScalar,
360{
361  type Result = ILineSegment<'a, T>;
362  fn intersect(self, other: &'a LineSegment<T>) -> Option<Self::Result> {
363    self.as_ref().intersect(other.as_ref())
364  }
365}
366
367impl<'a, T> Intersects for &'a Range<Point<T>>
368where
369  T: PolygonScalar,
370{
371  type Result = ILineSegment<'a, T>;
372  fn intersect(self, other: &'a Range<Point<T>>) -> Option<Self::Result> {
373    LineSegmentView::from(self).intersect(LineSegmentView::from(other))
374  }
375}
376
377impl<'a, T> Intersects for &'a RangeInclusive<Point<T>>
378where
379  T: PolygonScalar,
380{
381  type Result = ILineSegment<'a, T>;
382  fn intersect(self, other: &'a RangeInclusive<Point<T>>) -> Option<Self::Result> {
383    LineSegmentView::from(self).intersect(LineSegmentView::from(other))
384  }
385}
386
387///////////////////////////////////////////////////////////////////////////////
388// Tests
389
390#[cfg(test)]
391#[cfg(not(tarpaulin_include))]
392mod tests {
393  use super::*;
394  use crate::data::*;
395  use crate::Intersects;
396  use ILineSegment::*;
397
398  use test_strategy::proptest;
399
400  #[proptest]
401  fn flip_intersects_prop(pts: [i8; 8]) {
402    let [a, b, c, d, e, f, g, h] = pts;
403    let l1 = LineSegment::from((a, b)..(c, d));
404    let l2 = LineSegment::from((e, f)..(g, h));
405    assert_eq!(l1.intersect(&l2), l2.intersect(&l1));
406  }
407
408  //             P6
409  //
410  // P7      P5
411  //
412  // P4  P2
413  //
414  // P1  P3
415  //
416  static P1: Point<i32> = Point::new([0, 0]);
417  static P2: Point<i32> = Point::new([1, 1]);
418  static P3: Point<i32> = Point::new([1, 0]);
419  static P4: Point<i32> = Point::new([0, 1]);
420  static P5: Point<i32> = Point::new([2, 2]);
421  static P6: Point<i32> = Point::new([3, 3]);
422  static P7: Point<i32> = Point::new([0, 2]);
423
424  #[test]
425  fn line_crossing() {
426    assert_eq!((P1..P2).intersect(&(P3..P4)), Some(Crossing))
427  }
428
429  #[test]
430  fn line_not_crossing() {
431    assert_eq!((P1..P3).intersect(&(P2..P4)), None)
432  }
433
434  #[test]
435  fn endpoints_no_overlap() {
436    assert_eq!((P1..P2).intersect(&(P2..P3)), None)
437  }
438
439  #[test]
440  fn endpoints_overlap_1() {
441    assert_eq!((P2..P1).intersect(&(P2..P3)), Some(Crossing))
442  }
443
444  #[test]
445  fn endpoints_overlap_2() {
446    assert_eq!((P1..P2).intersect(&(P1..P3)), Some(Crossing))
447  }
448
449  #[test]
450  fn endpoints_overlap_3() {
451    assert_eq!(
452      (P1..=P2).intersect(&(P2..=P5)),
453      Some(Overlap(LineSegmentView::from(&(P2..=P2))))
454    )
455  }
456
457  #[test]
458  fn edges_overlap_1() {
459    assert_eq!(
460      (P1..P5).intersect(&(P2..P6)),
461      Some(Overlap(LineSegmentView::from(&(P2..P5))))
462    )
463  }
464
465  #[test]
466  fn edges_overlap_2() {
467    assert_eq!(
468      (P1..P6).intersect(&(P2..P6)),
469      Some(Overlap(LineSegmentView::from(&(P2..P6))))
470    )
471  }
472
473  #[test]
474  fn edges_overlap_3() {
475    assert_eq!(
476      (P6..P1).intersect(&(P6..P2)),
477      Some(Overlap(LineSegmentView::from(&(P6..P2))))
478    )
479  }
480
481  #[test]
482  fn edges_overlap_4() {
483    let l1 = LineSegment::new(Inclusive(P1), Exclusive(P5));
484    let l2 = LineSegment::new(Exclusive(P2), Inclusive(P6));
485    let l3 = LineSegment::new(Exclusive(P2), Exclusive(P5));
486    assert_eq!(l1.intersect(&l2), Some(Overlap(l3.as_ref())))
487  }
488
489  #[test]
490  fn edges_overlap_5() {
491    let l1 = LineSegment::new(Inclusive(P1), Inclusive(P5));
492    let l2 = LineSegment::new(Exclusive(P2), Inclusive(P6));
493    let l3 = LineSegment::new(Exclusive(P2), Inclusive(P5));
494    assert_eq!(l1.intersect(&l2), Some(Overlap(l3.as_ref())))
495  }
496
497  #[test]
498  fn edge_touch() {
499    assert_eq!((P1..P7).intersect(&(P4..P2)), Some(Crossing))
500  }
501
502  #[test]
503  fn edge_no_touch() {
504    assert_eq!((P1..P7).intersect(&(P2..P4)), None)
505  }
506
507  #[test]
508  fn subset_1() {
509    let l1 = LineSegment::new(Inclusive(P1), Inclusive(P2));
510    let l2 = LineSegment::new(Exclusive(P1), Exclusive(P2));
511    assert_eq!(l1.intersect(&l2), Some(Overlap(l2.as_ref())))
512  }
513
514  #[test]
515  fn subset_2() {
516    let l1 = LineSegment::new(Inclusive(P1), Exclusive(P2));
517    let l2 = LineSegment::new(Exclusive(P1), Inclusive(P2));
518    let l3 = LineSegment::new(Exclusive(P1), Exclusive(P2));
519    assert_eq!(l1.intersect(&l2), Some(Overlap(l3.as_ref())))
520  }
521
522  #[test]
523  fn unit_1() {
524    let a1 = Point::new([1, 0]);
525    let a2 = Point::new([1, 1]);
526    let b1 = Point::new([0, 1]);
527    let b2 = Point::new([2, 3]);
528    let l1 = LineSegment::from(a1..a2);
529    let l2 = LineSegment::from(b1..b2);
530    assert_eq!(l1.intersect(&l2), None)
531  }
532
533  #[test]
534  fn unit_2() {
535    let a1 = Point::new([1, 0]);
536    let a2 = Point::new([1, 1]);
537    let b1 = Point::new([0, 0]);
538    let b2 = Point::new([2, 3]);
539    let l1 = LineSegment::from(b2..b1);
540    let l2 = LineSegment::from(a1..a2);
541    assert_eq!(l1.intersect(&l2), None)
542  }
543
544  #[test]
545  fn unit_3() {
546    let l1 = LineSegment::from((0, 0)..(1, 0));
547    let l2 = LineSegment::from((1, 0)..(2, 0));
548    assert_eq!(l1.intersect(&l2), None)
549  }
550
551  #[test]
552  fn unit_4() {
553    let l1 = &LineSegment::from((0, 0)..(1, 0));
554    let l2 = &LineSegment::from((1, 0)..(2, 0));
555    assert_eq!(l2.intersect(l1), None);
556    assert_eq!(l1.intersect(l2), None);
557  }
558
559  #[test]
560  fn unit_5() {
561    let l1 = LineSegment::new(Inclusive((0, 0).into()), Inclusive((1, 0).into()));
562    let l2 = LineSegment::new(Inclusive((1, 0).into()), Inclusive((2, 0).into()));
563    let l3 = LineSegment::new(Inclusive((1, 0).into()), Inclusive((1, 0).into()));
564    assert_eq!(l2.intersect(&l1), Some(Overlap(l3.as_ref())))
565  }
566
567  #[test]
568  fn unit_6() {
569    let l1 = LineSegment::from((4, 0)..(3, 0));
570    let l2 = LineSegment::from((3, 0)..(1, 0));
571    assert_eq!(l1.intersect(&l2), None)
572  }
573
574  #[test]
575  fn unit_7() {
576    let l1 = LineSegment::from((0, 0)..(0, 1));
577    let l2 = LineSegment::from((1, 2)..(2, 1));
578    assert_eq!(l1.intersect(&l2), None)
579  }
580
581  #[test]
582  fn unit_8() {
583    let l1 = LineSegment::from((-106, 0)..(54, -128));
584    let l2 = LineSegment::from((-71, -28)..(31, -8));
585    assert_eq!(l1.intersect(&l2), l2.intersect(&l1));
586  }
587}
rgeometry/data/line_segment.rs

rgeometry/data/
line_segment.rs
