i_overlay 6.0.0

Boolean Operations for 2D Polygons: Supports intersection, union, difference, xor, and self-intersections for all polygon varieties.
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

use crate::build::sweep::{FillHandler, FillStrategy, SweepRunner};
use crate::core::link::OverlayLink;
use crate::core::solver::Solver;
use crate::geom::end::End;
use crate::geom::id_point::IdPoint;
use crate::segm::segment::{NONE, Segment, SegmentFill};
use crate::segm::winding::WindingCount;
use alloc::vec::Vec;
use core::ops::ControlFlow;
use i_shape::util::reserve::Reserve;

pub(super) trait InclusionFilterStrategy {
    fn is_included(fill: SegmentFill) -> bool;
}

pub(crate) struct StoreFillsHandler<'a> {
    fills: &'a mut Vec<SegmentFill>,
}

impl<'a> StoreFillsHandler<'a> {
    #[inline]
    pub(crate) fn new(fills: &'a mut Vec<SegmentFill>) -> Self {
        Self { fills }
    }
}

impl<C> FillHandler<C> for StoreFillsHandler<'_> {
    type Output = ();

    #[inline(always)]
    fn handle(&mut self, index: usize, _segment: &Segment<C>, fill: SegmentFill) -> ControlFlow<()> {
        // fills is pre-allocated to segments.len() and index is guaranteed
        // to be in range by the sweep algorithm
        unsafe { *self.fills.get_unchecked_mut(index) = fill };
        ControlFlow::Continue(())
    }

    #[inline(always)]
    fn finalize(self) {}
}

pub(crate) trait GraphNode {
    fn with_indices(indices: &[usize]) -> Self;
}

pub(crate) struct GraphBuilder<C, N> {
    sweep_runner: SweepRunner<C>,
    pub(super) links: Vec<OverlayLink>,
    pub(super) nodes: Vec<N>,
    pub(super) fills: Vec<SegmentFill>,
    pub(super) ends: Vec<End>,
}

impl<C: WindingCount, N: GraphNode> GraphBuilder<C, N> {
    #[inline]
    pub(crate) fn new() -> Self {
        Self {
            sweep_runner: SweepRunner::new(),
            links: Vec::new(),
            nodes: Vec::new(),
            fills: Vec::new(),
            ends: Vec::new(),
        }
    }

    #[inline]
    pub(super) fn build_fills_with_strategy<F: FillStrategy<C>>(
        &mut self,
        solver: &Solver,
        segments: &[Segment<C>],
    ) {
        self.fills.resize(segments.len(), NONE);
        self.sweep_runner
            .run::<F, _>(solver, segments, StoreFillsHandler::new(&mut self.fills));
    }

    #[inline]
    pub(super) fn build_links_by_filter<F: InclusionFilterStrategy>(&mut self, segments: &[Segment<C>]) {
        self.links.clear();
        self.links.reserve_capacity(segments.len());

        for (segment, &fill) in segments.iter().zip(&self.fills) {
            if !F::is_included(fill) {
                continue;
            }
            self.links.push(OverlayLink::new(
                IdPoint::new(0, segment.x_segment.a),
                IdPoint::new(0, segment.x_segment.b),
                fill,
            ));
        }
    }

    #[inline]
    pub(super) fn build_links_all(&mut self, segments: &[Segment<C>]) {
        self.links.clear();
        self.links.reserve_capacity(segments.len());

        for (segment, &fill) in segments.iter().zip(&self.fills) {
            self.links.push(OverlayLink::new(
                IdPoint::new(0, segment.x_segment.a),
                IdPoint::new(0, segment.x_segment.b),
                fill,
            ));
        }
    }
}