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

geo_booleanop/boolean/
fill_queue.rs
