1  use std::iter::Peekable;
  2  
  3  use kurbo::BezPath;
  4  
  5  use crate::{
  6      geom::{monotonic_pieces, Point, Segment},
  7      num::CheapOrderedFloat,
  8  };
  9  
 10  /// An index into our segment arena.
 11  ///
 12  /// Throughout this library, we assign identities to segments, so that we may
 13  /// consider segments as different even if they have the same start- and end-points.
 14  ///
 15  /// This index is used to identify a segment, whose data can be retrieved by looking
 16  /// it up in [`Segments`]. (Of course, this index-as-identifier breaks down if there are
 17  /// multiple `Segments` in flight. Just be careful not to mix them up.)
 18  #[cfg_attr(test, derive(serde::Serialize))]
 19  #[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
 20  pub struct SegIdx(pub(crate) usize);
 21  
 22  /// A vector indexed by `SegIdx`.
 23  #[cfg_attr(test, derive(serde::Serialize))]
 24  #[derive(Clone, Hash, PartialEq, Eq)]
 25  #[cfg_attr(test, serde(transparent))]
 26  pub struct SegVec<T> {
 27      inner: Vec<T>,
 28  }
 29  
 30  impl_typed_vec!(SegVec, SegIdx, "s");
 31  
 32  /// An arena of segments, each of which is a cubic Bézier.
 33  ///
 34  /// Segments are indexed by [`SegIdx`] and can be retrieved by indexing (i.e. with square brackets).
 35  #[derive(Clone, Default)]
 36  pub struct Segments {
 37      segs: SegVec<Segment>,
 38      contour_prev: SegVec<Option<SegIdx>>,
 39      contour_next: SegVec<Option<SegIdx>>,
 40      /// For each segment, stores true if the sweep-line order (small y to big y)
 41      /// is the same as the orientation in its original contour.
 42      orientation: SegVec<bool>,
 43      /// For each segment, stores its parameter range in the original input
 44      /// segment (which may have been split into monotonic sub-segments). Keeping
 45      /// track of where the splits happened allows us to potentially merge things
 46      /// back at the end.
 47      pub(crate) split_from_predecessor: SegVec<(f64, f64)>,
 48      /// The original input segments, for reconstructing/merging. (TODO: this
 49      /// representation is wasteful, since we only need it for segments that
 50      /// got split.)
 51      pub(crate) input_segs: SegVec<kurbo::PathSeg>,
 52  
 53      /// All the entrance heights, of segments, ordered by height.
 54      /// This includes horizontal segments.
 55      enter: Vec<(f64, SegIdx)>,
 56      /// All the exit heights of segments, ordered by height.
 57      /// This does not include horizontal segments.
 58      exit: Vec<(f64, SegIdx)>,
 59  }
 60  
 61  /// Certain operations expect closed paths, and return this as an error when a path is not closed.
 62  #[derive(Clone, Copy, Debug, PartialEq)]
 63  pub struct NonClosedPath {
 64      /// The point at the start of the non-closed path (always generated by a [`kurbo::PathEl::MoveTo`]).
 65      pub start_point: kurbo::Point,
 66      /// The point at the end of the non-closed path.
 67      pub end_point: kurbo::Point,
 68  }
 69  
 70  impl std::fmt::Display for NonClosedPath {
 71      fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 72          write!(
 73              f,
 74              "non-closed path starting at {} and ending at {}",
 75              self.start_point, self.end_point,
 76          )
 77      }
 78  }
 79  
 80  impl std::error::Error for NonClosedPath {}
 81  
 82  struct SegmentEntryFormatter<'a> {
 83      idx: SegIdx,
 84      seg: &'a Segment,
 85      prev: Option<SegIdx>,
 86      next: Option<SegIdx>,
 87      oriented: bool,
 88  }
 89  
 90  impl std::fmt::Debug for SegmentEntryFormatter<'_> {
 91      fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 92          let seg_idx = self.idx;
 93          let seg = self.seg;
 94          let prefix = if self.oriented {
 95              self.prev.map(|i| format!("{i:?} -> ")).unwrap_or_default()
 96          } else {
 97              self.next.map(|i| format!("{i:?} <- ")).unwrap_or_default()
 98          };
 99          let suffix = if self.oriented {
100              self.next.map(|i| format!(" -> {i:?}")).unwrap_or_default()
101          } else {
102              self.prev.map(|i| format!(" <- {i:?}")).unwrap_or_default()
103          };
104          write!(f, "{seg_idx:?}: {prefix}{seg:?}{suffix}")
105      }
106  }
107  
108  impl std::fmt::Debug for Segments {
109      fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
110          let mut list = f.debug_list();
111          for (idx, seg) in self.segs.iter() {
112              list.entry(&SegmentEntryFormatter {
113                  idx,
114                  seg,
115                  prev: self.contour_prev[idx],
116                  next: self.contour_next[idx],
117                  oriented: self.orientation[idx],
118              });
119          }
120          list.finish()
121      }
122  }
123  
124  fn cyclic_pairs<T>(xs: &[T]) -> impl Iterator<Item = (&T, &T)> {
125      pairs(xs).chain(xs.last().zip(xs.first()))
126  }
127  
128  fn pairs<T>(xs: &[T]) -> impl Iterator<Item = (&T, &T)> {
129      xs.windows(2).map(|pair| (&pair[0], &pair[1]))
130  }
131  
132  struct SubpathIter<'a, I: Iterator> {
133      inner: &'a mut Peekable<I>,
134      started: bool,
135  }
136  
137  impl<I> Iterator for SubpathIter<'_, I>
138  where
139      I: Iterator<Item = kurbo::PathEl>,
140  {
141      type Item = kurbo::PathEl;
142  
143      fn next(&mut self) -> Option<Self::Item> {
144          let ret = self.inner.peek()?;
145          if matches!(ret, kurbo::PathEl::MoveTo(_)) && self.started {
146              None
147          } else {
148              self.started = true;
149              self.inner.next()
150          }
151      }
152  }
153  
154  struct Subpaths<I: Iterator> {
155      inner: Peekable<I>,
156  }
157  
158  impl<I> Subpaths<I>
159  where
160      I: Iterator<Item = kurbo::PathEl>,
161  {
162      fn next(&mut self) -> Option<SubpathIter<'_, I>> {
163          if self.inner.peek().is_none() {
164              None
165          } else {
166              Some(SubpathIter {
167                  inner: &mut self.inner,
168                  started: false,
169              })
170          }
171      }
172  }
173  
174  impl Segments {
175      /// The number of segments in this arena.
176      #[allow(clippy::len_without_is_empty)]
177      pub fn len(&self) -> usize {
178          self.segs.len()
179      }
180  
181      /// Iterate over all indices that can be used to index into this arena.
182      pub fn indices(&self) -> impl Iterator<Item = SegIdx> {
183          (0..self.segs.len()).map(SegIdx)
184      }
185  
186      /// Iterate over all segments in this arena.
187      pub fn segments(&self) -> impl Iterator<Item = &Segment> {
188          self.segs.iter().map(|(_, s)| s)
189      }
190  
191      /// Returns the starting point of the segment at `idx`, relative to the segment's original orientation.
192      ///
193      /// The segment itself is stored in sweep-line order (i.e. its starting
194      /// point has the smaller y coordinate) regardless of the original
195      /// orientation of the segment. Use this method to retrieve the segment's
196      /// original start point.
197      pub fn oriented_start(&self, idx: SegIdx) -> Point {
198          if self.orientation[idx] {
199              self[idx].start()
200          } else {
201              self[idx].end()
202          }
203      }
204  
205      /// Returns the ending point of the segment at `idx`, relative to the segment's original orientation.
206      ///
207      /// The segment itself is stored in sweep-line order (i.e. its starting
208      /// point has the smaller y coordinate) regardless of the original
209      /// orientation of the segment. Use this method to retrieve the segment's
210      /// original end point.
211      pub fn oriented_end(&self, idx: SegIdx) -> Point {
212          if self.orientation[idx] {
213              self[idx].end()
214          } else {
215              self[idx].start()
216          }
217      }
218  
219      /// Returns the index of the segment following `idx`.
220      ///
221      /// If `idx` is part of a non-closed path and it is the last segment,
222      /// this returns `None`. If `idx` is part of a closed path, this will
223      /// always return `Some`, and you might need to be careful to avoid looping
224      /// infinitely.
225      pub fn contour_next(&self, idx: SegIdx) -> Option<SegIdx> {
226          self.contour_next[idx]
227      }
228  
229      /// Returns the index of the segment preceding `idx`.
230      ///
231      /// If `idx` is part of a non-closed path and it is the first segment,
232      /// this returns `None`. If `idx` is part of a closed path, this will
233      /// always return `Some`, and you might need to be careful to avoid looping
234      /// infinitely.
235      pub fn contour_prev(&self, idx: SegIdx) -> Option<SegIdx> {
236          self.contour_prev[idx]
237      }
238  
239      /// Does the sweep-line orientation of `idx` agree with its original orientation?
240      pub fn positively_oriented(&self, idx: SegIdx) -> bool {
241          self.orientation[idx]
242      }
243  
244      /// Add a (non-closed) polyline to this arena.
245      pub fn add_points<P: Into<Point>>(&mut self, ps: impl IntoIterator<Item = P>) {
246          let old_len = self.segs.len();
247  
248          let ps: Vec<_> = ps.into_iter().map(|p| p.into()).collect();
249          if ps.len() <= 1 {
250              return;
251          }
252  
253          for (p, q) in pairs(&ps) {
254              let (a, b, orient) = if p < q { (p, q, true) } else { (q, p, false) };
255              self.segs.push(Segment::straight(*a, *b));
256              self.orientation.push(orient);
257              self.split_from_predecessor.push((0.0, 1.0));
258              self.input_segs
259                  .push(kurbo::PathSeg::Line((p.to_kurbo(), q.to_kurbo()).into()));
260              self.contour_prev
261                  .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
262              self.contour_next.push(Some(SegIdx(self.segs.len())));
263          }
264  
265          if old_len < self.segs.len() {
266              self.contour_prev[SegIdx(old_len)] = None;
267              // unwrap: contour_next has the same length as `segs`, which is
268              // non-empty because we checked its length
269              *self.contour_next.inner.last_mut().unwrap() = None;
270          }
271  
272          self.update_enter_exit(old_len);
273      }
274  
275      /// Add a collection of closed polylines to this arena.
276      ///
277      /// This can be much faster than calling `add_cycles` repeatedly.
278      pub fn add_closed_polylines<P: Into<Point>>(
279          &mut self,
280          ps: impl IntoIterator<Item = impl IntoIterator<Item = P>>,
281      ) {
282          let old_len = self.segs.len();
283          for p in ps {
284              self.add_polyline_without_updating_enter_exit(p);
285          }
286          self.update_enter_exit(old_len);
287      }
288  
289      /// Add a closed polyline to this arena.
290      pub fn add_closed_polyline<P: Into<Point>>(&mut self, ps: impl IntoIterator<Item = P>) {
291          let old_len = self.segs.len();
292          self.add_polyline_without_updating_enter_exit(ps);
293          self.update_enter_exit(old_len);
294      }
295  
296      /// Add a Bézier path to this arena.
297      ///
298      /// The path can contain multiple subpaths, and each of them must be closed.
299      pub fn add_bez_path(&mut self, p: &BezPath) -> Result<(), NonClosedPath> {
300          let old_len = self.segs.len();
301          self.add_path_without_updating_enter_exit(p, true)?;
302          self.update_enter_exit(old_len);
303          Ok(())
304      }
305  
306      /// Add a Bézier path to this arena.
307      ///
308      /// The path can contain multiple subpaths, and each of them may or may not be closed.
309      pub fn add_non_closed_bez_path(&mut self, p: &BezPath) -> Result<(), NonClosedPath> {
310          let old_len = self.segs.len();
311          self.add_path_without_updating_enter_exit(p, false)?;
312          self.update_enter_exit(old_len);
313          Ok(())
314      }
315  
316      pub(crate) fn add_path_without_updating_enter_exit(
317          &mut self,
318          p: &BezPath,
319          must_be_closed: bool,
320      ) -> Result<(), NonClosedPath> {
321          let mut subpaths = Subpaths {
322              inner: p.iter().peekable(),
323          };
324          while let Some(subpath) = subpaths.next() {
325              let old_len = self.segs.len();
326              for seg in kurbo::segments(subpath) {
327                  match seg {
328                      kurbo::PathSeg::Line(ell) => {
329                          let p0: Point = ell.p0.into();
330                          let p1: Point = ell.p1.into();
331                          let (p0, p1, orient) = if p0 <= p1 {
332                              (p0, p1, true)
333                          } else {
334                              (p1, p0, false)
335                          };
336                          if p0 != p1 {
337                              self.segs.push(Segment::straight(p0, p1));
338                              self.orientation.push(orient);
339                              self.split_from_predecessor.push((0.0, 1.0));
340                              self.input_segs.push(seg);
341                              self.contour_prev
342                                  .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
343                              self.contour_next.push(Some(SegIdx(self.segs.len())));
344                          }
345                      }
346                      _ => {
347                          let cubic = to_cubic(seg);
348                          let cubics = monotonic_pieces(cubic);
349                          for monotonic in cubics {
350                              let c = monotonic.piece;
351                              let (p0, p1, p2, p3, orient) = if (c.p0.y, c.p0.x) <= (c.p3.y, c.p3.x) {
352                                  (c.p0, c.p1, c.p2, c.p3, true)
353                              } else {
354                                  (c.p3, c.p2, c.p1, c.p0, false)
355                              };
356                              self.segs.push(Segment::monotonic_cubic(
357                                  p0.into(),
358                                  p1.into(),
359                                  p2.into(),
360                                  p3.into(),
361                              ));
362                              self.orientation.push(orient);
363                              self.split_from_predecessor
364                                  .push((monotonic.start_t, monotonic.end_t));
365                              self.input_segs.push(seg);
366                              self.contour_prev
367                                  .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
368                              self.contour_next.push(Some(SegIdx(self.segs.len())));
369                          }
370                      }
371                  }
372              }
373              if old_len < self.segs.len() {
374                  let start_idx = SegIdx(old_len);
375                  let end_idx = SegIdx(self.segs.len() - 1);
376  
377                  // unwrap: contour_next has the same length as `segs`, which is
378                  // non-empty because we checked its length
379                  let start_point = self.oriented_start(start_idx).to_kurbo();
380                  let end_point = self.oriented_end(end_idx).to_kurbo();
381                  if start_point == end_point {
382                      self.contour_prev[start_idx] = Some(end_idx);
383                      self.contour_next[end_idx] = Some(start_idx);
384                  } else if must_be_closed {
385                      return Err(NonClosedPath {
386                          start_point,
387                          end_point,
388                      });
389                  }
390              }
391          }
392          Ok(())
393      }
394  
395      fn add_polyline_without_updating_enter_exit<P: Into<Point>>(
396          &mut self,
397          ps: impl IntoIterator<Item = P>,
398      ) {
399          let old_len = self.segs.len();
400  
401          let ps: Vec<_> = ps.into_iter().map(|p| p.into()).collect();
402          if ps.len() <= 1 {
403              return;
404          }
405  
406          for (p, q) in cyclic_pairs(&ps) {
407              let (a, b, orient) = if p < q { (p, q, true) } else { (q, p, false) };
408              self.segs.push(Segment::straight(*a, *b));
409              self.orientation.push(orient);
410              self.split_from_predecessor.push((0.0, 1.0));
411              self.input_segs
412                  .push(kurbo::PathSeg::Line((p.to_kurbo(), q.to_kurbo()).into()));
413              self.contour_prev
414                  .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
415              self.contour_next.push(Some(SegIdx(self.segs.len())));
416          }
417  
418          if old_len < self.segs.len() {
419              self.contour_prev[SegIdx(old_len)] = Some(SegIdx(self.segs.len() - 1));
420              // unwrap: contour_next has the same length as `segs`, which is
421              // non-empty because we checked its length
422              *self.contour_next.inner.last_mut().unwrap() = Some(SegIdx(old_len));
423          }
424      }
425  
426      /// Construct a segment arena from a single closed polyline.
427      pub fn from_closed_polyline<P: Into<Point>>(ps: impl IntoIterator<Item = P>) -> Self {
428          let mut ret = Self::default();
429          ret.add_closed_polyline(ps);
430          ret
431      }
432  
433      pub(crate) fn update_enter_exit(&mut self, old_len: usize) {
434          for idx in old_len..self.len() {
435              let seg_idx = SegIdx(idx);
436              let seg = &self.segs[seg_idx];
437  
438              self.enter.push((seg.start().y, seg_idx));
439              if !seg.is_horizontal() {
440                  self.exit.push((seg.end().y, seg_idx));
441              }
442          }
443  
444          // We sort the enter segments by y position, and then by horizontal
445          // start position so that they're fairly likely to get inserted in the
446          // sweep-line in order (which makes the indexing fix-ups faster).
447          self.enter.sort_by(|(y1, seg1), (y2, seg2)| {
448              CheapOrderedFloat::from(*y1)
449                  .cmp(&CheapOrderedFloat::from(*y2))
450                  .then_with(|| {
451                      CheapOrderedFloat::from(self.segs[*seg1].at_y(*y1))
452                          .cmp(&CheapOrderedFloat::from(self.segs[*seg2].at_y(*y1)))
453                  })
454          });
455          self.exit.sort_by(|(y1, _), (y2, _)| {
456              CheapOrderedFloat::from(*y1).cmp(&CheapOrderedFloat::from(*y2))
457          });
458      }
459  
460      /// All the entrance heights of segments, ordered by height.
461      ///
462      /// Includes horizontal segments.
463      pub fn entrances(&self) -> &[(f64, SegIdx)] {
464          &self.enter
465      }
466  
467      /// All the exit heights of segments, ordered by height.
468      ///
469      /// Does not include horizontal segments.
470      pub fn exits(&self) -> &[(f64, SegIdx)] {
471          &self.exit
472      }
473  
474      /// Checks that we satisfy our internal invariants. For testing only.
475      pub fn check_invariants(&self) {
476          for (idx, seg) in self.segs.iter() {
477              assert!(seg.start() <= seg.end());
478              if let Some(next_idx) = self.contour_next(idx) {
479                  assert_eq!(self.oriented_end(idx), self.oriented_start(next_idx));
480                  assert_eq!(self.contour_prev(next_idx), Some(idx));
481              }
482          }
483      }
484  }
485  
486  // kurbo's PathSeg::to_cubic turns lines into degenerate cubics, which are numerically
487  // annoying (e.g. they confuse the monotonicity checker). So we roll our own version,
488  // but eventually we should just handle lines and quadratics without converting them.
489  fn to_cubic(seg: kurbo::PathSeg) -> kurbo::CubicBez {
490      match seg {
491          kurbo::PathSeg::Line(kurbo::Line { p0, p1 }) => kurbo::CubicBez {
492              p0,
493              p1: p0 + (p1 - p0) * (1.0 / 3.0),
494              p2: p0 + (p1 - p0) * (2.0 / 3.0),
495              p3: p1,
496          },
497          kurbo::PathSeg::Quad(_) => seg.to_cubic(),
498          kurbo::PathSeg::Cubic(c) => c,
499      }
500  }
501  
502  impl std::ops::Index<SegIdx> for Segments {
503      type Output = Segment;
504  
505      fn index(&self, index: SegIdx) -> &Self::Output {
506          &self.segs[index]
507      }
508  }