geo_booleanop2/boolean/
fill_queue.rs

1use super::helper::Float;
2use geo_types::{LineString, Polygon};
3use std::collections::BinaryHeap;
4use std::rc::{Rc, Weak};
5
6use super::helper::BoundingBox;
7use super::sweep_event::SweepEvent;
8use super::Operation;
9
10pub fn fill_queue<F>(
11    subject: &[Polygon<F>],
12    clipping: &[Polygon<F>],
13    sbbox: &mut BoundingBox<F>,
14    cbbox: &mut BoundingBox<F>,
15    operation: Operation,
16) -> BinaryHeap<Rc<SweepEvent<F>>>
17where
18    F: Float,
19{
20    let mut event_queue: BinaryHeap<Rc<SweepEvent<F>>> = BinaryHeap::new();
21    let mut contour_id = 0u32;
22
23    for polygon in subject {
24        contour_id += 1;
25        process_polygon(polygon.exterior(), true, contour_id, &mut event_queue, sbbox, true);
26        for interior in polygon.interiors() {
27            process_polygon(interior, true, contour_id, &mut event_queue, sbbox, false);
28        }
29    }
30
31    for polygon in clipping {
32        let exterior = operation != Operation::Difference;
33        if exterior {
34            contour_id += 1;
35        }
36        process_polygon(polygon.exterior(), false, contour_id, &mut event_queue, cbbox, exterior);
37        for interior in polygon.interiors() {
38            process_polygon(interior, false, contour_id, &mut event_queue, cbbox, false);
39        }
40    }
41
42    event_queue
43}
44
45fn process_polygon<F>(
46    contour_or_hole: &LineString<F>,
47    is_subject: bool,
48    contour_id: u32,
49    event_queue: &mut BinaryHeap<Rc<SweepEvent<F>>>,
50    bbox: &mut BoundingBox<F>,
51    is_exterior_ring: bool,
52) where
53    F: Float,
54{
55    for line in contour_or_hole.lines() {
56        if line.start == line.end {
57            continue; // skip collapsed edges
58        }
59
60        let e1 = SweepEvent::new_rc(contour_id, line.start, false, Weak::new(), is_subject, is_exterior_ring);
61        let e2 = SweepEvent::new_rc(
62            contour_id,
63            line.end,
64            false,
65            Rc::downgrade(&e1),
66            is_subject,
67            is_exterior_ring,
68        );
69        e1.set_other_event(&e2);
70
71        if e1 < e2 {
72            e2.set_left(true)
73        } else {
74            e1.set_left(true)
75        }
76
77        bbox.min.x = bbox.min.x.min(line.start.x);
78        bbox.min.y = bbox.min.y.min(line.start.y);
79        bbox.max.x = bbox.max.x.max(line.start.x);
80        bbox.max.y = bbox.max.y.max(line.start.y);
81
82        event_queue.push(e1);
83        event_queue.push(e2);
84    }
85}
86
87#[cfg(test)]
88mod test {
89    use super::*;
90    use geo_types::Coord;
91    use std::cmp::Ordering;
92    use std::collections::BinaryHeap;
93    use std::rc::{Rc, Weak};
94
95    fn make_simple(x: f64, y: f64, is_subject: bool) -> Rc<SweepEvent<f64>> {
96        SweepEvent::new_rc(0, Coord { x, y }, false, Weak::new(), is_subject, true)
97    }
98
99    fn check_order_in_queue(first: Rc<SweepEvent<f64>>, second: Rc<SweepEvent<f64>>) {
100        let mut queue: BinaryHeap<Rc<SweepEvent<f64>>> = BinaryHeap::new();
101
102        assert_eq!(first.cmp(&second), Ordering::Greater);
103        assert_eq!(second.cmp(&first), Ordering::Less);
104        {
105            queue.push(first.clone());
106            queue.push(second.clone());
107
108            let p1 = queue.pop().unwrap();
109            let p2 = queue.pop().unwrap();
110
111            assert!(Rc::ptr_eq(&first, &p1));
112            assert!(Rc::ptr_eq(&second, &p2));
113        }
114        {
115            queue.push(second.clone());
116            queue.push(first.clone());
117
118            let p1 = queue.pop().unwrap();
119            let p2 = queue.pop().unwrap();
120
121            assert!(Rc::ptr_eq(&first, &p1));
122            assert!(Rc::ptr_eq(&second, &p2));
123        }
124    }
125
126    #[test]
127    fn test_least_by_x() {
128        check_order_in_queue(make_simple(0.0, 0.0, false), make_simple(0.5, 0.5, false))
129    }
130
131    #[test]
132    fn test_least_by_y() {
133        check_order_in_queue(make_simple(0.0, 0.0, false), make_simple(0.0, 0.5, false))
134    }
135
136    #[test]
137    fn test_least_left() {
138        let e1 = make_simple(0.0, 0.0, false);
139        e1.set_left(true);
140        let e2 = make_simple(0.0, 0.0, false);
141        e2.set_left(false);
142
143        check_order_in_queue(e2, e1)
144    }
145
146    #[test]
147    fn test_shared_edge_not_colinear() {
148        let other_e1 = make_simple(1.0, 1.0, false);
149        let e1 = make_simple(0.0, 0.0, false);
150        e1.set_other_event(&other_e1);
151        e1.set_left(true);
152        let other_e2 = make_simple(2.0, 3.0, false);
153        let e2 = make_simple(0.0, 0.0, false);
154        e2.set_other_event(&other_e2);
155        e2.set_left(true);
156
157        check_order_in_queue(e1, e2)
158    }
159
160    #[test]
161    fn test_collinear_edges() {
162        let other_e1 = make_simple(1.0, 1.0, true);
163        let e1 = make_simple(0.0, 0.0, true);
164        e1.set_other_event(&other_e1);
165        e1.set_left(true);
166        let other_e2 = make_simple(2.0, 2.0, false);
167        let e2 = make_simple(0.0, 0.0, false);
168        e2.set_other_event(&other_e2);
169        e2.set_left(true);
170
171        check_order_in_queue(e1, e2)
172    }
173}
geo_booleanop2/boolean/fill_queue.rs

geo_booleanop2/boolean/
fill_queue.rs
