geo/algorithm/sweep/
iter.rs

1use std::cmp::Ordering;
2
3use super::*;
4use crate::{line_intersection::line_intersection, Coord, LineIntersection};
5
6/// A segment of a input [`Cross`] type.
7///
8/// This type is used to convey the part of the input geometry that is
9/// intersecting at a given intersection. This is returned by the
10/// [`CrossingsIter::intersections`] method.
11#[derive(Debug, Clone)]
12pub(crate) struct Crossing<C: Cross> {
13    /// The input associated with this segment.
14    pub cross: C,
15
16    /// The geometry of this segment.
17    ///
18    /// This is a part of the input `crossable` geometry and either
19    /// starts or ends at the intersection point last yielded by
20    /// [`CrossingsIter`]. If it ends at the point (`at_left` is
21    /// `false`), then it is guaranteed to not contain any other
22    /// intersection point in its interior.
23    pub line: LineOrPoint<C::Scalar>,
24
25    /// Whether this is the first segment of the input line.
26    pub first_segment: bool,
27
28    /// Flag that is `true` if the next geom in the sequence overlaps
29    /// (i.e. intersects at more than one point) with this. Not
30    /// relevant and `false` if this is a point.
31    ///
32    /// Note that the overlapping segments may not always
33    /// _all_ get batched together. They may be reported as
34    /// one or more set of overlapping segments in an
35    /// arbitrary order.
36    pub has_overlap: bool,
37
38    /// Flag that is `true` if the `geom` starts at the intersection
39    /// point. Otherwise, it ends at the intersection point.
40    pub at_left: bool,
41
42    pub(super) segment: IMSegment<C>,
43}
44
45pub(crate) fn compare_crossings<X: Cross>(a: &Crossing<X>, b: &Crossing<X>) -> Ordering {
46    a.at_left.cmp(&b.at_left).then_with(|| {
47        let ord = a.segment.partial_cmp(&b.segment).unwrap();
48        if a.at_left {
49            ord
50        } else {
51            ord.reverse()
52        }
53    })
54}
55
56impl<C: Cross + Clone> Crossing<C> {
57    /// Convert `self` into a `Crossing` to return to user.
58    pub(super) fn from_segment(segment: &IMSegment<C>, event_ty: EventType) -> Crossing<C> {
59        Crossing {
60            cross: segment.cross_cloned(),
61            line: segment.geom(),
62            first_segment: segment.is_first_segment(),
63            has_overlap: segment.is_overlapping(),
64            at_left: event_ty == EventType::LineLeft,
65            segment: segment.clone(),
66        }
67    }
68}
69
70/// Iterator that yields all crossings.
71///
72/// Yields all end points, intersections and overlaps of a set of
73/// line-segments and points. Construct it by `collect`-ing an
74/// iterator of [`Cross`]. The implementation uses the
75/// [Bentley-Ottman] algorithm and runs in time O((n + k) log n) time;
76/// this is faster than a brute-force search for intersections across
77/// all pairs of input segments if k --- the number of intersections
78/// --- is small compared to n^2.
79///
80/// ## Usage
81///
82/// Construct from an iterator of any type implementing the
83/// [`Cross`] trait. Use the [`CrossingsIter::intersections`]
84/// method to access all segments that start or end at the last
85/// yielded point.
86///
87/// ```rust,ignore
88/// use geo::Line;
89/// use geo::sweep::CrossingsIter;
90/// use std::iter::FromIterator;
91/// let input = vec![
92///     Line::from([(1., 0.), (0., 1.)]),
93///     Line::from([(0., 0.75), (1., 0.25)]),
94///     Line::from([(0., 0.25), (1., 0.75)]),
95///     Line::from([(0., 0.), (1., 1.)]),
96/// ];
97/// let iter = CrossingsIter::<_>::from_iter(input);
98/// // 1 intersection point, and 8 end points
99/// assert_eq!(iter.count(), 9);
100/// ```
101///
102/// [Bentley-Ottman]: //en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
103pub(crate) struct CrossingsIter<C>
104where
105    C: Cross + Clone,
106{
107    sweep: Sweep<C>,
108    segments: Vec<Crossing<C>>,
109}
110
111impl<C> CrossingsIter<C>
112where
113    C: Cross + Clone,
114{
115    /// Faster sweep when input goemetries are known to not intersect except at
116    /// end-points.
117    pub fn new_simple<I: IntoIterator<Item = C>>(iter: I) -> Self {
118        Self::new_ex(iter, true)
119    }
120
121    /// Returns the segments that intersect the last point yielded by
122    /// the iterator.
123    pub fn intersections_mut(&mut self) -> &mut [Crossing<C>] {
124        &mut self.segments
125    }
126
127    pub fn intersections(&self) -> &[Crossing<C>] {
128        &self.segments
129    }
130
131    pub(crate) fn prev_active(&self, c: &Crossing<C>) -> Option<(LineOrPoint<C::Scalar>, C)> {
132        self.sweep
133            .with_prev_active(c, |s| (s.geom, s.cross.clone()))
134    }
135
136    fn new_ex<T: IntoIterator<Item = C>>(iter: T, is_simple: bool) -> Self {
137        let iter = iter.into_iter();
138        let size = {
139            let (min_size, max_size) = iter.size_hint();
140            max_size.unwrap_or(min_size)
141        };
142        let sweep = Sweep::new(iter, is_simple);
143        let segments = Vec::with_capacity(4 * size);
144        Self { sweep, segments }
145    }
146}
147
148impl<C> FromIterator<C> for CrossingsIter<C>
149where
150    C: Cross + Clone,
151{
152    fn from_iter<T: IntoIterator<Item = C>>(iter: T) -> Self {
153        Self::new_ex(iter, false)
154    }
155}
156
157impl<C> Iterator for CrossingsIter<C>
158where
159    C: Cross + Clone,
160{
161    type Item = Coord<C::Scalar>;
162
163    fn next(&mut self) -> Option<Self::Item> {
164        let segments = &mut self.segments;
165
166        segments.clear();
167        let mut last_point = self.sweep.peek_point();
168        debug!("pt: {last_point:?}");
169        while last_point == self.sweep.peek_point() && self.sweep.peek_point().is_some() {
170            last_point = self.sweep.next_event(|seg, ty| {
171                trace!(
172                    "cb: {seg:?} {ty:?} (crossable = {cross:?})",
173                    cross = seg.cross_cloned().line()
174                );
175                segments.push(Crossing::from_segment(seg, ty))
176            });
177        }
178
179        if segments.is_empty() {
180            None
181        } else {
182            last_point.map(|p| *p)
183        }
184    }
185}
186
187/// Iterator over all intersections of a collection of lines.
188///
189/// Yields tuples `(C, C, LineIntersection)` for each pair of input
190/// crossables that intersect or overlap. This is a drop-in
191/// replacement for computing [`LineIntersection`] over all pairs of
192/// the collection, but is typically more efficient. The
193/// implementation uses the [Bentley-Ottman] algorithm and runs in
194/// time O((n + k) log n) time; this is faster than a brute-force
195/// search for intersections across all pairs of input segments if k,
196/// the number of intersections is small compared to n^2.
197///
198/// ## Usage
199///
200/// Construct from an iterator of any type implementing the
201/// [`Cross`] trait. The geo-type [`Line`](crate::Line) implements this trait.
202/// See the trait documentation for more information on usage with
203/// custom types.
204///
205/// ```rust
206/// use geo::Line;
207/// use geo::sweep::Intersections;
208/// use std::iter::FromIterator;
209/// let input = vec![
210///     Line::from([(1., 0.), (0., 1.)]),
211///     Line::from([(0., 0.75), (1., 0.25)]),
212///     Line::from([(0., 0.25), (1., 0.75)]),
213///     Line::from([(0., 0.), (1., 1.)]),
214/// ];
215/// let iter = Intersections::<_>::from_iter(input);
216/// // All pairs intersect
217/// assert_eq!(iter.count(), 6);
218/// ```
219///
220/// [Bentley-Ottman]: //en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
221pub struct Intersections<C: Cross + Clone> {
222    inner: CrossingsIter<C>,
223    idx: usize,
224    jdx: usize,
225    is_overlap: bool,
226    pt: Option<Coord<C::Scalar>>,
227}
228
229impl<C> FromIterator<C> for Intersections<C>
230where
231    C: Cross + Clone,
232{
233    fn from_iter<T: IntoIterator<Item = C>>(iter: T) -> Self {
234        Self {
235            inner: FromIterator::from_iter(iter),
236            idx: 0,
237            jdx: 0,
238            is_overlap: false,
239            pt: None,
240        }
241    }
242}
243
244impl<C> Intersections<C>
245where
246    C: Cross + Clone,
247{
248    fn intersection(&mut self) -> Option<(C, C, LineIntersection<C::Scalar>)> {
249        let (si, sj) = {
250            let segments = self.inner.intersections();
251            (&segments[self.idx], &segments[self.jdx])
252        };
253        debug!(
254            "comparing intersection: [{iso}]",
255            iso = if self.is_overlap { "OVL" } else { "" }
256        );
257        for i in [si, sj] {
258            debug!(
259                "\t{geom:?} ({at_left}) [{ovl}] [{first}]",
260                geom = i.cross.line(),
261                first = if i.first_segment { "FIRST" } else { "" },
262                at_left = if i.at_left { "S" } else { "E" },
263                ovl = if i.has_overlap { "OVL" } else { "" },
264            );
265        }
266        // Ignore intersections that have already been processed
267        let should_compute = if self.is_overlap {
268            // For overlap, we only return intersection if both segments are the
269            // first, and both are at left.
270            debug_assert_eq!(si.at_left, sj.at_left);
271            si.at_left && (si.first_segment && sj.first_segment)
272        } else {
273            (!si.at_left || si.first_segment) && (!sj.at_left || sj.first_segment)
274        };
275
276        if should_compute {
277            let si = si.cross.clone();
278            let sj = sj.cross.clone();
279
280            let int = line_intersection(si.line().line(), sj.line().line())
281                .expect("line_intersection returned `None` disagreeing with `CrossingsIter`");
282
283            Some((si, sj, int))
284        } else {
285            None
286        }
287    }
288
289    fn step(&mut self) -> bool {
290        let seg_len = self.inner.intersections_mut().len();
291        if 1 + self.jdx < seg_len {
292            self.is_overlap =
293                self.is_overlap && self.inner.intersections_mut()[self.jdx].has_overlap;
294            self.jdx += 1;
295        } else {
296            self.idx += 1;
297            if 1 + self.idx >= seg_len {
298                loop {
299                    self.pt = self.inner.next();
300                    if self.pt.is_none() {
301                        return false;
302                    }
303                    if self.inner.intersections_mut().len() > 1 {
304                        break;
305                    }
306                }
307                self.idx = 0;
308            }
309            self.is_overlap = self.inner.intersections_mut()[self.idx].has_overlap;
310            self.jdx = self.idx + 1;
311        }
312        true
313    }
314}
315
316impl<C> Iterator for Intersections<C>
317where
318    C: Cross + Clone,
319{
320    type Item = (C, C, LineIntersection<C::Scalar>);
321
322    fn next(&mut self) -> Option<Self::Item> {
323        loop {
324            if !self.step() {
325                return None;
326            }
327            let it = self.intersection();
328            debug!("\t{it:?}", it = it.is_some());
329            if let Some(result) = it {
330                return Some(result);
331            }
332        }
333    }
334}
335
336#[cfg(test)]
337pub(super) mod tests {
338    use crate::Line;
339    use log::info;
340    use pretty_env_logger::env_logger;
341    use std::{io::Write, rc::Rc};
342
343    use super::*;
344
345    pub(super) fn init_log() {
346        let _ = env_logger::builder()
347            .format(|buf, record| writeln!(buf, "{} - {}", record.level(), record.args()))
348            .try_init();
349    }
350
351    #[test]
352    fn simple_iter() {
353        let input = vec![
354            Rc::from(Line::from([(1., 0.), (0., 1.)])),
355            Line::from([(0., 0.), (1., 1.)]).into(),
356        ];
357        let iter: CrossingsIter<_> = input.into_iter().collect();
358        assert_eq!(iter.count(), 5);
359    }
360
361    #[test]
362    fn overlap_intersect() {
363        init_log();
364
365        let input = vec![
366            Line::from([(0., 0.), (1., 1.)]),
367            [(1., 0.), (0., 1.)].into(),
368            [(0., 0.5), (1., 0.5)].into(),
369            [(-1., 0.5), (0.5, 0.5)].into(),
370            [(0.5, 0.5), (0.5, 0.5)].into(),
371            [(0., 0.), (0., 0.)].into(),
372        ];
373        // Intersections (by_idx):
374        // (0, 1), (0, 2), (0, 3), (0, 4), (0, 5),
375        // (1, 2), (1, 3), (1, 4),
376        // (2, 3)
377        let mut verify = 0;
378        for (i, l1) in input.iter().enumerate() {
379            for (j, l2) in input.iter().enumerate() {
380                if j <= i {
381                    continue;
382                }
383                if line_intersection(*l1, *l2).is_some() {
384                    let lp_a = LineOrPoint::from(*l1);
385                    let lp_b = LineOrPoint::from(*l2);
386                    eprintln!("{lp_a:?} intersects {lp_b:?}",);
387                    verify += 1;
388                }
389            }
390        }
391
392        let iter: Intersections<_> = input.iter().collect();
393        let count = iter
394            .inspect(|(a, b, _int)| {
395                let lp_a = LineOrPoint::from(**a);
396                let lp_b = LineOrPoint::from(**b);
397                eprintln!("{lp_a:?} intersects {lp_b:?}",);
398            })
399            .count();
400        assert_eq!(count, verify);
401    }
402
403    #[test]
404    #[ignore]
405    fn check_adhoc_crossings() {
406        init_log();
407
408        let input = vec![
409            Line::from([(0., 0.), (1., 1.)]),
410            [(1., 0.), (0., 1.)].into(),
411            [(0., 0.5), (1., 0.5)].into(),
412            [(-1., 0.5), (0.5, 0.5)].into(),
413            [(0.5, 0.5), (0.5, 0.5)].into(),
414            [(0., 0.), (0., 0.)].into(),
415        ];
416
417        let mut iter: CrossingsIter<_> = input.into_iter().collect();
418        while let Some(pt) = iter.next() {
419            info!("pt: {pt:?}");
420            iter.intersections().iter().for_each(|i| {
421                info!(
422                    "\t{geom:?} ({at_left}) {ovl}",
423                    geom = i.line,
424                    at_left = if i.at_left { "S" } else { "E" },
425                    ovl = if i.has_overlap { "[OVL] " } else { "" },
426                );
427            });
428        }
429    }
430}
geo/algorithm/sweep/iter.rs

geo/algorithm/sweep/
iter.rs
