geo 0.33.0

Geospatial primitives and algorithms
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

use crate::geometry::*;
use crate::intersects::has_disjoint_bboxes;
use crate::monotone_chain::MonotoneChainSegment;
use crate::{BoundingRect, GeoNum, Intersects};

macro_rules! intersects_MonotoneChainSegment {
    ( $k:ty) => {
        impl<'a: 'caller, 'caller, T> $crate::Intersects<$k> for MonotoneChainSegment<'a, T>
        where
            $k: BoundingRect<T>,
            LineString<T>: Intersects<$k>,
            Line<T>: Intersects<$k>,
            Coord<T>: Intersects<$k>,
            T: GeoNum,
        {
            fn intersects(&self, rhs: &$k) -> bool {
                // PERF: this recursivee function recalculates the
                //  bounding box of rhs on each loop
                if has_disjoint_bboxes(self, rhs) {
                    return false;
                }

                match self.ls().len() {
                    0 => false,
                    1 => self.ls()[0].intersects(rhs),
                    2 => {
                        // PERF: One potential speed optimization here is to use specialized function
                        // with pre-requisite of bounding box intersection.
                        // e.g. Line intersect Line could become just the orientation checks
                        Line::<T>::new(self.ls()[0], self.ls()[1]).intersects(rhs)
                    }
                    _ => {
                        if let (l, Some(r)) = self.divide() {
                            l.intersects(rhs) || r.intersects(rhs)
                        } else {
                            unreachable!("divide() should always return Some for n > 2");
                        }
                    }
                }
            }
        }
    };
}

intersects_MonotoneChainSegment!(Coord<T>);
symmetric_intersects_impl!(Coord<T>, MonotoneChainSegment<'a, T>);

intersects_MonotoneChainSegment!(Line<T>);
symmetric_intersects_impl!(Line<T>, MonotoneChainSegment<'a, T>);

impl<'a, T> Intersects<MonotoneChainSegment<'a, T>> for MonotoneChainSegment<'a, T>
where
    T: GeoNum,
{
    fn intersects(&self, rhs: &MonotoneChainSegment<'a, T>) -> bool {
        if has_disjoint_bboxes(self, rhs) {
            return false;
        }
        // handle degenerate cases
        if self.ls().len() == 1 {
            return self.ls()[0].intersects(rhs);
        }
        if rhs.ls().len() == 1 {
            return rhs.ls()[0].intersects(self);
        }

        // recurse with binary split on both sides
        match (self.divide(), rhs.divide()) {
            ((a, Some(b)), (c, Some(d))) => {
                a.intersects(&c) || a.intersects(&d) || b.intersects(&c) || b.intersects(&d)
            }
            ((a, Some(b)), (_c, None)) => a.intersects(rhs) || b.intersects(rhs),
            ((_a, None), (c, Some(d))) => self.intersects(&c) || self.intersects(&d),

            ((a, None), (c, None)) => Line::<T>::new(a.ls()[0], a.ls()[1])
                .intersects(&Line::<T>::new(c.ls()[0], c.ls()[1])),
        }
    }
}