1 use super::helper::Float; 2 use geo_types::Coordinate; 3 use std::cell::RefCell; 4 use std::cmp::Ordering; 5 use std::rc::{Rc, Weak}; 6 7 use super::helper::less_if; 8 use super::signed_area::signed_area; 9 10 #[derive(Clone, Copy, PartialEq, Eq, Debug)] 11 pub enum EdgeType { 12 Normal, 13 NonContributing, 14 SameTransition, 15 DifferentTransition, 16 } 17 18 #[derive(Clone, Copy, PartialEq, Eq, Debug)] 19 pub enum ResultTransition { 20 None, 21 InOut, 22 OutIn, 23 } 24 25 #[derive(Clone, Debug)] 26 struct MutablePart<F> 27 where 28 F: Float, 29 { 30 left: bool, 31 other_event: Weak<SweepEvent<F>>, 32 prev_in_result: Weak<SweepEvent<F>>, 33 edge_type: EdgeType, 34 in_out: bool, 35 other_in_out: bool, 36 result_transition: ResultTransition, 37 other_pos: i32, 38 output_contour_id: i32, 39 } 40 41 #[derive(Clone, Debug)] 42 pub struct SweepEvent<F> 43 where 44 F: Float, 45 { 46 mutable: RefCell<MutablePart<F>>, 47 pub contour_id: u32, 48 pub point: Coordinate<F>, 49 pub is_subject: bool, 50 pub is_exterior_ring: bool, 51 } 52 53 impl<F> SweepEvent<F> 54 where 55 F: Float, 56 { new_rc( contour_id: u32, point: Coordinate<F>, left: bool, other_event: Weak<SweepEvent<F>>, is_subject: bool, is_exterior_ring: bool, ) -> Rc<SweepEvent<F>>57 pub fn new_rc( 58 contour_id: u32, 59 point: Coordinate<F>, 60 left: bool, 61 other_event: Weak<SweepEvent<F>>, 62 is_subject: bool, 63 is_exterior_ring: bool, 64 ) -> Rc<SweepEvent<F>> { 65 Rc::new(SweepEvent { 66 mutable: RefCell::new(MutablePart { 67 left, 68 other_event, 69 prev_in_result: Weak::new(), 70 edge_type: EdgeType::Normal, 71 in_out: false, 72 other_in_out: false, 73 result_transition: ResultTransition::None, 74 other_pos: 0, 75 output_contour_id: -1, 76 }), 77 contour_id, 78 point, 79 is_subject, 80 is_exterior_ring, 81 }) 82 } 83 is_left(&self) -> bool84 pub fn is_left(&self) -> bool { 85 self.mutable.borrow().left 86 } 87 set_left(&self, left: bool)88 pub fn set_left(&self, left: bool) { 89 self.mutable.borrow_mut().left = left 90 } 91 get_other_event(&self) -> Option<Rc<SweepEvent<F>>>92 pub fn get_other_event(&self) -> Option<Rc<SweepEvent<F>>> { 93 self.mutable.borrow().other_event.upgrade() 94 } 95 set_other_event(&self, other_event: &Rc<SweepEvent<F>>)96 pub fn set_other_event(&self, other_event: &Rc<SweepEvent<F>>) { 97 self.mutable.borrow_mut().other_event = Rc::downgrade(other_event); 98 } 99 get_prev_in_result(&self) -> Option<Rc<SweepEvent<F>>>100 pub fn get_prev_in_result(&self) -> Option<Rc<SweepEvent<F>>> { 101 self.mutable.borrow().prev_in_result.upgrade() 102 } 103 set_prev_in_result(&self, prev_in_result: &Rc<SweepEvent<F>>)104 pub fn set_prev_in_result(&self, prev_in_result: &Rc<SweepEvent<F>>) { 105 self.mutable.borrow_mut().prev_in_result = Rc::downgrade(prev_in_result); 106 } 107 unset_prev_in_result(&self)108 pub fn unset_prev_in_result(&self) { 109 self.mutable.borrow_mut().prev_in_result = Weak::new(); 110 } 111 get_edge_type(&self) -> EdgeType112 pub fn get_edge_type(&self) -> EdgeType { 113 self.mutable.borrow().edge_type 114 } 115 set_edge_type(&self, edge_type: EdgeType)116 pub fn set_edge_type(&self, edge_type: EdgeType) { 117 self.mutable.borrow_mut().edge_type = edge_type 118 } 119 is_in_out(&self) -> bool120 pub fn is_in_out(&self) -> bool { 121 self.mutable.borrow().in_out 122 } 123 is_other_in_out(&self) -> bool124 pub fn is_other_in_out(&self) -> bool { 125 self.mutable.borrow().other_in_out 126 } 127 is_in_result(&self) -> bool128 pub fn is_in_result(&self) -> bool { 129 self.mutable.borrow().result_transition != ResultTransition::None 130 } 131 set_result_transition(&self, result_transition: ResultTransition)132 pub fn set_result_transition(&self, result_transition: ResultTransition) { 133 self.mutable.borrow_mut().result_transition = result_transition 134 } 135 get_result_transition(&self) -> ResultTransition136 pub fn get_result_transition(&self) -> ResultTransition { 137 self.mutable.borrow().result_transition 138 } 139 set_in_out(&self, in_out: bool, other_in_out: bool)140 pub fn set_in_out(&self, in_out: bool, other_in_out: bool) { 141 let mut mutable = self.mutable.borrow_mut(); 142 143 mutable.in_out = in_out; 144 mutable.other_in_out = other_in_out; 145 } 146 get_other_pos(&self) -> i32147 pub fn get_other_pos(&self) -> i32 { 148 self.mutable.borrow().other_pos 149 } 150 set_other_pos(&self, other_pos: i32)151 pub fn set_other_pos(&self, other_pos: i32) { 152 self.mutable.borrow_mut().other_pos = other_pos 153 } 154 get_output_contour_id(&self) -> i32155 pub fn get_output_contour_id(&self) -> i32 { 156 self.mutable.borrow().output_contour_id 157 } 158 set_output_contour_id(&self, output_contour_id: i32)159 pub fn set_output_contour_id(&self, output_contour_id: i32) { 160 self.mutable.borrow_mut().output_contour_id = output_contour_id 161 } 162 is_below(&self, p: Coordinate<F>) -> bool163 pub fn is_below(&self, p: Coordinate<F>) -> bool { 164 if let Some(ref other_event) = self.get_other_event() { 165 if self.is_left() { 166 signed_area(self.point, other_event.point, p) > 0. 167 } else { 168 signed_area(other_event.point, self.point, p) > 0. 169 } 170 } else { 171 false 172 } 173 } 174 is_above(&self, p: Coordinate<F>) -> bool175 pub fn is_above(&self, p: Coordinate<F>) -> bool { 176 !self.is_below(p) 177 } 178 is_vertical(&self) -> bool179 pub fn is_vertical(&self) -> bool { 180 match self.get_other_event() { 181 Some(ref other_event) => self.point.x == other_event.point.x, 182 None => false, 183 } 184 } 185 186 /// Helper function to avoid confusion by inverted ordering is_before(&self, other: &SweepEvent<F>) -> bool187 pub fn is_before(&self, other: &SweepEvent<F>) -> bool { 188 self > other 189 } 190 191 /// Helper function to avoid confusion by inverted ordering is_after(&self, other: &SweepEvent<F>) -> bool192 pub fn is_after(&self, other: &SweepEvent<F>) -> bool { 193 self < other 194 } 195 } 196 197 impl<F> PartialEq for SweepEvent<F> 198 where 199 F: Float, 200 { eq(&self, other: &Self) -> bool201 fn eq(&self, other: &Self) -> bool { 202 self.contour_id == other.contour_id 203 && self.is_left() == other.is_left() 204 && self.point == other.point 205 && self.is_subject == other.is_subject 206 } 207 } 208 209 impl<F> Eq for SweepEvent<F> where F: Float {} 210 211 impl<F> PartialOrd for SweepEvent<F> 212 where 213 F: Float, 214 { partial_cmp(&self, other: &Self) -> Option<Ordering>215 fn partial_cmp(&self, other: &Self) -> Option<Ordering> { 216 Some(self.cmp(other)) 217 } 218 } 219 220 impl<F> Ord for SweepEvent<F> 221 where 222 F: Float, 223 { 224 #[inline] cmp(&self, other: &Self) -> Ordering225 fn cmp(&self, other: &Self) -> Ordering { 226 // Ord is exactly the other way round as in the js implementation as BinaryHeap sorts decending 227 let p1 = self.point; 228 let p2 = other.point; 229 230 if p1.x > p2.x { 231 return Ordering::Less; 232 } 233 if p1.x < p2.x { 234 return Ordering::Greater; 235 } 236 if p1.y > p2.y { 237 return Ordering::Less; 238 } 239 if p1.y < p2.y { 240 return Ordering::Greater; 241 } 242 243 if self.is_left() != other.is_left() { 244 return less_if(self.is_left()); 245 } 246 247 if let (Some(other1), Some(other2)) = (self.get_other_event(), other.get_other_event()) { 248 if signed_area(p1, other1.point, other2.point) != 0. { 249 return less_if(!self.is_below(other2.point)); 250 } 251 } 252 253 less_if(!self.is_subject && other.is_subject) 254 } 255 } 256 257 #[cfg(feature = "debug-booleanop")] 258 pub trait JsonDebug { to_json_debug(&self) -> String259 fn to_json_debug(&self) -> String; to_json_debug_short(&self) -> String260 fn to_json_debug_short(&self) -> String; 261 } 262 263 #[cfg(feature = "debug-booleanop")] 264 impl<F> JsonDebug for Rc<SweepEvent<F>> 265 where 266 F: Float, 267 { to_json_debug(&self) -> String268 fn to_json_debug(&self) -> String { 269 format!( 270 "{{\"self\": {}, \"other\": {}}}", 271 self.to_json_debug_short(), 272 self.get_other_event().unwrap().to_json_debug_short(), 273 ) 274 } 275 to_json_debug_short(&self) -> String276 fn to_json_debug_short(&self) -> String { 277 format!( 278 "{{\"addr\": \"{:p}\", \"point\": [{}, {}], \"type\": \"{}\", \"poly\": \"{}\"}}", 279 *self, 280 self.point.x, 281 self.point.y, 282 if self.is_left() { "L" } else { "R" }, 283 if self.is_subject { "A" } else { "B" }, 284 ) 285 } 286 } 287 288 #[cfg(test)] 289 mod test { 290 use super::super::helper::test::xy; 291 use super::*; 292 se_pair( contour_id: u32, x: f64, y: f64, other_x: f64, other_y: f64, is_subject: bool, ) -> (Rc<SweepEvent<f64>>, Rc<SweepEvent<f64>>)293 pub fn se_pair( 294 contour_id: u32, 295 x: f64, 296 y: f64, 297 other_x: f64, 298 other_y: f64, 299 is_subject: bool, 300 ) -> (Rc<SweepEvent<f64>>, Rc<SweepEvent<f64>>) { 301 let other = SweepEvent::new_rc( 302 contour_id, 303 Coordinate { x: other_x, y: other_y }, 304 false, 305 Weak::new(), 306 is_subject, 307 true, 308 ); 309 let event = SweepEvent::new_rc( 310 contour_id, 311 Coordinate { x, y }, 312 true, 313 Rc::downgrade(&other), 314 is_subject, 315 true, 316 ); 317 // Make sure test cases fulfill the invariant of left/right relationship. 318 assert!(event.is_before(&other)); 319 320 (event, other) 321 } 322 323 #[test] test_is_below()324 pub fn test_is_below() { 325 let other_s1 = SweepEvent::new_rc(0, xy(1, 1), false, Weak::new(), false, true); 326 let s1 = SweepEvent::new_rc(0, xy(0, 0), true, Rc::downgrade(&other_s1), false, true); 327 let s2 = SweepEvent::new_rc(0, xy(0, 0), false, Rc::downgrade(&s1), false, true); 328 329 assert!(s1.is_below(xy(0, 1))); 330 assert!(s1.is_below(xy(1, 2))); 331 assert!(!s1.is_below(xy(0, 0))); 332 assert!(!s1.is_below(xy(5, -1))); 333 334 assert!(!s2.is_below(xy(0, 1))); 335 assert!(!s2.is_below(xy(1, 2))); 336 assert!(!s2.is_below(xy(0, 0))); 337 assert!(!s2.is_below(xy(5, -1))); 338 } 339 340 #[test] test_is_above()341 pub fn test_is_above() { 342 let other_s1 = SweepEvent::new_rc(0, xy(1, 1), false, Weak::new(), false, true); 343 let s1 = SweepEvent::new_rc(0, xy(0, 0), true, Rc::downgrade(&other_s1), false, true); 344 let s2 = SweepEvent::new_rc(0, xy(0, 1), false, Rc::downgrade(&s1), false, true); 345 346 assert!(!s1.is_above(xy(0, 1))); 347 assert!(!s1.is_above(xy(1, 2))); 348 assert!(s1.is_above(xy(0, 0))); 349 assert!(s1.is_above(xy(5, -1))); 350 351 assert!(s2.is_above(xy(0, 1))); 352 assert!(s2.is_above(xy(1, 2))); 353 assert!(s2.is_above(xy(0, 0))); 354 assert!(s2.is_above(xy(5, -1))); 355 } 356 357 #[test] test_is_vertical()358 pub fn test_is_vertical() { 359 let other_s1 = SweepEvent::new_rc(0, xy(0, 1), false, Weak::new(), false, true); 360 let s1 = SweepEvent::new_rc(0, xy(0, 0), true, Rc::downgrade(&other_s1), false, true); 361 let other_s2 = SweepEvent::new_rc(0, xy(0.0001, 1), false, Weak::new(), false, true); 362 let s2 = SweepEvent::new_rc(0, xy(0, 0), true, Rc::downgrade(&other_s2), false, true); 363 364 assert!(s1.is_vertical()); 365 assert!(!s2.is_vertical()); 366 } 367 368 #[rustfmt::skip] 369 #[test] test_order_star_pattern()370 fn test_order_star_pattern() { 371 // This test verifies the assumption underlying the `precompute_iteration_order` logic: 372 // Events with an identical points must be ordered: 373 // - R events before L events 374 // - R events in clockwise order 375 // - L events in counter-clockwise order 376 let id = 0; 377 let z = 0.; 378 379 // Group 'a' which have their right event at (0, 0), clockwise 380 let (_av_l, av_r) = se_pair(id, 0., -1., z, z, true); // vertical comes first 381 let (_a1_l, a1_r) = se_pair(id, -2., -6., z, z, true); 382 let (_a2_l, a2_r) = se_pair(id, -1., -2., z, z, true); 383 let (_a3_l, a3_r) = se_pair(id, -1., -1., z, z, true); 384 let (_a4_l, a4_r) = se_pair(id, -2., -1., z, z, true); 385 let (_a5_l, a5_r) = se_pair(id, -2., 1., z, z, true); 386 let (_a6_l, a6_r) = se_pair(id, -1., 1., z, z, true); 387 let (_a7_l, a7_r) = se_pair(id, -1., 2., z, z, true); 388 let (_a8_l, a8_r) = se_pair(id, -2., 6., z, z, true); 389 390 // Group 'b' which have their left event at (0, 0), counter clockwise 391 let (b1_l, _b1_r) = se_pair(id, z, z, 2., -6., true); 392 let (b2_l, _b2_r) = se_pair(id, z, z, 1., -2., true); 393 let (b3_l, _b3_r) = se_pair(id, z, z, 1., -1., true); 394 let (b4_l, _b4_r) = se_pair(id, z, z, 2., -1., true); 395 let (b5_l, _b5_r) = se_pair(id, z, z, 2., 1., true); 396 let (b6_l, _b6_r) = se_pair(id, z, z, 1., 1., true); 397 let (b7_l, _b7_r) = se_pair(id, z, z, 1., 2., true); 398 let (b8_l, _b8_r) = se_pair(id, z, z, 2., 6., true); 399 let (bv_l, _bv_r) = se_pair(id, z, z, 0., 1., true); // vertical comes last 400 401 let events_expected_order = [ 402 av_r, a1_r, a2_r, a3_r, a4_r, a5_r, a6_r, a7_r, a8_r, 403 b1_l, b2_l, b3_l, b4_l, b5_l, b6_l, b7_l, b8_l, bv_l, 404 ]; 405 406 for i in 0 .. events_expected_order.len() - 1 { 407 for j in i + 1 .. events_expected_order.len() { 408 assert!(events_expected_order[i].is_before(&events_expected_order[j])); 409 } 410 } 411 412 } 413 } 414