1  use crate::{num::CheapOrderedFloat, SegIdx};
  2  
  3  /// Describes the interaction between a line segment and a sweep-line.
  4  ///
  5  /// In exact math, a non-horizontal line segment can interact with a sweep-line
  6  /// in exactly one way: by intersecting it at a point. When dealing with inexact
  7  /// math, intersections and re-orderings between line segments might force
  8  /// our sweep-line algorithm to perturb the line segment. In that case, even
  9  /// a non-horizontal line segment might enter and leave the sweep-line at two
 10  /// different points.
 11  ///
 12  /// `OutputEvent` is ordered by the smallest horizontal coordinate where
 13  /// it intersects the sweep-line (i.e. [`OutputEvent::smaller_x`]).
 14  ///
 15  /// The two points, `x0` and `x1`, are in sweep-line order. This doesn't
 16  /// necessarily mean that `x0` is smaller than `x1`! Instead, it means that
 17  /// when traversing the segment in sweep-line order (i.e. in increasing `y`,
 18  /// and increasing `x` if the segment is horizontal) then it visits `x0`
 19  /// before `x1`.
 20  #[derive(Clone, Debug, PartialEq)]
 21  pub struct OutputEvent {
 22      /// The first horizontal coordinate on this sweep-line that we'd hit if
 23      /// we were traversing the segment in sweep-line orientation.
 24      pub x0: f64,
 25      /// Does this line segment extend "above" (i.e. smaller `y`) this sweep-line?
 26      ///
 27      /// If so, it will extend up from `x0`, because that's what the "sweep-line order"
 28      /// means.
 29      pub connected_above: bool,
 30      /// The last horizontal coordinate on this sweep-line that we'd hit if
 31      /// we were traversing the segment in sweep-line orientation.
 32      pub x1: f64,
 33      /// Does this line segment extend "below" (i.e. larger `y`) this sweep-line?
 34      ///
 35      /// If so, it will extend down from `x1`, because that's what the "sweep-line order"
 36      /// means.
 37      pub connected_below: bool,
 38      /// The segment that's interacting with the sweep line.
 39      pub seg_idx: SegIdx,
 40      /// The segment's index in the new sweep line (`None` for horizontal segments).
 41      pub sweep_idx: Option<usize>,
 42      /// The segment's index in the old sweep line (`None` for horizontal segments).
 43      pub old_sweep_idx: Option<usize>,
 44  }
 45  
 46  impl Eq for OutputEvent {}
 47  
 48  impl OutputEvent {
 49      /// The smallest `x` coordinate at which the line segment touches the sweep-line.
 50      pub fn smaller_x(&self) -> f64 {
 51          self.x0.min(self.x1)
 52      }
 53  
 54      /// The largest `x` coordinate at which the line segment touches the sweep-line.
 55      pub fn larger_x(&self) -> f64 {
 56          self.x0.max(self.x1)
 57      }
 58  
 59      pub(crate) fn new(
 60          seg_idx: SegIdx,
 61          x0: f64,
 62          connected_above: bool,
 63          x1: f64,
 64          connected_below: bool,
 65          sweep_idx: Option<usize>,
 66          old_sweep_idx: Option<usize>,
 67      ) -> Self {
 68          Self {
 69              x0,
 70              connected_above,
 71              x1,
 72              connected_below,
 73              seg_idx,
 74              sweep_idx,
 75              old_sweep_idx,
 76          }
 77      }
 78  
 79      /// Does the line segment extend up from the horizontal coordinate `x`?
 80      pub fn connected_above_at(&self, x: f64) -> bool {
 81          x == self.x0 && self.connected_above
 82      }
 83  
 84      /// Does the line segment extend down from the horizontal coordinate `x`?
 85      pub fn connected_below_at(&self, x: f64) -> bool {
 86          x == self.x1 && self.connected_below
 87      }
 88  }
 89  
 90  impl Ord for OutputEvent {
 91      fn cmp(&self, other: &Self) -> std::cmp::Ordering {
 92          CheapOrderedFloat::from(self.smaller_x())
 93              .cmp(&CheapOrderedFloat::from(other.smaller_x()))
 94              .then_with(|| {
 95                  CheapOrderedFloat::from(self.larger_x())
 96                      .cmp(&CheapOrderedFloat::from(other.larger_x()))
 97              })
 98      }
 99  }
100  
101  impl PartialOrd for OutputEvent {
102      fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
103          Some(self.cmp(other))
104      }
105  }