axiolid_overlay/arrangement.rs
1//! Planar subdivision by several arc rings at once (#120).
2//!
3//! [`arc_overlay`](crate::arc_overlay) answers one boolean of two rings.
4//! A stepped or stacked solid needs more: the section changes with height,
5//! and every face of the solid (each wall, ledge and cap) is bounded by
6//! pieces of the same boundaries. [`ArcArrangement`] cuts the plane by all
7//! the rings at once, once, and records for each piece which rings contain
8//! the region on either side. Any region built from those pieces then
9//! shares vertices with every other region by index, not by two roundings
10//! happening to agree.
11//!
12//! # Exact, then rounded once
13//!
14//! Where boundaries cross, which pieces coincide, and which ring contains
15//! what are exact decisions (ADR 0070). Crossing points are rounded to
16//! `f64` once, into [`ArcArrangement::vertices`], and every piece refers to
17//! them by index.
18
19use axiolid_core::{Point2, Tolerance};
20
21use crate::arc::{arc_ring_area, reverse_arc_ring, validate_arc_ring, ArcRing};
22use crate::exact_arc::arrangement::{self, Raw};
23use crate::OverlayError;
24
25/// One piece of the subdivision: part of one or more input edges, running
26/// between two vertices with no other ring's boundary crossing it.
27#[derive(Debug, Clone, PartialEq)]
28pub struct ArrangementEdge {
29 /// Start vertex, an index into [`ArcArrangement::vertices`].
30 pub from: usize,
31 /// End vertex.
32 pub to: usize,
33 /// Bulge from `from` to `to`; `0` for a straight piece.
34 pub bulge: f64,
35 /// Rings whose boundary carries this piece.
36 pub sources: Vec<EdgeSource>,
37 left: Vec<bool>,
38 right: Vec<bool>,
39}
40
41impl ArrangementEdge {
42 /// Whether ring `ring` contains the region on the left of the piece.
43 ///
44 /// Left and right are taken along `from -> to`. A ring whose boundary
45 /// carries the piece contains exactly one side.
46 pub fn inside_left(&self, ring: usize) -> bool {
47 self.left.get(ring).copied().unwrap_or(false)
48 }
49
50 /// Whether ring `ring` contains the region on the right of the piece.
51 pub fn inside_right(&self, ring: usize) -> bool {
52 self.right.get(ring).copied().unwrap_or(false)
53 }
54}
55
56/// Where a piece of the subdivision came from.
57#[derive(Debug, Clone, Copy, PartialEq, Eq)]
58pub struct EdgeSource {
59 /// Index of the input ring.
60 pub ring: usize,
61 /// Index of the edge in that ring, as the caller passed it: the edge
62 /// leaving `vertices[edge]`.
63 pub edge: usize,
64 /// Whether the piece runs the same way as that input edge.
65 pub forward: bool,
66}
67
68/// One use of a piece in a region boundary.
69#[derive(Debug, Clone, Copy, PartialEq, Eq)]
70pub struct EdgeUse {
71 /// Index into [`ArcArrangement::edges`].
72 pub edge: usize,
73 /// Whether the boundary traverses the piece from `to` to `from`.
74 pub reversed: bool,
75}
76
77/// A region of the subdivision: an outer boundary and its holes.
78///
79/// The outer boundary runs counter-clockwise and each hole clockwise, so
80/// the region always lies to the left of its boundary.
81#[derive(Debug, Clone, PartialEq)]
82pub struct ArrangementRegion {
83 /// Outer boundary, in travel order.
84 pub outer: Vec<EdgeUse>,
85 /// Hole boundaries, in travel order.
86 pub holes: Vec<Vec<EdgeUse>>,
87}
88
89/// The plane cut by several simple arc rings.
90///
91/// Built once, queried many times: [`Self::regions`] selects any set of
92/// faces by a predicate over ring membership and links them into regions,
93/// all over the same vertices.
94pub struct ArcArrangement {
95 raw: Raw,
96 vertices: Vec<Point2>,
97 edges: Vec<ArrangementEdge>,
98 counts: Vec<usize>,
99}
100
101impl std::fmt::Debug for ArcArrangement {
102 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
103 f.debug_struct("ArcArrangement")
104 .field("vertices", &self.vertices)
105 .field("edges", &self.edges)
106 .finish_non_exhaustive()
107 }
108}
109
110impl ArcArrangement {
111 /// Subdivide the plane by `rings`.
112 ///
113 /// Each ring must pass [`validate_arc_ring`] and be simple; its winding
114 /// does not matter (each is read as the region it encloses). Rings may
115 /// cross, touch and share boundary pieces with each other.
116 ///
117 /// # Errors
118 ///
119 /// Any [`validate_arc_ring`] refusal, with the ring's own reason.
120 pub fn new(rings: &[ArcRing], tolerance: Tolerance) -> Result<Self, OverlayError> {
121 let mut oriented = Vec::with_capacity(rings.len());
122 let mut reversed = Vec::with_capacity(rings.len());
123 for ring in rings {
124 validate_arc_ring(ring, tolerance)?;
125 let flip = arc_ring_area(ring) < 0.0;
126 oriented.push(if flip {
127 reverse_arc_ring(ring)
128 } else {
129 ring.clone()
130 });
131 reversed.push(flip);
132 }
133 let raw = arrangement::build(&oriented);
134 let counts: Vec<usize> = rings.iter().map(|ring| ring.vertices.len()).collect();
135 let edges = raw
136 .edges
137 .iter()
138 .map(|edge| ArrangementEdge {
139 from: edge.from,
140 to: edge.to,
141 bulge: edge.bulge,
142 sources: edge
143 .sources
144 .iter()
145 .map(|&(ring, index, forward)| {
146 // Reversal re-indexes edges: reversed edge `k`
147 // is original edge `n - 2 - k` (mod n), run the
148 // other way.
149 let n = counts[ring];
150 if reversed[ring] {
151 EdgeSource {
152 ring,
153 edge: (2 * n - 2 - index) % n,
154 forward: !forward,
155 }
156 } else {
157 EdgeSource {
158 ring,
159 edge: index,
160 forward,
161 }
162 }
163 })
164 .collect(),
165 left: edge.sides(counts.len(), true),
166 right: edge.sides(counts.len(), false),
167 })
168 .collect();
169 Ok(Self {
170 vertices: raw.vertex_positions(),
171 raw,
172 edges,
173 counts,
174 })
175 }
176
177 /// Distinct vertices, each an exact point rounded once.
178 pub fn vertices(&self) -> &[Point2] {
179 &self.vertices
180 }
181
182 /// Pieces of the subdivision.
183 pub fn edges(&self) -> &[ArrangementEdge] {
184 &self.edges
185 }
186
187 /// Number of input rings.
188 pub fn ring_count(&self) -> usize {
189 self.counts.len()
190 }
191
192 /// The regions where `inside` holds, as linked boundaries.
193 ///
194 /// `inside` receives one flag per input ring (whether a point lies in
195 /// that ring) and says whether the point belongs to the wanted set. A
196 /// piece bounds the set exactly when `inside` differs across it; it is
197 /// traversed so that the set lies on its left.
198 ///
199 /// # Errors
200 ///
201 /// [`OverlayError::SelfIntersection`] if the boundary cannot be linked,
202 /// which simple input rings cannot produce.
203 pub fn regions(
204 &self,
205 inside: impl Fn(&[bool]) -> bool,
206 ) -> Result<Vec<ArrangementRegion>, OverlayError> {
207 let keep: Vec<Option<bool>> = self
208 .edges
209 .iter()
210 .map(|edge| match (inside(&edge.left), inside(&edge.right)) {
211 (true, false) => Some(false),
212 (false, true) => Some(true),
213 _ => None,
214 })
215 .collect();
216 let uses = |ring: Vec<(usize, bool)>| -> Vec<EdgeUse> {
217 ring.into_iter()
218 .map(|(edge, reversed)| EdgeUse { edge, reversed })
219 .collect()
220 };
221 Ok(self
222 .raw
223 .regions(&keep)?
224 .into_iter()
225 .map(|(outer, holes)| ArrangementRegion {
226 outer: uses(outer),
227 holes: holes.into_iter().map(uses).collect(),
228 })
229 .collect())
230 }
231
232 /// A region boundary as an [`ArcRing`] over the rounded vertices.
233 pub fn ring(&self, uses: &[EdgeUse]) -> ArcRing {
234 ArcRing::new(
235 uses.iter()
236 .map(|u| {
237 let edge = &self.edges[u.edge];
238 let (from, bulge) = if u.reversed {
239 (edge.to, -edge.bulge)
240 } else {
241 (edge.from, edge.bulge)
242 };
243 crate::arc::ArcVertex::bulged(self.vertices[from], bulge)
244 })
245 .collect(),
246 )
247 }
248}