range.rs
1 use crate::{num::CheapOrderedFloat, SegIdx}; 2 3 use super::{ChangedInterval, OutputEvent, SweepLine}; 4 5 /// A horizontal fragment. 6 /// 7 /// Represents a horizontal part of a segment, which could be either an actual 8 /// horizontal segment or a little horizontal connector of a segment in a 9 /// sweep-line. 10 #[derive(Clone, Debug, PartialEq)] 11 struct HFrag { 12 /// The segment this horizontal fragment is a part of. 13 pub seg: SegIdx, 14 /// The first (smallest) horizontal position of this fragment. 15 pub start: f64, 16 /// The last (largest) horizontal position of this fragment. 17 pub end: f64, 18 /// Does this segment continue out of the sweep-line at `start`? 19 /// 20 /// For a horizontal segment, this will always be false. On its own, 21 /// this doesn't tell you whether the segment points up or down at 22 /// `start`; for that, see `enter_first`. 23 pub connected_at_start: bool, 24 /// Does this segment continue out of the sweep-line at `end`? 25 /// 26 /// For a horizontal segment, this will always be false. 27 pub connected_at_end: bool, 28 /// When traversing the segment in sweep-line order, does it visit 29 /// `start` first? 30 /// 31 /// For example: 32 /// 33 /// ```text 34 /// s_1 s_2 s_3 35 /// ╲ ╱ ╲ 36 /// ╲ ╱ ╲ 37 /// ─ ─ ─ 38 /// ╲ ╱ ╲ 39 /// ╲ ╱ ╲ 40 /// ``` 41 /// 42 /// When moving from top to bottom (i.e. sweep-line order), s_1 and s_2 43 /// visit the larger horizontal position of the fragment before the smaller 44 /// one, so `enter_first` is false. On the other hand, s_3 has `enter_first` 45 /// as true. 46 pub enter_first: bool, 47 /// The position of the segment in the current sweep-line. 48 /// 49 /// This will be `None` if, and only if, the segment is horizontal. 50 pub sweep_idx: Option<usize>, 51 /// The position of the segment in the old sweep-line. 52 /// 53 /// This will be `None` if, and only if, the segment is horizontal. 54 pub old_sweep_idx: Option<usize>, 55 } 56 57 impl HFrag { 58 /// Given a segment's interaction with the sweep-line, returns the corresponding 59 /// horizontal fragment if there is one. 60 pub fn from_position(pos: OutputEvent) -> Option<Self> { 61 let OutputEvent { 62 x0, 63 connected_above, 64 x1, 65 connected_below, 66 .. 67 } = pos; 68 69 if x0 == x1 { 70 return None; 71 } 72 73 let enter_first = x0 < x1; 74 let (start, end, connected_at_start, connected_at_end) = if enter_first { 75 (x0, x1, connected_above, connected_below) 76 } else { 77 (x1, x0, connected_below, connected_above) 78 }; 79 Some(HFrag { 80 end, 81 start, 82 enter_first, 83 seg: pos.seg_idx, 84 connected_at_start, 85 connected_at_end, 86 sweep_idx: pos.sweep_idx, 87 old_sweep_idx: pos.old_sweep_idx, 88 }) 89 } 90 91 /// Does this horizontal fragment's segment stick up from the sweep-line at `x`? 92 pub fn connected_above_at(&self, x: f64) -> bool { 93 (x == self.start && self.enter_first && self.connected_at_start) 94 || (x == self.end && !self.enter_first && self.connected_at_end) 95 } 96 97 /// Does this horizontal fragment's segment stick down from the sweep-line at `x`? 98 pub fn connected_below_at(&self, x: f64) -> bool { 99 (x == self.start && !self.enter_first && self.connected_at_start) 100 || (x == self.end && self.enter_first && self.connected_at_end) 101 } 102 } 103 104 /// Emits output events for a single sub-range of a single sweep-line. 105 /// 106 /// This is constructed using [`SweepLine::next_range`]. By repeatedly 107 /// calling `SweepLineRange::increase_x` you can iterate over all 108 /// interesting horizontal positions, left to right (i.e. smaller `x` to larger 109 /// `x`). 110 #[derive(Debug)] 111 pub struct SweepLineRange<'bufs, 'state, 'segs> { 112 last_x: Option<f64>, 113 line: &'state SweepLine<'state, 'state, 'segs>, 114 bufs: &'bufs mut SweepLineRangeBuffers, 115 changed_interval: ChangedInterval, 116 output_events: &'state [OutputEvent], 117 } 118 119 impl<'bufs, 'state, 'segs> SweepLineRange<'bufs, 'state, 'segs> { 120 pub(crate) fn new( 121 line: &'state SweepLine<'state, 'state, 'segs>, 122 output_events: &'state [OutputEvent], 123 bufs: &'bufs mut SweepLineRangeBuffers, 124 changed_interval: ChangedInterval, 125 ) -> Self { 126 let ret = Self { 127 last_x: None, 128 output_events, 129 changed_interval, 130 line, 131 bufs, 132 }; 133 134 #[cfg(feature = "slow-asserts")] 135 ret.check_invariants(); 136 137 ret 138 } 139 140 fn output_events(&self) -> &[OutputEvent] { 141 self.output_events 142 } 143 144 /// The current horizontal position, or `None` if we're finished. 145 pub fn x(&self) -> Option<f64> { 146 match ( 147 self.bufs.active_horizontals.first(), 148 self.output_events().first(), 149 ) { 150 (None, None) => None, 151 (None, Some(pos)) => Some(pos.smaller_x()), 152 (Some(h), None) => Some(h.end), 153 (Some(h), Some(pos)) => Some((h.end).min(pos.smaller_x())), 154 } 155 } 156 157 fn positions_at_x<'c, 'b: 'c>(&'b self, x: f64) -> impl Iterator<Item = &'b OutputEvent> + 'c { 158 self.output_events() 159 .iter() 160 .take_while(move |p| p.smaller_x() == x) 161 } 162 163 /// Updates a [`SegmentsConnectedAtX`] to reflect the current horizontal position. 164 pub fn update_segments_at_x(&self, segs: &mut SegmentsConnectedAtX) { 165 segs.connected_up.clear(); 166 segs.connected_down.clear(); 167 168 let Some(x) = self.x() else { 169 return; 170 }; 171 172 for hseg in &self.bufs.active_horizontals { 173 if hseg.connected_above_at(x) { 174 segs.connected_up 175 .push((hseg.seg, hseg.old_sweep_idx.unwrap())); 176 } 177 178 if hseg.connected_below_at(x) { 179 segs.connected_down 180 .push((hseg.seg, hseg.sweep_idx.unwrap())); 181 } 182 } 183 184 for pos in self.positions_at_x(x) { 185 if pos.connected_above_at(x) { 186 segs.connected_up 187 .push((pos.seg_idx, pos.old_sweep_idx.unwrap())); 188 } 189 190 if pos.connected_below_at(x) { 191 segs.connected_down 192 .push((pos.seg_idx, pos.sweep_idx.unwrap())); 193 } 194 } 195 196 segs.connected_up 197 .sort_by_key(|(_seg_idx, sweep_idx)| *sweep_idx); 198 segs.connected_down 199 .sort_by_key(|(_seg_idx, sweep_idx)| *sweep_idx); 200 } 201 202 /// Iterates over the horizontal segments that are active at the current position. 203 /// 204 /// This includes the segments that end here, but does not include the ones 205 /// that start here. 206 pub fn active_horizontals(&self) -> impl Iterator<Item = SegIdx> + '_ { 207 self.bufs.active_horizontals.iter().map(|hseg| hseg.seg) 208 } 209 210 /// Iterates over the horizontal segments that are active at the current position, along 211 /// with a boolean telling you whether the horizontal segment has the same orientation 212 /// as the segment that it belongs to. 213 /// 214 /// This includes the segments that end here, but does not include the ones 215 /// that start here. 216 pub fn active_horizontals_and_orientations(&self) -> impl Iterator<Item = (SegIdx, bool)> + '_ { 217 self.bufs 218 .active_horizontals 219 .iter() 220 .map(|hseg| (hseg.seg, hseg.enter_first)) 221 } 222 223 /// Returns the collection of all output events that end at the current 224 /// position, or `None` if this batcher is finished. 225 /// 226 /// All the returned events start at the previous `x` position and end 227 /// at the current `x` position. In particular, if you alternate between 228 /// calling [`SweepLineRange::increase_x`] and this method, you'll 229 /// receive non-overlapping batches of output events. 230 pub fn events(&mut self) -> Option<Vec<OutputEvent>> { 231 let next_x = self.x()?; 232 233 let mut ret = Vec::new(); 234 for h in &self.bufs.active_horizontals { 235 // unwrap: on the first event of this sweep line, active_horizontals is empty. So 236 // we only get here after last_x is populated. 237 let x0 = self.last_x.unwrap(); 238 let x1 = next_x.min(h.end); 239 let connected_end = x1 == h.end && h.connected_at_end; 240 let connected_start = x0 == h.start && h.connected_at_start; 241 if h.enter_first { 242 ret.push(OutputEvent::new( 243 h.seg, 244 x0, 245 connected_start, 246 x1, 247 connected_end, 248 h.sweep_idx, 249 h.old_sweep_idx, 250 )); 251 } else { 252 ret.push(OutputEvent::new( 253 h.seg, 254 x1, 255 connected_end, 256 x0, 257 connected_start, 258 h.sweep_idx, 259 h.old_sweep_idx, 260 )); 261 } 262 } 263 264 // Drain the active horizontals, throwing away horizontal segments that end before 265 // the new x position. 266 self.drain_active_horizontals(next_x); 267 268 // Move along to the next horizontal position, processing the x events at the current 269 // position and either emitting them immediately or saving them as horizontals. 270 while let Some(ev) = self.output_events.first() { 271 if ev.smaller_x() > next_x { 272 break; 273 } 274 self.output_events = &self.output_events[1..]; 275 276 if ev.x0 == ev.x1 { 277 // We push output event for points immediately. 278 ret.push(ev.clone()); 279 } else if let Some(hseg) = HFrag::from_position(ev.clone()) { 280 // For horizontal segments, we don't output anything straight 281 // away. When we update the horizontal position and visit our 282 // horizontal segments, we'll output something. 283 self.bufs.active_horizontals.push(hseg); 284 } 285 } 286 self.bufs 287 .active_horizontals 288 .sort_by_key(|a| CheapOrderedFloat::from(a.end)); 289 self.last_x = Some(next_x); 290 Some(ret) 291 } 292 293 /// Move along to the next horizontal position. 294 pub fn increase_x(&mut self) { 295 if let Some(x) = self.x() { 296 self.drain_active_horizontals(x); 297 298 while let Some(ev) = self.output_events.first() { 299 if ev.smaller_x() > x { 300 break; 301 } 302 self.output_events = &self.output_events[1..]; 303 304 if let Some(hseg) = HFrag::from_position(ev.clone()) { 305 self.bufs.active_horizontals.push(hseg); 306 } 307 } 308 } 309 self.bufs 310 .active_horizontals 311 .sort_by_key(|a| CheapOrderedFloat::from(a.end)); 312 } 313 314 fn drain_active_horizontals(&mut self, x: f64) { 315 let new_start = self 316 .bufs 317 .active_horizontals 318 .iter() 319 .position(|h| h.end > x) 320 .unwrap_or(self.bufs.active_horizontals.len()); 321 self.bufs.active_horizontals.drain(..new_start); 322 } 323 324 /// The indices within the sweep line represented by this range. 325 pub fn seg_range(&self) -> ChangedInterval { 326 self.changed_interval.clone() 327 } 328 329 /// Returns an iterator over the segments in this range, ordered according 330 /// to the "old" sweep-line. 331 /// 332 /// In addition to appearing in a different order, the set of segments returned 333 /// by this method and [`Self::segment_range`] may differ: segments that exit at the 334 /// current sweep line will be returned here and not there, while segments that 335 /// enter at the current sweep line will be returned there and not here. 336 pub fn old_segment_range(&self) -> impl Iterator<Item = SegIdx> + '_ { 337 let range = self.changed_interval.segs.clone(); 338 self.line().old_segment_range(range) 339 } 340 341 /// Returns an iterator over the segments in this range, ordered according 342 /// to the "new" sweep-line. 343 /// 344 /// In addition to appearing in a different order, the set of segments returned 345 /// by this method and [`Self::old_segment_range`] may differ: segments that exit at the 346 /// current sweep line will be returned there and not here, while segments that 347 /// enter at the current sweep line will be returned here and not there. 348 pub fn segment_range(&self) -> impl Iterator<Item = SegIdx> + '_ { 349 let range = self.changed_interval.segs.clone(); 350 self.line().segment_range(range) 351 } 352 353 /// The sweep line that this is a range of. 354 pub fn line(&self) -> &SweepLine<'_, '_, 'segs> { 355 self.line 356 } 357 358 #[cfg(feature = "slow-asserts")] 359 fn check_invariants(&self) { 360 for ev in self.output_events() { 361 let seg = &self.line.segments()[ev.seg_idx]; 362 let y = self.line.y(); 363 let eps = self.line.eps(); 364 365 // The curve comparison is guaranteed to give a strong 366 // ordering when the curves are 1.5 eps apart in ell_infty. 367 // That means the perturbed points should always be within 368 // 1.5 * sqrt(2) eps in ell_2, which is less than 2.5 eps. We 369 // compute distance to accuracy 0.5 eps, so we'll assert 370 // that our number is less than 3 eps. 371 372 // Ok, this doesn't work because of https://github.com/linebender/kurbo/issues/446 373 // For now, we'll use ell_infty comparisons. 374 // 375 // let n0 = seg.nearest(p0, eps / 2.0); 376 // let n1 = seg.nearest(p1, eps / 2.0); 377 378 // assert!(n0.distance_sq <= eps * eps * 9.0); 379 // assert!(n1.distance_sq <= eps * eps * 9.0); 380 381 let (lower, upper) = if seg.is_horizontal() { 382 (seg.start().x - 2.0 * eps, seg.end().x + 2.0 * eps) 383 } else { 384 (seg.lower(y, 2.0 * eps), seg.upper(y, 2.0 * eps)) 385 }; 386 assert!(ev.smaller_x() <= upper && lower <= ev.larger_x()); 387 } 388 } 389 } 390 391 /// A re-usable struct for collecting segments at a single position on a sweep-line. 392 /// 393 /// See [`SweepLineRange::update_segments_at_x`] for where this is used. At 394 /// any given time, this struct is implicitly associated to a single horizontal 395 /// position: the position of the `SweepLineRange` last time we were updated. 396 #[derive(Debug, Default)] 397 pub struct SegmentsConnectedAtX { 398 connected_up: Vec<(SegIdx, usize)>, 399 connected_down: Vec<(SegIdx, usize)>, 400 } 401 402 impl SegmentsConnectedAtX { 403 /// The segments that are connected up to a previous sweep-line at the 404 /// current horizontal position. 405 /// 406 /// The returned iterator is sorted by the old sweep-line order. In other 407 /// words, it will return segments clockwise when viewed from the current 408 /// position. 409 pub fn connected_up(&self) -> impl Iterator<Item = SegIdx> + '_ { 410 self.connected_up.iter().map(|x| x.0) 411 } 412 413 /// The segments that are connected down to a subsequent sweep-line at the 414 /// current horizontal position. 415 /// 416 /// The returned iterator is sorted by the new sweep-line order. In other 417 /// words, it will return segments counter-clockwise when viewed from the current 418 /// position. 419 pub fn connected_down(&self) -> impl Iterator<Item = SegIdx> + '_ { 420 self.connected_down.iter().map(|x| x.0) 421 } 422 } 423 424 /// Holds some buffers that are used when iterating over a sweep-line. 425 /// 426 /// Save on re-allocation by allocating this once and reusing it in multiple calls to 427 /// [`SweepLine::next_range`]. 428 #[derive(Clone, Debug, Default)] 429 pub struct SweepLineRangeBuffers { 430 /// All the horizontal segments overlapping with the sweep-line-range's current 431 /// horizontal position, ordered by ending position. 432 /// 433 /// We could keep this in an ordered data structure, but it turns out to 434 /// be faster to just sort it regularly: every time we modify this, we also 435 /// advance the horizontal position and iterate over this entire collection. 436 /// Therefore, there's no asymptotic run-time to be gained by having a fast 437 /// way to insert/delete a single element. 438 active_horizontals: Vec<HFrag>, 439 } 440 441 impl SweepLineRangeBuffers { 442 pub(crate) fn clear(&mut self) { 443 self.active_horizontals.clear(); 444 } 445 }