i_overlay/string/
split.rs

1use alloc::vec::Vec;
2use i_float::int::point::IntPoint;
3use i_shape::int::path::ContourExtension;
4use i_shape::int::shape::IntContour;
5use i_shape::util::reserve::Reserve;
6
7pub(super) trait Split {
8    fn split_loops(
9        self,
10        min_area: u64,
11        contour_buffer: &mut IntContour,
12        bin_store: &mut BinStore,
13    ) -> Vec<Self>
14    where
15        Self: Sized;
16}
17
18impl Split for IntContour {
19    fn split_loops(
20        self,
21        min_area: u64,
22        contour_buffer: &mut IntContour,
23        bin_store: &mut BinStore,
24    ) -> Vec<Self> {
25        if self.is_empty() {
26            return Vec::new();
27        }
28        contour_buffer.reserve_capacity(self.len());
29        contour_buffer.clear();
30
31        bin_store.init(&self);
32
33        let mut result: Vec<IntContour> = Vec::with_capacity(16);
34
35        for point in self {
36            let next_pos = contour_buffer.len() + 1;
37            let pos = bin_store.insert_if_not_exist(point, next_pos);
38            if pos < contour_buffer.len() {
39                // found a loop
40                let tail_len = contour_buffer.len() - pos;
41                if tail_len < 2 {
42                    // tail is too small
43                    contour_buffer.truncate(pos);
44                } else {
45                    let mut tail = contour_buffer.split_off(pos);
46                    tail.push(point);
47                    if tail.validate_area(min_area) {
48                        result.push(tail);
49                    }
50                }
51            } else {
52                contour_buffer.push(point);
53            }
54        }
55
56        if contour_buffer.len() > 2 {
57            result.push(contour_buffer.as_slice().to_vec());
58        }
59
60        result
61    }
62}
63
64#[derive(Debug, Clone, Copy)]
65struct PointItem {
66    point: IntPoint,
67    pos: usize,
68}
69
70#[derive(Debug, Clone, Copy)]
71struct Bin {
72    offset: usize,
73    data: usize,
74}
75
76pub(super) struct BinStore {
77    mask: u32,
78    bins: Vec<Bin>,
79    items: Vec<PointItem>,
80}
81
82impl BinStore {
83    pub(super) fn new() -> Self {
84        Self {
85            mask: 0,
86            bins: Vec::new(),
87            items: Vec::new(),
88        }
89    }
90
91    fn init(&mut self, contour: &IntContour) {
92        let log = contour.len().ilog2().saturating_sub(4).clamp(1, 30);
93        let bins_count = (1 << log) as usize;
94
95        self.bins.clear();
96        self.bins.resize(bins_count, Bin { offset: 0, data: 0 });
97
98        self.items.clear();
99        self.items.resize(
100            contour.len(),
101            PointItem {
102                point: IntPoint::EMPTY,
103                pos: 0,
104            },
105        );
106
107        self.mask = bins_count.wrapping_sub(1) as u32;
108
109        for &p in contour.iter() {
110            let index = self.bin_index(p);
111            unsafe {
112                // SAFETY: bin_index comes from bin_index(point); mask == bins_count - 1 with bins sized to bins_count, so this lookup is always in-bounds.
113                self.bins.get_unchecked_mut(index).data += 1
114            };
115        }
116
117        let mut offset = 0;
118        for bin in self.bins.iter_mut() {
119            let next_offset = offset + bin.data;
120            *bin = Bin {
121                offset,
122                data: offset,
123            };
124            offset = next_offset;
125        }
126    }
127
128    #[inline]
129    fn insert_if_not_exist(&mut self, point: IntPoint, pos: usize) -> usize {
130        let index = self.bin_index(point);
131        let bin = unsafe {
132            // SAFETY: insert_if_not_exist only touches bins within the pre-sized array; bin_index shares the same invariant.
133            self.bins.get_unchecked_mut(index)
134        };
135        let start = bin.offset;
136        let end = bin.data;
137        for i in start..end {
138            let item = unsafe {
139                // SAFETY: items is pre-resized to contour.len(); start..end stays inside that range while we probe, so the mutable borrow is valid.
140                self.items.get_unchecked_mut(i)
141            };
142            if item.point == point {
143                return item.pos;
144            }
145        }
146        bin.data = end + 1;
147        unsafe {
148            // SAFETY: end < items.len() because we grow data one slot at a time inside the reserved window.
149            *self.items.get_unchecked_mut(end) = PointItem { point, pos }
150        }
151
152        usize::MAX
153    }
154
155    #[inline]
156    fn bin_index(&self, p: IntPoint) -> usize {
157        let x = p.x.unsigned_abs();
158        let y = p.y.unsigned_abs();
159        let hash = x.wrapping_mul(31) ^ y.wrapping_mul(17);
160        (hash & self.mask) as usize
161    }
162}
163
164trait ValidateArea {
165    fn validate_area(&self, min_area: u64) -> bool;
166}
167
168impl ValidateArea for IntContour {
169    #[inline]
170    fn validate_area(&self, min_area: u64) -> bool {
171        if min_area == 0 {
172            return true;
173        }
174        let abs_area = self.unsafe_area().unsigned_abs() >> 1;
175        abs_area < min_area
176    }
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182    use crate::i_shape::int::path::IntPath;
183    use alloc::vec;
184
185    #[test]
186    fn test_empty_path() {
187        let path: IntPath = vec![];
188        let mut contour: IntContour = Vec::new();
189        let mut bin_store = BinStore::new();
190        let result = path.split_loops(0, &mut contour, &mut bin_store);
191        assert_eq!(result, vec![] as Vec<IntPath>);
192    }
193
194    #[test]
195    fn test_single_point() {
196        let path = vec![IntPoint::new(0, 0)];
197        let mut contour: IntContour = Vec::new();
198        let mut bin_store = BinStore::new();
199        let result = path.split_loops(0, &mut contour, &mut bin_store);
200        assert!(result.is_empty());
201    }
202
203    #[test]
204    fn test_two_points() {
205        let path = vec![IntPoint::new(0, 0), IntPoint::new(1, 1)];
206        let mut contour: IntContour = Vec::new();
207        let mut bin_store = BinStore::new();
208        let result = path.split_loops(0, &mut contour, &mut bin_store);
209        assert!(result.is_empty());
210    }
211
212    #[test]
213    fn test_no_repeated_points() {
214        let path = vec![
215            IntPoint::new(0, 0),
216            IntPoint::new(0, 1),
217            IntPoint::new(1, 1),
218            IntPoint::new(1, 0),
219        ];
220
221        let mut contour: IntContour = Vec::new();
222        let mut bin_store = BinStore::new();
223        let result = path.clone().split_loops(0, &mut contour, &mut bin_store);
224        assert_eq!(result, vec![path]);
225    }
226
227    #[test]
228    fn test_2_loops_0() {
229        let path = vec![
230            IntPoint::new(0, 0),
231            IntPoint::new(1, 1),
232            IntPoint::new(2, 0),
233            IntPoint::new(3, 1),
234            IntPoint::new(4, 0),
235            IntPoint::new(3, -1),
236            IntPoint::new(2, 0), // same point
237            IntPoint::new(1, -1),
238        ];
239
240        let mut contour: IntContour = Vec::new();
241        let mut bin_store = BinStore::new();
242        let result = path.split_loops(0, &mut contour, &mut bin_store);
243        assert_eq!(result.len(), 2);
244        assert_eq!(
245            result[0],
246            [
247                IntPoint::new(3, 1),
248                IntPoint::new(4, 0),
249                IntPoint::new(3, -1),
250                IntPoint::new(2, 0),
251            ]
252            .to_vec()
253        );
254        assert_eq!(
255            result[1],
256            [
257                IntPoint::new(0, 0),
258                IntPoint::new(1, 1),
259                IntPoint::new(2, 0),
260                IntPoint::new(1, -1),
261            ]
262            .to_vec()
263        );
264    }
265
266    #[test]
267    fn test_2_loops_1() {
268        let path = vec![
269            IntPoint::new(0, 0),
270            IntPoint::new(1, 1),
271            IntPoint::new(2, 0),
272            IntPoint::new(3, 1),
273            IntPoint::new(3, -1),
274            IntPoint::new(2, 0), // same point
275            IntPoint::new(1, -1),
276        ];
277
278        let mut contour: IntContour = Vec::new();
279        let mut bin_store = BinStore::new();
280        let result = path.split_loops(0, &mut contour, &mut bin_store);
281        assert_eq!(result.len(), 2);
282        assert_eq!(
283            result[0],
284            [
285                IntPoint::new(3, 1),
286                IntPoint::new(3, -1),
287                IntPoint::new(2, 0),
288            ]
289            .to_vec()
290        );
291        assert_eq!(
292            result[1],
293            [
294                IntPoint::new(0, 0),
295                IntPoint::new(1, 1),
296                IntPoint::new(2, 0),
297                IntPoint::new(1, -1),
298            ]
299            .to_vec()
300        );
301    }
302
303    #[test]
304    fn test_2_loops_with_tails() {
305        let path = vec![
306            IntPoint::new(-1, 0),
307            IntPoint::new(0, 0),
308            IntPoint::new(1, 1),
309            IntPoint::new(2, 0),
310            IntPoint::new(3, 1),
311            IntPoint::new(4, 0),
312            IntPoint::new(5, 0),
313            IntPoint::new(4, 0),
314            IntPoint::new(3, -1),
315            IntPoint::new(2, 0), // same point
316            IntPoint::new(1, -1),
317            IntPoint::new(0, 0),
318        ];
319
320        let mut contour: IntContour = Vec::new();
321        let mut bin_store = BinStore::new();
322        let result = path.split_loops(0, &mut contour, &mut bin_store);
323        assert_eq!(result.len(), 2);
324        assert_eq!(
325            result[0],
326            [
327                IntPoint::new(3, 1),
328                IntPoint::new(4, 0),
329                IntPoint::new(3, -1),
330                IntPoint::new(2, 0),
331            ]
332            .to_vec()
333        );
334        assert_eq!(
335            result[1],
336            [
337                IntPoint::new(1, 1),
338                IntPoint::new(2, 0),
339                IntPoint::new(1, -1),
340                IntPoint::new(0, 0),
341            ]
342            .to_vec()
343        );
344    }
345
346    #[test]
347    fn test_single_loop() {
348        let path = vec![
349            IntPoint::new(0, 0),
350            IntPoint::new(1, 1),
351            IntPoint::new(2, 0),
352            IntPoint::new(0, 0), // same point, forms a loop
353        ];
354
355        let mut contour: IntContour = Vec::new();
356        let mut bin_store = BinStore::new();
357        let result = path.split_loops(0, &mut contour, &mut bin_store);
358        assert_eq!(result.len(), 1);
359        assert_eq!(
360            result[0],
361            [
362                IntPoint::new(1, 1),
363                IntPoint::new(2, 0),
364                IntPoint::new(0, 0),
365            ]
366            .to_vec()
367        );
368    }
369
370    #[test]
371    fn test_cross() {
372        let path = vec![
373            IntPoint::new(-2, -1),
374            IntPoint::new(-2, 1),
375            IntPoint::new(0, 0),
376            IntPoint::new(-1, 2),
377            IntPoint::new(1, 2),
378            IntPoint::new(0, 0), // same point, forms a loop
379            IntPoint::new(2, 1),
380            IntPoint::new(2, -1),
381            IntPoint::new(0, 0), // same point, forms a loop
382            IntPoint::new(1, -2),
383            IntPoint::new(-1, -2),
384            IntPoint::new(0, 0), // same point, forms a loop
385        ];
386
387        let mut contour: IntContour = Vec::new();
388        let mut bin_store = BinStore::new();
389        let result = path.split_loops(0, &mut contour, &mut bin_store);
390        assert_eq!(result.len(), 4);
391        assert_eq!(
392            result[0],
393            [
394                IntPoint::new(-1, 2),
395                IntPoint::new(1, 2),
396                IntPoint::new(0, 0),
397            ]
398            .to_vec()
399        );
400        assert_eq!(
401            result[1],
402            [
403                IntPoint::new(2, 1),
404                IntPoint::new(2, -1),
405                IntPoint::new(0, 0),
406            ]
407            .to_vec()
408        );
409        assert_eq!(
410            result[2],
411            [
412                IntPoint::new(1, -2),
413                IntPoint::new(-1, -2),
414                IntPoint::new(0, 0),
415            ]
416            .to_vec()
417        );
418        assert_eq!(
419            result[3],
420            [
421                IntPoint::new(-2, -1),
422                IntPoint::new(-2, 1),
423                IntPoint::new(0, 0),
424            ]
425            .to_vec()
426        );
427    }
428}
i_overlay/string/split.rs

i_overlay/string/
split.rs
