i_overlay/split/
solver_tree.rs

1use alloc::vec::Vec;
2use i_tree::ExpiredVal;
3use crate::geom::line_range::LineRange;
4use crate::geom::x_segment::XSegment;
5use crate::segm::segment::Segment;
6use crate::segm::winding::WindingCount;
7use crate::split::snap_radius::SnapRadius;
8use crate::split::solver::SplitSolver;
9use i_tree::seg::exp::{SegExpCollection, SegRange};
10use i_tree::seg::tree::SegExpTree;
11use crate::core::solver::Solver;
12
13#[derive(Debug, Clone, Copy)]
14struct IdSegment {
15    id: usize,
16    x_segment: XSegment,
17}
18
19impl ExpiredVal<i32> for IdSegment {
20    #[inline]
21    fn expiration(&self) -> i32 {
22        self.x_segment.b.x
23    }
24}
25
26impl SplitSolver {
27    pub(super) fn tree_split<C: WindingCount>(
28        &mut self,
29        snap_radius: SnapRadius,
30        segments: &mut Vec<Segment<C>>,
31        solver: &Solver
32    ) -> bool {
33        let range: SegRange<i32> = segments.ver_range().into();
34        let mut tree: SegExpTree<i32, i32, IdSegment> = if let Some(tree) = SegExpTree::new(range) {
35            tree
36        } else {
37            return self.list_split(snap_radius, segments, solver);
38        };
39
40        let mut reusable_buffer = Vec::new();
41
42        let mut need_to_fix = true;
43        let mut any_intersection = false;
44
45        let mut snap_radius = snap_radius;
46
47        while need_to_fix && segments.len() > 2 {
48            need_to_fix = false;
49            self.marks.clear();
50
51            let radius = snap_radius.radius();
52
53            for (i, si) in segments.iter().enumerate() {
54                let time = si.x_segment.a.x;
55                let si_range = si.x_segment.y_range().into();
56                for sj in tree.iter_by_range(si_range, time) {
57                    let (this_index, scan_index, this, scan) = if si.x_segment < sj.x_segment {
58                        (i, sj.id, &si.x_segment, &sj.x_segment)
59                    } else {
60                        (sj.id, i, &sj.x_segment, &si.x_segment)
61                    };
62
63                    let is_round = SplitSolver::cross(
64                        this_index,
65                        scan_index,
66                        this,
67                        scan,
68                        &mut self.marks,
69                        radius,
70                    );
71
72                    need_to_fix = is_round || need_to_fix;
73                }
74
75                tree.insert_by_range(si_range, si.id_segment(i));
76            }
77
78            if self.marks.is_empty() {
79                return any_intersection;
80            }
81
82            any_intersection = true;
83            tree.clear();
84
85            self.apply(segments, &mut reusable_buffer, solver);
86
87            snap_radius.increment();
88        }
89
90        any_intersection
91    }
92}
93
94impl From<LineRange> for SegRange<i32> {
95    #[inline]
96    fn from(value: LineRange) -> Self {
97        Self {
98            min: value.min,
99            max: value.max,
100        }
101    }
102}
103
104trait VerticalRange {
105    fn ver_range(&self) -> LineRange;
106}
107
108impl<C: Send> VerticalRange for Vec<Segment<C>> {
109    fn ver_range(&self) -> LineRange {
110        let mut min_y = self[0].x_segment.a.y;
111        let mut max_y = min_y;
112
113        for edge in self.iter() {
114            min_y = min_y.min(edge.x_segment.a.y);
115            max_y = max_y.max(edge.x_segment.a.y);
116            min_y = min_y.min(edge.x_segment.b.y);
117            max_y = max_y.max(edge.x_segment.b.y);
118        }
119
120        LineRange {
121            min: min_y,
122            max: max_y,
123        }
124    }
125}
126
127impl<C: Send> Segment<C> {
128    #[inline]
129    fn id_segment(&self, id: usize) -> IdSegment {
130        IdSegment {
131            id,
132            x_segment: self.x_segment,
133        }
134    }
135}
i_overlay/split/solver_tree.rs

i_overlay/split/
solver_tree.rs
