1use lyon::algorithms::hit_test::hit_test_path;
2use lyon::geom::arrayvec::ArrayVec;
3use lyon::geom::{BezierSegment, CubicBezierSegment, LineSegment, QuadraticBezierSegment};
4use lyon::path::{FillRule, PathEvent};
5use rayon::prelude::*;
6use std::collections::HashSet;
7
8trait BezierSegmentExt<S> {
9 fn to_linear(self) -> Option<LineSegment<S>>;
10 fn to_quadratic(self) -> Option<QuadraticBezierSegment<S>>;
11 fn to_cubic(self) -> Option<CubicBezierSegment<S>>;
12}
13impl<S> BezierSegmentExt<S> for BezierSegment<S> {
14 fn to_linear(self) -> Option<LineSegment<S>> {
15 match self {
16 BezierSegment::Linear(inner) => Some(inner),
17 _ => None,
18 }
19 }
20 fn to_quadratic(self) -> Option<QuadraticBezierSegment<S>> {
21 match self {
22 BezierSegment::Quadratic(inner) => Some(inner),
23 _ => None,
24 }
25 }
26 fn to_cubic(self) -> Option<CubicBezierSegment<S>> {
27 match self {
28 BezierSegment::Cubic(inner) => Some(inner),
29 _ => None,
30 }
31 }
32}
33
34fn bezier_segment(event: PathEvent) -> Option<BezierSegment<f32>> {
35 match event {
36 PathEvent::Begin { .. } => None,
37 PathEvent::Line { from, to } => Some(LineSegment { from, to }.into()),
38 PathEvent::End {
39 last,
40 first,
41 close: true,
42 } => Some(
43 LineSegment {
44 from: last,
45 to: first,
46 }
47 .into(),
48 ),
49 PathEvent::End { close: false, .. } => None,
50 PathEvent::Quadratic { from, ctrl, to } => {
51 Some(QuadraticBezierSegment { from, to, ctrl }.into())
52 }
53 PathEvent::Cubic {
54 from,
55 ctrl1,
56 ctrl2,
57 to,
58 } => Some(
59 CubicBezierSegment {
60 from,
61 to,
62 ctrl1,
63 ctrl2,
64 }
65 .into(),
66 ),
67 }
68}
69
70fn is_clockwise<I>(path: I, tolerance: f32) -> bool
71where
72 I: Iterator<Item = PathEvent>,
73{
74 lyon::path::iterator::Flattened::new(tolerance, path)
75 .map(|event| match event {
76 PathEvent::Begin { .. } => 0.,
77 PathEvent::Line { from, to } => (to.x - from.x) * (to.y + from.y),
78 PathEvent::End {
79 last,
80 first,
81 close: true,
82 } => (first.x - last.x) * (first.y + last.y),
83 PathEvent::End { close: false, .. } => 0.,
84 _ => unreachable!("flattened should remove curve events"),
85 })
86 .sum::<f32>()
87 > 0.
88}
89
90fn reverse(path: &mut [PathEvent]) {
91 match path.first() {
92 Some(PathEvent::Begin { .. }) => {}
93 _ => panic!("expected path to begin with PathEvent::Begin"),
94 }
95 let (new_first, new_end) = match path.last() {
96 Some(PathEvent::End { last, first, close }) => (
97 PathEvent::Begin { at: *last },
98 PathEvent::End {
99 first: *last,
100 last: *first,
101 close: *close,
102 },
103 ),
104 _ => panic!("expected path to end with PathEvent::End"),
105 };
106
107 path.reverse();
108 path[0] = new_first;
109 path[path.len() - 1] = new_end;
110 if path.len() > 2 {
111 for event in path.iter_mut() {
112 match event.clone() {
113 PathEvent::Begin { .. } | PathEvent::End { .. } => {}
114 PathEvent::Line { from, to } => {
115 *event = PathEvent::Line { from: to, to: from };
116 }
117 PathEvent::Quadratic { from, to, ctrl } => {
118 *event = PathEvent::Quadratic {
119 from: to,
120 to: from,
121 ctrl,
122 };
123 }
124 PathEvent::Cubic {
125 from,
126 to,
127 ctrl1,
128 ctrl2,
129 } => {
130 *event = PathEvent::Cubic {
131 from: to,
132 ctrl1: ctrl2,
133 ctrl2: ctrl1,
134 to: from,
135 };
136 }
137 }
138 }
139 }
140}
141
142fn intersections_t(
143 left: &BezierSegment<f32>,
144 right: &BezierSegment<f32>,
145) -> ArrayVec<[(f32, f32); 9]> {
146 let mut out = ArrayVec::new();
147 match left {
148 BezierSegment::Linear(left) => match right {
149 BezierSegment::Linear(right) => {
150 if let Some(intersection) = left.intersection_t(right) {
151 out.push(intersection);
152 }
153 }
154 BezierSegment::Quadratic(right) => {
155 for (tr, tl) in right.line_segment_intersections_t(&left) {
156 out.push((tl, tr))
157 }
158 }
159 BezierSegment::Cubic(right) => {
160 for (tr, tl) in right.line_segment_intersections_t(&left) {
161 out.push((tl, tr))
162 }
163 }
164 },
165 BezierSegment::Quadratic(left) => match right {
166 BezierSegment::Linear(right) => {
167 out.try_extend_from_slice(&left.line_segment_intersections_t(&right))
168 .unwrap();
169 }
170 BezierSegment::Quadratic(right) => {
171 out.try_extend_from_slice(&left.to_cubic().quadratic_intersections_t(&right))
172 .unwrap();
173 }
174 BezierSegment::Cubic(right) => {
175 out.try_extend_from_slice(&left.to_cubic().cubic_intersections_t(&right))
176 .unwrap();
177 }
178 },
179 BezierSegment::Cubic(left) => match right {
180 BezierSegment::Linear(right) => {
181 out.try_extend_from_slice(&left.line_segment_intersections_t(&right))
182 .unwrap();
183 }
184 BezierSegment::Quadratic(right) => {
185 out.try_extend_from_slice(&left.quadratic_intersections_t(&right))
186 .unwrap();
187 }
188 BezierSegment::Cubic(right) => {
189 out.try_extend_from_slice(&left.cubic_intersections_t(&right))
190 .unwrap();
191 }
192 },
193 }
194 out
195}
196
197struct IndexedIntersectionT {
198 left: (usize, f32),
199 right: (usize, f32),
200}
201
202fn path_intersections_t(left: &[PathEvent], right: &[PathEvent]) -> Vec<IndexedIntersectionT> {
203 left.into_par_iter()
204 .enumerate()
205 .flat_map(|(left_index, left_event)| {
206 right
207 .into_par_iter()
208 .enumerate()
209 .map(move |(right_index, right_event)| {
210 ((left_index, left_event), (right_index, right_event))
211 })
212 })
213 .filter_map(|((left_index, left_event), (right_index, right_event))| {
214 bezier_segment(*left_event).and_then(|left| {
215 bezier_segment(*right_event).map(|right| ((left_index, left), (right_index, right)))
216 })
217 })
218 .flat_map(|((left_index, left), (right_index, right))| {
219 intersections_t(&left, &right)
220 .as_slice()
221 .to_vec()
222 .into_par_iter()
223 .map(move |(tl, tr)| IndexedIntersectionT {
224 left: (left_index, tl),
225 right: (right_index, tr),
226 })
227 })
228 .collect()
229}
230
231fn insert_intersection(events: &mut Vec<PathEvent>, index: usize, t: f32) {
232 let event = events[index];
233 let segment = bezier_segment(event).expect("PathEvent should be a valid BezierSegment");
234 let (left, right) = segment.split(t);
235 match event {
236 PathEvent::Begin { .. } => panic!("PathEvent::Begin not expected"),
237 PathEvent::Line { .. } => {
238 let left = left
239 .to_linear()
240 .expect("PathEvent::Line expects BezierSegment::Linear");
241 let right = right
242 .to_linear()
243 .expect("PathEvent::Line expects BezierSegment::Linear");
244 events[index] = PathEvent::Line {
245 from: left.from,
246 to: left.to,
247 };
248 events.insert(
249 index + 1,
250 PathEvent::Line {
251 from: right.from,
252 to: right.to,
253 },
254 )
255 }
256 PathEvent::End { close: true, .. } => {
257 let left = left
258 .to_linear()
259 .expect("PathEvent::End expects BezierSegment::Linear");
260 let right = right
261 .to_linear()
262 .expect("PathEvent::End expects BezierSegment::Linear");
263 events[index] = PathEvent::Line {
264 from: left.from,
265 to: left.to,
266 };
267 events.insert(
268 index + 1,
269 PathEvent::End {
270 last: right.from,
271 first: right.to,
272 close: true,
273 },
274 )
275 }
276 PathEvent::End { close: false, .. } => panic!("PathEvent::End must be closed"),
277 PathEvent::Quadratic { .. } => {
278 let left = left
279 .to_quadratic()
280 .expect("PathEvent::End expects BezierSegment::Linear");
281 let right = right
282 .to_quadratic()
283 .expect("PathEvent::End expects BezierSegment::Linear");
284 events[index] = PathEvent::Quadratic {
285 from: left.from,
286 ctrl: left.ctrl,
287 to: left.to,
288 };
289 events.insert(
290 index + 1,
291 PathEvent::Quadratic {
292 from: right.from,
293 ctrl: right.ctrl,
294 to: right.to,
295 },
296 )
297 }
298 PathEvent::Cubic { .. } => {
299 let left = left
300 .to_cubic()
301 .expect("PathEvent::End expects BezierSegment::Linear");
302 let right = right
303 .to_cubic()
304 .expect("PathEvent::End expects BezierSegment::Linear");
305 events[index] = PathEvent::Cubic {
306 from: left.from,
307 ctrl1: left.ctrl1,
308 ctrl2: left.ctrl2,
309 to: left.to,
310 };
311 events.insert(
312 index + 1,
313 PathEvent::Cubic {
314 from: right.from,
315 ctrl1: right.ctrl1,
316 ctrl2: right.ctrl2,
317 to: right.to,
318 },
319 )
320 }
321 }
322}
323
324fn insert_intersections<I>(path: &mut Vec<PathEvent>, insertions: I) -> Vec<usize>
325where
326 I: Iterator<Item = (usize, f32)>,
327{
328 let insertions: Vec<(usize, f32)> = insertions.collect();
329 let mut normalized: Vec<(usize, f32, f32)> =
330 insertions.iter().cloned().map(|(i, t)| (i, t, t)).collect();
331 normalized.sort_by(|(i1, t1, _), (i2, t2, _)| match i1.cmp(i2) {
332 std::cmp::Ordering::Equal => t1.partial_cmp(t2).unwrap(),
333 c => c,
334 });
335 let mut last_insertion: Option<(usize, f32, f32)> = None;
336 for insertion in normalized.iter_mut() {
337 if let Some(last_insertion) = last_insertion {
338 if last_insertion.0 == insertion.0 {
339 insertion.1 = (insertion.1 - last_insertion.2) / (1. - last_insertion.2);
340 }
341 }
342 last_insertion = Some(*insertion);
343 }
344 let mut inserted_indices = vec![0; insertions.len()];
345 let mut offset = 0;
346 for (index, t, og_t) in normalized {
347 insert_intersection(path, index + offset, t);
348 let og_index = insertions.iter().position(|i| i == &(index, og_t)).unwrap();
349 inserted_indices[og_index] = index + offset;
350 offset += 1;
351 }
352 inserted_indices
353}
354
355fn update_intersections(
356 left: &mut Vec<PathEvent>,
357 right: &mut Vec<PathEvent>,
358) -> Vec<(usize, usize)> {
359 let intersections = path_intersections_t(left, right);
360 let left_inserted = insert_intersections(left, intersections.iter().map(|i| i.left));
361 let right_inserted = insert_intersections(right, intersections.iter().map(|i| i.right));
362 left_inserted
363 .into_iter()
364 .zip(right_inserted.into_iter())
365 .collect()
366}
367
368#[derive(Copy, Clone)]
369enum IntersectionLabel {
370 InsideToOutside,
371 OutsideToInside,
372}
373
374fn label_intersections(
375 left: &[PathEvent],
376 right: &[PathEvent],
377 intersections: &[(usize, usize)],
378 fill_rule: FillRule,
379 tolerance: f32,
380) -> Vec<IntersectionLabel> {
381 let right_intersections = intersections.iter().map(|(_, i)| *i).collect::<Vec<_>>();
382 let mut inside = match &right[0] {
383 PathEvent::Begin { at } => hit_test_path(at, left.iter().cloned(), fill_rule, tolerance),
384 _ => panic!("path should start with PathEvent::Begin"),
385 };
386 let mut intersection_labels =
387 vec![IntersectionLabel::InsideToOutside; right_intersections.len()];
388 for (path_index, _) in right.iter().enumerate() {
389 if let Some(intersection_index) = right_intersections.iter().position(|&i| i == path_index)
390 {
391 intersection_labels[intersection_index] = if inside {
392 IntersectionLabel::InsideToOutside
393 } else {
394 IntersectionLabel::OutsideToInside
395 };
396 inside = !inside;
397 }
398 }
399 intersection_labels
400}
401
402#[derive(Copy, Clone)]
403pub enum SelectionRule {
404 Intersection,
405}
406
407fn select_path_events(
408 left: &[PathEvent],
409 right: &[PathEvent],
410 intersections: &[(usize, usize)],
411 intersection_labels: &[IntersectionLabel],
412 selection_rule: SelectionRule,
413 starting_intersection: usize,
414) -> (Vec<PathEvent>, HashSet<usize>) {
415 let starting_intersection = intersections[starting_intersection];
416 let mut is_cur_left = true;
417 let mut cur_path_index = starting_intersection.0;
418 let mut out = Vec::with_capacity(right.len());
419 let mut intersections_used = HashSet::new();
420
421 let starting_point = match &left[cur_path_index] {
422 PathEvent::Line { to, .. }
423 | PathEvent::Quadratic { to, .. }
424 | PathEvent::Cubic { to, .. } => *to,
425 PathEvent::Begin { .. } => {
426 unreachable!("an intersection cannot occur at a PathEvent::Begin")
427 }
428 PathEvent::End {
429 first, close: true, ..
430 } => *first,
431 PathEvent::End { close: false, .. } => {
432 unreachable!("an intersection cannot occur at a PathEvent::End that does not close")
433 }
434 };
435 out.push(PathEvent::Begin { at: starting_point });
436
437 loop {
438 if let Some(index) = intersections
439 .iter()
440 .map(|(l, r)| if is_cur_left { l } else { r })
441 .enumerate()
442 .find_map(|(index, intersection)| {
443 if intersection == &cur_path_index {
444 Some(index)
445 } else {
446 None
447 }
448 })
449 {
450 intersections_used.insert(index);
451 let label = intersection_labels[index];
452 let intersection = intersections[index];
453 match (label, selection_rule) {
454 (IntersectionLabel::InsideToOutside, SelectionRule::Intersection) => {
455 is_cur_left = true;
456 cur_path_index = intersection.0;
457 }
458 (IntersectionLabel::OutsideToInside, SelectionRule::Intersection) => {
459 is_cur_left = false;
460 cur_path_index = intersection.1;
461 }
462 }
463 }
464
465 cur_path_index += 1;
466 if (is_cur_left && cur_path_index >= left.len())
467 || (!is_cur_left && cur_path_index >= right.len())
468 {
469 cur_path_index = 1;
471 }
472
473 let (next_event, mut is_end) = if is_cur_left {
474 (
475 left[cur_path_index],
476 cur_path_index == starting_intersection.0,
477 )
478 } else {
479 (
480 right[cur_path_index],
481 cur_path_index == starting_intersection.1,
482 )
483 };
484
485 match next_event {
486 PathEvent::Begin { .. } => {
487 panic!("should skip first PathEvent::Begin while select path events")
488 }
489 PathEvent::End {
490 last, close: false, ..
491 } => {
492 out.push(PathEvent::End {
493 last,
494 first: starting_point,
495 close: false,
496 });
497 is_end = true;
498 }
499 PathEvent::End {
500 last,
501 first,
502 close: true,
503 } => {
504 if is_end {
505 out.push(PathEvent::End {
506 last,
507 first: starting_point,
508 close: true,
509 });
510 } else {
511 out.push(PathEvent::Line {
512 from: last,
513 to: first,
514 });
515 }
516 }
517 PathEvent::Line { from, to } => {
518 if is_end {
519 out.push(PathEvent::End {
520 last: from,
521 first: starting_point,
522 close: true,
523 });
524 } else {
525 out.push(PathEvent::Line { from, to });
526 }
527 }
528 PathEvent::Quadratic { from, to, ctrl } => {
529 out.push(PathEvent::Quadratic { from, to, ctrl });
530 if is_end {
531 out.push(PathEvent::End {
532 last: to,
533 first: starting_point,
534 close: true,
535 });
536 }
537 }
538 PathEvent::Cubic {
539 from,
540 to,
541 ctrl1,
542 ctrl2,
543 } => {
544 out.push(PathEvent::Cubic {
545 from,
546 to,
547 ctrl1,
548 ctrl2,
549 });
550 if is_end {
551 out.push(PathEvent::End {
552 last: to,
553 first: starting_point,
554 close: true,
555 });
556 }
557 }
558 };
559
560 if is_end {
561 break;
562 }
563 }
564
565 (out, intersections_used)
566}
567
568pub fn clip<LeftIter, RightIter>(
569 left: LeftIter,
570 right: RightIter,
571 selection_rule: SelectionRule,
572 fill_rule: FillRule,
573 tolerance: f32,
574) -> Vec<Vec<PathEvent>>
575where
576 LeftIter: IntoIterator<Item = PathEvent>,
577 RightIter: IntoIterator<Item = PathEvent>,
578{
579 let mut left = left.into_iter().collect::<Vec<_>>();
580 let mut right = right.into_iter().collect::<Vec<_>>();
581 if is_clockwise(left.iter().cloned(), tolerance)
582 != is_clockwise(right.iter().cloned(), tolerance)
583 {
584 reverse(&mut right)
585 }
586 let intersections = update_intersections(&mut left, &mut right);
587 if intersections.is_empty() {
588 return match selection_rule {
589 SelectionRule::Intersection => vec![],
590 };
591 }
592 let intersection_labels =
593 label_intersections(&left, &right, &intersections, fill_rule, tolerance);
594
595 let mut out = vec![];
596 let mut intersections_to_be_used = (0..intersections.len()).into_iter().collect::<HashSet<_>>();
597 while !intersections_to_be_used.is_empty() {
598 let next = intersections_to_be_used.iter().cloned().next().unwrap();
599 let (clipped, used) = select_path_events(
600 &left,
601 &right,
602 &intersections,
603 &intersection_labels,
604 selection_rule,
605 next,
606 );
607 intersections_to_be_used = intersections_to_be_used
608 .difference(&used)
609 .cloned()
610 .collect();
611 out.push(clipped);
612 }
613 out
614}
615
616#[cfg(test)]
617mod tests {
618 use super::*;
619 use lyon::geom::point;
620 use lyon::path::polygon::Polygon;
621
622 #[test]
623 fn intersect_squares() {
624 let left = Polygon {
625 points: &[
626 point(-10., 10.),
627 point(10., 10.),
628 point(10., -10.),
629 point(-10., -10.),
630 ],
631 closed: true,
632 };
633
634 let right = Polygon {
635 points: &[
636 point(-5., 5.),
637 point(15., 5.),
638 point(15., -15.),
639 point(-5., -15.),
640 ],
641 closed: true,
642 };
643
644 let out = clip(
645 left.path_events(),
646 right.path_events(),
647 SelectionRule::Intersection,
648 FillRule::NonZero,
649 0.,
650 )
651 .pop();
652
653 let expected_out = Polygon {
654 points: &[
655 point(10., 5.),
656 point(10., -10.),
657 point(-5., -10.),
658 point(-5., 5.),
659 ],
660 closed: true,
661 };
662
663 assert_eq!(out.unwrap(), expected_out.path_events().collect::<Vec<_>>());
664 }
665
666 #[test]
667 fn clockwise_square() {
668 let square_cw = Polygon {
669 points: &[
670 point(-10., 10.),
671 point(10., 10.),
672 point(10., -10.),
673 point(-10., -10.),
674 ],
675 closed: true,
676 };
677 assert!(is_clockwise(square_cw.path_events(), 0.01));
678
679 let square_ccw = Polygon {
680 points: &[
681 point(10., 10.),
682 point(-10., 10.),
683 point(-10., -10.),
684 point(10., -10.),
685 ],
686 closed: true,
687 };
688 assert!(!is_clockwise(square_ccw.path_events(), 0.01))
689 }
690
691 #[test]
692 fn intersect_reversed_squares() {
693 let left = Polygon {
694 points: &[
695 point(-10., 10.),
696 point(10., 10.),
697 point(10., -10.),
698 point(-10., -10.),
699 ],
700 closed: true,
701 };
702
703 let right = Polygon {
704 points: &[
705 point(15., 5.),
706 point(-5., 5.),
707 point(-5., -15.),
708 point(15., -15.),
709 ],
710 closed: true,
711 };
712
713 let out = clip(
714 left.path_events(),
715 right.path_events(),
716 SelectionRule::Intersection,
717 FillRule::NonZero,
718 0.,
719 )
720 .pop();
721
722 let expected_out = Polygon {
723 points: &[
724 point(10., 5.),
725 point(10., -10.),
726 point(-5., -10.),
727 point(-5., 5.),
728 ],
729 closed: true,
730 };
731
732 assert_eq!(out.unwrap(), expected_out.path_events().collect::<Vec<_>>());
733 }
734}