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