i_overlay/split/
solver_tree.rs

1use crate::core::solver::Solver;
2use crate::geom::line_range::LineRange;
3use crate::geom::x_segment::XSegment;
4use crate::segm::segment::Segment;
5use crate::segm::winding::WindingCount;
6use crate::split::snap_radius::SnapRadius;
7use crate::split::solver::SplitSolver;
8use alloc::vec::Vec;
9use i_tree::ExpiredVal;
10use i_tree::seg::exp::{SegExpCollection, SegRange};
11use i_tree::seg::tree::SegExpTree;
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 =
64                        SplitSolver::cross(this_index, scan_index, this, scan, &mut self.marks, radius);
65
66                    need_to_fix = is_round || need_to_fix;
67                }
68
69                tree.insert_by_range(si_range, si.id_segment(i));
70            }
71
72            if self.marks.is_empty() {
73                return any_intersection;
74            }
75
76            any_intersection = true;
77            tree.clear();
78
79            self.apply(segments, &mut reusable_buffer, solver);
80
81            snap_radius.increment();
82        }
83
84        any_intersection
85    }
86}
87
88impl From<LineRange> for SegRange<i32> {
89    #[inline]
90    fn from(value: LineRange) -> Self {
91        Self {
92            min: value.min,
93            max: value.max,
94        }
95    }
96}
97
98trait VerticalRange {
99    fn ver_range(&self) -> LineRange;
100}
101
102impl<C: Send> VerticalRange for Vec<Segment<C>> {
103    fn ver_range(&self) -> LineRange {
104        let mut min_y = self[0].x_segment.a.y;
105        let mut max_y = min_y;
106
107        for edge in self.iter() {
108            min_y = min_y.min(edge.x_segment.a.y);
109            max_y = max_y.max(edge.x_segment.a.y);
110            min_y = min_y.min(edge.x_segment.b.y);
111            max_y = max_y.max(edge.x_segment.b.y);
112        }
113
114        LineRange {
115            min: min_y,
116            max: max_y,
117        }
118    }
119}
120
121impl<C: Send> Segment<C> {
122    #[inline]
123    fn id_segment(&self, id: usize) -> IdSegment {
124        IdSegment {
125            id,
126            x_segment: self.x_segment,
127        }
128    }
129}
i_overlay/split/solver_tree.rs

i_overlay/split/
solver_tree.rs
