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

use crate::build::builder::{GraphBuilder, GraphNode};
use crate::core::solver::Solver;
use crate::geom::end::End;
use crate::segm::winding::WindingCount;
use alloc::vec::Vec;
use i_key_sort::sort::two_keys::TwoKeysSort;

impl<C: WindingCount, N: GraphNode> GraphBuilder<C, N> {
    pub(super) fn build_nodes_and_connect_links(&mut self, solver: &Solver) {
        let n = self.links.len();
        if n == 0 {
            return;
        }

        self.build_ends(solver);

        self.nodes.clear();
        self.nodes.reserve(n);

        let mut ai = 0;
        let mut bi = 0;
        let mut indices = Vec::with_capacity(4);

        while ai < n || bi < n {
            let (a_cnt, next_ai, a_point) = if ai < n {
                let point = self.links[ai].a.point;
                let mut end = ai + 1;
                while end < n && self.links[end].a.point == point {
                    end += 1;
                }
                (end - ai, end, Some(point))
            } else {
                (0, ai, None)
            };

            let (b_cnt, next_bi, b_point) = if bi < n {
                let point = self.ends[bi].point;
                let mut end = bi + 1;
                while end < n && self.ends[end].point == point {
                    end += 1;
                }
                (end - bi, end, Some(point))
            } else {
                (0, bi, None)
            };

            let (consume_a, consume_b) = match (a_point, b_point) {
                (Some(a), Some(b)) if a == b => (a_cnt, b_cnt),
                (Some(a), Some(b)) if a < b => (a_cnt, 0),
                (Some(_), Some(_)) => (0, b_cnt),
                (Some(_), None) => (a_cnt, 0),
                (None, Some(_)) => (0, b_cnt),
                (None, None) => break,
            };

            let node_id = self.nodes.len();

            if consume_a > 0 {
                let start = ai;
                let end = ai + consume_a;
                for idx in start..end {
                    self.links[idx].a.id = node_id;
                    indices.push(idx);
                }
                ai = next_ai;
            }

            if consume_b > 0 {
                let start = bi;
                let end = bi + consume_b;
                for idx in start..end {
                    let link_idx = self.ends[idx].index;
                    indices.push(link_idx);
                    self.links[link_idx].b.id = node_id;
                }
                bi = next_bi;
            }

            debug_assert!(!indices.is_empty());
            self.nodes.push(N::with_indices(indices.as_slice()));
            indices.clear();
        }
    }

    #[inline]
    fn build_ends(&mut self, solver: &Solver) {
        self.ends.clear();
        self.ends.reserve(self.links.len());
        for (i, link) in self.links.iter().enumerate() {
            self.ends.push(End {
                index: i,
                point: link.b.point,
            });
        }
        self.ends
            .sort_by_two_keys(solver.is_parallel_sort_allowed(), |e| e.point.x, |e| e.point.y);
    }
}