1 use super::helper::Float;
2 use geo_types::{LineString, Polygon};
3 use std::collections::BinaryHeap;
4 use std::rc::{Rc, Weak};
5
6 use super::sweep_event::SweepEvent;
7 use super::Operation;
8 use super::helper::BoundingBox;
9
fill_queue<F>( subject: &[Polygon<F>], clipping: &[Polygon<F>], sbbox: &mut BoundingBox<F>, cbbox: &mut BoundingBox<F>, operation: Operation, ) -> BinaryHeap<Rc<SweepEvent<F>>> where F: Float,10 pub 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>>>
17 where
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
process_polygon<F>( contour_or_hole: &LineString<F>, is_subject: bool, contour_id: u32, event_queue: &mut BinaryHeap<Rc<SweepEvent<F>>>, bbox: &mut BoundingBox<F>, is_exterior_ring: bool, ) where F: Float,52 fn 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)]
95 mod 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
make_simple(x: f64, y: f64, is_subject: bool) -> Rc<SweepEvent<f64>>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
check_order_in_queue(first: Rc<SweepEvent<f64>>, second: Rc<SweepEvent<f64>>)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]
test_least_by_x()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]
test_least_by_y()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]
test_least_left()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]
test_shared_edge_not_colinear()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]
test_collinear_edges()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 }
181