geo_booleanop/boolean/
possible_intersection.rs

1use super::divide_segment::divide_segment;
2use super::helper::Float;
3use super::segment_intersection::{intersection, LineIntersection};
4use super::sweep_event::{EdgeType, SweepEvent};
5use std::collections::BinaryHeap;
6use std::rc::Rc;
7
8pub fn possible_intersection<F>(
9    se1: &Rc<SweepEvent<F>>,
10    se2: &Rc<SweepEvent<F>>,
11    queue: &mut BinaryHeap<Rc<SweepEvent<F>>>,
12) -> u8
13where
14    F: Float,
15{
16    let (other1, other2) = match (se1.get_other_event(), se2.get_other_event()) {
17        (Some(other1), Some(other2)) => (other1, other2),
18        _ => return 0,
19    };
20
21    let inter = intersection(se1.point, other1.point, se2.point, other2.point);
22
23    #[cfg(feature = "debug-booleanop")]
24    match inter {
25        LineIntersection::Point(inter) => {
26            println!("{{\"intersection\": [{}, {}]}}", inter.x, inter.y);
27        }
28        LineIntersection::Overlap(p1, p2) => {
29            println!(
30                "{{\"overlap1\": [{}, {}], \"overlap2\": [{}, {}]}}",
31                p1.x, p1.y, p2.x, p2.y
32            );
33        }
34        _ => {}
35    }
36
37    match inter {
38        LineIntersection::None => 0, // No intersection
39        LineIntersection::Point(_) if se1.point == se2.point || other1.point == other2.point => {
40            // The line segments intersect at either the left or right endpoint.
41            // In this case we ignore the result of intersection computation for numerical
42            // stability (the computed intersection can slightly deviate from the endpoints).
43            // It may be tempting to make this check earlier to short-circuit the intersection
44            // computation, but it may be tricky, because we still need to differentiate from
45            // overlapping cases.
46            0
47        }
48        LineIntersection::Point(inter) => {
49            if se1.point != inter && other1.point != inter {
50                divide_segment(&se1, inter, queue);
51            }
52            if se2.point != inter && other2.point != inter {
53                divide_segment(&se2, inter, queue);
54            }
55            1
56        }
57        LineIntersection::Overlap(_, _) if se1.is_subject == se2.is_subject => 0, // The line segments associated to se1 and se2 overlap
58        LineIntersection::Overlap(_, _) => {
59            let mut events = Vec::new();
60            let mut left_coincide = false;
61            let mut right_coincide = false;
62
63            if se1.point == se2.point {
64                left_coincide = true
65            } else if se1 < se2 {
66                events.push((se2.clone(), other2.clone()));
67                events.push((se1.clone(), other1.clone()));
68            } else {
69                events.push((se1.clone(), other1.clone()));
70                events.push((se2.clone(), other2.clone()));
71            }
72
73            if other1.point == other2.point {
74                right_coincide = true
75            } else if other1 < other2 {
76                events.push((other2, se2.clone()));
77                events.push((other1, se1.clone()));
78            } else {
79                events.push((other1, se1.clone()));
80                events.push((other2, se2.clone()));
81            }
82
83            if left_coincide {
84                // both line segments are equal or share the left endpoint
85                se2.set_edge_type(EdgeType::NonContributing);
86                if se1.is_in_out() == se2.is_in_out() {
87                    se1.set_edge_type(EdgeType::SameTransition)
88                } else {
89                    se1.set_edge_type(EdgeType::DifferentTransition)
90                }
91
92                if left_coincide && !right_coincide {
93                    divide_segment(&events[1].1, events[0].0.point, queue)
94                }
95                return 2;
96            }
97
98            if right_coincide {
99                // the line segments share the right endpoint
100                divide_segment(&events[0].0, events[1].0.point, queue);
101                return 3;
102            }
103
104            if !Rc::ptr_eq(&events[0].0, &events[3].1) {
105                // no line segment includes totally the other one
106                divide_segment(&events[0].0, events[1].0.point, queue);
107                divide_segment(&events[1].0, events[2].0.point, queue);
108                return 3;
109            }
110
111            // one line segment includes the other one
112            // TODO: write this in a non-panicking way. Note that we must not access the "other event"
113            // via events[3].1 because that is only a static reference, and the first divide segment
114            // internally modifies the other event point (we must access the updated other event).
115            // Probably the best solution is to introduce explicit return types for divide_segment.
116            divide_segment(&events[0].0, events[1].0.point, queue);
117            divide_segment(&events[3].0.get_other_event().unwrap(), events[2].0.point, queue);
118
119            3
120        }
121    }
122}
geo_booleanop/boolean/possible_intersection.rs

geo_booleanop/boolean/
possible_intersection.rs
