geo/algorithm/relate/geomgraph/index/
rstar_edge_set_intersector.rs

1use super::super::Edge;
2use super::{EdgeSetIntersector, SegmentIntersector};
3use crate::GeoFloat;
4
5use std::cell::RefCell;
6use std::rc::Rc;
7
8use rstar::RTree;
9
10pub(crate) struct RstarEdgeSetIntersector;
11
12impl RstarEdgeSetIntersector {
13    pub fn new() -> Self {
14        RstarEdgeSetIntersector
15    }
16}
17
18struct Segment<'a, F: GeoFloat + rstar::RTreeNum> {
19    i: usize,
20    edge: &'a RefCell<Edge<F>>,
21    envelope: rstar::AABB<crate::Coord<F>>,
22}
23
24impl<'a, F> Segment<'a, F>
25where
26    F: GeoFloat + rstar::RTreeNum,
27{
28    fn new(i: usize, edge: &'a RefCell<Edge<F>>) -> Self {
29        use crate::rstar::RTreeObject;
30        let p1 = edge.borrow().coords()[i];
31        let p2 = edge.borrow().coords()[i + 1];
32        Self {
33            i,
34            edge,
35            envelope: rstar::AABB::from_corners(p1, p2),
36        }
37    }
38}
39
40impl<'a, F> rstar::RTreeObject for Segment<'a, F>
41where
42    F: GeoFloat + rstar::RTreeNum,
43{
44    type Envelope = rstar::AABB<crate::Coord<F>>;
45
46    fn envelope(&self) -> Self::Envelope {
47        self.envelope
48    }
49}
50
51impl<F> EdgeSetIntersector<F> for RstarEdgeSetIntersector
52where
53    F: GeoFloat + rstar::RTreeNum,
54{
55    fn compute_intersections_within_set(
56        &mut self,
57        edges: &[Rc<RefCell<Edge<F>>>],
58        check_for_self_intersecting_edges: bool,
59        segment_intersector: &mut SegmentIntersector<F>,
60    ) {
61        let segments: Vec<Segment<F>> = edges
62            .iter()
63            .flat_map(|edge| {
64                let start_of_final_segment: usize = RefCell::borrow(edge).coords().len() - 1;
65                (0..start_of_final_segment).map(|segment_i| Segment::new(segment_i, edge))
66            })
67            .collect();
68        let tree = RTree::bulk_load(segments);
69
70        for (edge0, edge1) in tree.intersection_candidates_with_other_tree(&tree) {
71            if check_for_self_intersecting_edges || edge0.edge.as_ptr() != edge1.edge.as_ptr() {
72                segment_intersector.add_intersections(edge0.edge, edge0.i, edge1.edge, edge1.i);
73            }
74        }
75    }
76
77    fn compute_intersections_between_sets(
78        &mut self,
79        edges0: &[Rc<RefCell<Edge<F>>>],
80        edges1: &[Rc<RefCell<Edge<F>>>],
81        segment_intersector: &mut SegmentIntersector<F>,
82    ) {
83        let segments0: Vec<Segment<F>> = edges0
84            .iter()
85            .flat_map(|edge| {
86                let start_of_final_segment: usize = RefCell::borrow(edge).coords().len() - 1;
87                (0..start_of_final_segment).map(|segment_i| Segment::new(segment_i, edge))
88            })
89            .collect();
90        let tree_0 = RTree::bulk_load(segments0);
91
92        let segments1: Vec<Segment<F>> = edges1
93            .iter()
94            .flat_map(|edge| {
95                let start_of_final_segment: usize = RefCell::borrow(edge).coords().len() - 1;
96                (0..start_of_final_segment).map(|segment_i| Segment::new(segment_i, edge))
97            })
98            .collect();
99        let tree_1 = RTree::bulk_load(segments1);
100
101        for (edge0, edge1) in tree_0.intersection_candidates_with_other_tree(&tree_1) {
102            segment_intersector.add_intersections(edge0.edge, edge0.i, edge1.edge, edge1.i);
103        }
104    }
105}
geo/algorithm/relate/geomgraph/index/rstar_edge_set_intersector.rs

geo/algorithm/relate/geomgraph/index/
rstar_edge_set_intersector.rs
