1  #![deny(missing_docs)]
  2  #![doc = include_str!("../README.md")]
  3  
  4  #[macro_use]
  5  mod typed_vec;
  6  
  7  #[cfg(any(test, feature = "arbitrary"))]
  8  pub mod arbitrary;
  9  pub mod curve;
 10  mod geom;
 11  mod num;
 12  pub mod order;
 13  mod position;
 14  mod segments;
 15  pub mod sweep;
 16  pub mod topology;
 17  
 18  #[cfg(feature = "generators")]
 19  pub mod generators;
 20  
 21  pub use geom::{Point, Segment};
 22  use kurbo::Shape;
 23  pub use segments::{SegIdx, Segments};
 24  
 25  // pub so that we can use it in fuzz tests, but it's really private
 26  #[doc(hidden)]
 27  pub mod treevec;
 28  
 29  use topology::{BinaryWindingNumber, Topology};
 30  
 31  use crate::segments::NonClosedPath;
 32  
 33  #[cfg(test)]
 34  pub mod perturbation;
 35  
 36  /// A fill rule tells us how to decide whether a point is "inside" a polyline.
 37  #[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
 38  pub enum FillRule {
 39      /// The point is "inside" if its winding number is odd.
 40      EvenOdd,
 41      /// The point is "inside" if its winding number is non-zero.
 42      NonZero,
 43  }
 44  
 45  /// Binary operations between sets.
 46  #[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
 47  pub enum BinaryOp {
 48      /// A point is in the union of two sets if it is in either one.
 49      Union,
 50      /// A point is in the intersection of two sets if it is in both.
 51      Intersection,
 52      /// A point is in the difference of two sets if it is in the first but not the second.
 53      Difference,
 54      /// A point is in the exclusive-or of two sets if it is in one or the other, but not both.
 55      Xor,
 56  }
 57  
 58  #[derive(Clone, Copy, Debug, PartialEq)]
 59  /// The input points were faulty.
 60  pub enum Error {
 61      /// At least one of the inputs was infinite.
 62      Infinity,
 63      /// At least one of the inputs was not a number.
 64      NaN,
 65      /// One of the inputs had a non-closed path.
 66      NonClosedPath(NonClosedPath),
 67  }
 68  
 69  impl From<NonClosedPath> for Error {
 70      fn from(ncp: NonClosedPath) -> Self {
 71          Error::NonClosedPath(ncp)
 72      }
 73  }
 74  
 75  impl std::fmt::Display for Error {
 76      fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 77          match self {
 78              Error::Infinity => write!(f, "one of the inputs was infinite"),
 79              Error::NaN => write!(f, "one of the inputs had a NaN"),
 80              Error::NonClosedPath(_) => write!(f, "one of the inputs had a non-closed path"),
 81          }
 82      }
 83  }
 84  
 85  impl std::error::Error for Error {}
 86  
 87  /// Computes a boolean operation between two sets, each of which is described as a collection of closed polylines.
 88  pub fn binary_op(
 89      set_a: &kurbo::BezPath,
 90      set_b: &kurbo::BezPath,
 91      fill_rule: FillRule,
 92      op: BinaryOp,
 93  ) -> Result<topology::Contours, Error> {
 94      // Find the extremal values, to figure out how much precision we can support.
 95      let bbox = set_a.bounding_box().union(set_b.bounding_box());
 96      let min = bbox.min_x().min(bbox.min_y());
 97      let max = bbox.max_x().max(bbox.max_y());
 98      if min.is_infinite() || max.is_infinite() {
 99          return Err(Error::Infinity);
100      }
101      // If there was any NaN in the input, it should have propagated to the min and max.
102      if min.is_nan() || max.is_nan() {
103          return Err(Error::NaN);
104      }
105  
106      // TODO: we did some analysis for error bounds in the case of polylines.
107      // Think more about what makes sense for curves.
108      let m_2 = min.abs().max(max.abs());
109      let eps = m_2 * (f64::EPSILON * 64.0);
110      let eps = eps.max(1e-6);
111  
112      debug_assert!(eps.is_finite());
113  
114      let top = Topology::from_paths_binary(set_a, set_b, eps)?;
115      #[cfg(feature = "debug-svg")]
116      {
117          svg::save(
118              "out.svg",
119              &top.dump_svg(|tag| {
120                  if tag {
121                      "red".to_owned()
122                  } else {
123                      "blue".to_owned()
124                  }
125              }),
126          )
127          .unwrap();
128      }
129  
130      let inside = |windings: BinaryWindingNumber| {
131          let inside_one = |winding| match fill_rule {
132              FillRule::EvenOdd => winding % 2 != 0,
133              FillRule::NonZero => winding != 0,
134          };
135  
136          match op {
137              BinaryOp::Union => inside_one(windings.shape_a) || inside_one(windings.shape_b),
138              BinaryOp::Intersection => inside_one(windings.shape_a) && inside_one(windings.shape_b),
139              BinaryOp::Xor => inside_one(windings.shape_a) != inside_one(windings.shape_b),
140              BinaryOp::Difference => inside_one(windings.shape_a) && !inside_one(windings.shape_b),
141          }
142      };
143  
144      Ok(top.contours(inside))
145  }
146  
147  #[cfg(test)]
148  mod tests {
149      use insta::assert_ron_snapshot;
150      use kurbo::BezPath;
151  
152      use super::*;
153  
154      #[test]
155      fn two_squares() {
156          fn to_bez(mut points: impl Iterator<Item = (f64, f64)>) -> BezPath {
157              let p = points.next().unwrap();
158              let mut ret = BezPath::default();
159              ret.move_to(p);
160              for q in points {
161                  ret.line_to(q);
162              }
163              ret.line_to(p);
164              ret
165          }
166          let a = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)];
167          let b = vec![(-0.5, -0.5), (0.5, -0.5), (0.5, 0.5), (-0.5, 0.5)];
168          let output = binary_op(
169              &to_bez(a.into_iter()),
170              &to_bez(b.into_iter()),
171              FillRule::EvenOdd,
172              BinaryOp::Intersection,
173          )
174          .unwrap();
175  
176          insta::assert_ron_snapshot!(output);
177      }
178  
179      // This example has a union of two not-quite-axis-aligned crosses. It
180      // suffers from some extra quadratic segments near the intersection points,
181      // but it used to be worse.
182      #[test]
183      fn path_blowup() {
184          let path1 = "M-90.03662872314453,-212 L-90.03662872314453,212 L90.03565216064453,212 L90.03565216064453,-212 L-90.03662872314453,-212 Z";
185          let path2 = "M211.99964904785156,-90.03582000732422 L-212.00035095214844,-90.03646087646484 L-212.00062561035156,90.03582000732422 L211.99937438964844,90.03646087646484 L211.99964904785156,-90.03582000732422 Z";
186          if let Ok(output) = binary_op(
187              &BezPath::from_svg(path1).unwrap(),
188              &BezPath::from_svg(path2).unwrap(),
189              FillRule::NonZero,
190              BinaryOp::Union,
191          ) {
192              let output = output.contours().next().unwrap();
193              let path_length = output.path.elements().len();
194              // This should ideally be more like 12, but there
195              // are some small horizontal segments in the output.
196              // It used to be 77, though...
197              assert!(path_length <= 16);
198          }
199      }
200  
201      #[test]
202      fn test_empty_horizontals() {
203          let square = kurbo::Rect::from_origin_size((0.0, 0.0), (10.0, 10.0)).to_path(0.0);
204          let line_and_back = {
205              let mut path = kurbo::Line::new((-1.0, 0.0), (1.0, 0.0)).to_path(0.0);
206              path.close_path();
207              path
208          };
209          let line_and_back_2 = {
210              let mut path = kurbo::Line::new((2.0, 1.0), (12.0, 1.0)).to_path(0.0);
211              path.close_path();
212              path
213          };
214  
215          Topology::from_path(&line_and_back, 1e-3).unwrap();
216          Topology::from_path(&line_and_back_2, 1e-3).unwrap();
217          Topology::<i32>::from_paths([(&line_and_back, ()), (&line_and_back_2, ())], 1e-3).unwrap();
218          Topology::<i32>::from_paths(
219              [(&line_and_back, ()), (&line_and_back_2, ()), (&square, ())],
220              1e-3,
221          )
222          .unwrap();
223  
224          let output = binary_op(
225              &square,
226              &line_and_back_2,
227              FillRule::EvenOdd,
228              BinaryOp::Difference,
229          )
230          .unwrap();
231          assert_ron_snapshot!(output);
232      }
233  
234      #[test]
235      fn monotonicity_violation() {
236          let path = "M-16.252847470703124,8.977497100830078 C-8.126453262439954,8.977497100830078 -3.724613933559983,8.977497100830078 4.401851380682135,8.977497100830078 C4.401851380682135,8.977497100830078 16.252847872314454,8.977497100830075 16.252847872314454,-0.5280563794708262 C16.252847872314454,-8.977497100830078 4.401851380682135,-8.977497100830075 4.401851380682135,-8.977497100830075 L4.401851380682135,-8.977497100830075 C-5.078945812623724,-8.977497100830075 -1.5236468651340243,-8.977497100830075 -11.004562568404802,-8.977497100830075 Z";
237          let path = BezPath::from_svg(path).unwrap();
238          Topology::from_path(&path, 0.001).unwrap();
239      }
240  }