boolygon 0.1.0

Boolean operations on polygons.
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

use std::{collections::BTreeSet, fmt::Debug};

use crate::{
    clipper::{Clipper, Operator},
    graph::Graph,
    Geometry, IsClose, Shape,
};

/// Determines the role of a [`Node`] during the clipping process.
#[derive(Debug, Clone, Copy)]
pub(super) enum Role {
    /// The node belongs to the subject shape.
    Subject(usize),
    /// The node belongs to the clip shape.
    Clip(usize),
}

impl Role {
    pub(super) fn is_subject(&self) -> bool {
        matches!(self, Role::Subject(_))
    }
}

/// A vertex and its metadata inside a graph.
#[derive(Debug)]
pub(super) struct Node<T>
where
    T: Geometry,
{
    /// The vertex being represented by this node.
    pub(super) vertex: T::Vertex,
    /// The role of the node.
    pub(super) role: Role,
    /// The index of the node following this one.
    pub(super) next: usize,
    /// Vertices from the oposite shape located at the same point.
    pub(super) siblings: BTreeSet<usize>,
}

impl<T> Node<T>
where
    T: Geometry,
{
    /// Returns true if, and only if, this node has siblings.
    pub(super) fn is_intersection(&self) -> bool {
        !self.siblings.is_empty()
    }
}

/// An iterator of [`Node`] that yields consecutive items from a [`Graph`] which vertex belongs to
/// the output boundary.
pub(super) struct NodeIterator<'a, Op, T>
where
    T: Geometry,
{
    pub(super) clipper: &'a Clipper<Op, Shape<T>, Shape<T>, <T::Vertex as IsClose>::Tolerance>,
    pub(super) graph: &'a mut Graph<T>,
    pub(super) next: Option<usize>,
}

impl<Op, T> Iterator for NodeIterator<'_, Op, T>
where
    T: Geometry,
    T::Vertex: Copy + PartialEq,
    Op: Operator<T>,
{
    type Item = Node<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let node = self.graph.nodes[self.next?].take()?;
        self.next = self.clipper.successor(self.graph, &node);
        Some(node)
    }
}

/// A wrapper iterator around [`NodeIterator`] that stops yielding vertices when the boundary forms
/// a closed shape.
pub(super) struct BoundaryCollector<'a, Op, T>
where
    T: Geometry,
{
    iterator: NodeIterator<'a, Op, T>,
    terminal: Vec<usize>,
    closed: bool,
}

impl<'a, Op, T> From<NodeIterator<'a, Op, T>> for BoundaryCollector<'a, Op, T>
where
    T: Geometry,
{
    fn from(iterator: NodeIterator<'a, Op, T>) -> Self {
        Self {
            iterator,
            terminal: Vec::new(),
            closed: false,
        }
    }
}

impl<Op, T> Iterator for &mut BoundaryCollector<'_, Op, T>
where
    T: Geometry,
    T::Vertex: Copy + PartialEq,
    Op: Operator<T>,
{
    type Item = Node<T>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.closed {
            return None;
        }

        let current = self.iterator.next?;
        let node = self.iterator.next()?;

        if self.terminal.is_empty() {
            self.terminal
                .extend(node.siblings.iter().copied().chain([current]));
        } else if let Some(next) = self.iterator.next {
            self.closed = self.terminal.contains(&next);
        } else {
            self.closed = node
                .siblings
                .iter()
                .filter_map(|&sibling| self.iterator.graph.nodes[sibling].as_ref())
                .map(|sibling| sibling.next)
                .chain([node.next])
                .any(|node| self.terminal.contains(&node));
        };

        Some(node)
    }
}

impl<Op, T> BoundaryCollector<'_, Op, T>
where
    T: Geometry,
    T::Vertex: Copy + PartialEq,
    Op: Operator<T>,
{
    /// Returns a vector of vertices if, and only if, the resulting boundary forms a closed shape.
    pub(super) fn collect(mut self) -> Option<Vec<T::Vertex>> {
        let vertices = self.map(|node| node.vertex).collect();
        self.closed.then_some(vertices)
    }
}