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};
20use axiolid_guarantees::Sign;
21
22use crate::arc::{arc_orientation, reverse_arc_ring, validate_arc_ring, ArcRing};
23use crate::exact_arc::arrangement::{self, Raw};
24use crate::OverlayError;
25
26/// One piece of the subdivision: part of one or more input edges, running
27/// between two vertices with no other ring's boundary crossing it.
28#[derive(Debug, Clone, PartialEq)]
29pub struct ArrangementEdge {
30 /// Start vertex, an index into [`ArcArrangement::vertices`].
31 pub from: usize,
32 /// End vertex.
33 pub to: usize,
34 /// Bulge from `from` to `to`; `0` for a straight piece.
35 pub bulge: f64,
36 /// Rings whose boundary carries this piece.
37 pub sources: Vec<EdgeSource>,
38 /// Rings that contain both sides without carrying the piece, ascending.
39 inside: Vec<usize>,
40 /// Rings that carry the piece, ascending, each with whether it
41 /// contains the left side (else the right).
42 carriers: Vec<(usize, bool)>,
43}
44
45impl ArrangementEdge {
46 /// Whether ring `ring` contains the region on the left of the piece.
47 ///
48 /// Left and right are taken along `from -> to`. A ring whose boundary
49 /// carries the piece contains exactly one side.
50 pub fn inside_left(&self, ring: usize) -> bool {
51 self.contains(ring, true)
52 }
53
54 /// Whether ring `ring` contains the region on the right of the piece.
55 pub fn inside_right(&self, ring: usize) -> bool {
56 self.contains(ring, false)
57 }
58
59 fn contains(&self, ring: usize, left: bool) -> bool {
60 match self.carriers.iter().find(|c| c.0 == ring) {
61 Some(&(_, on_left)) => on_left == left,
62 None => self.inside.binary_search(&ring).is_ok(),
63 }
64 }
65
66 /// The rings containing one side of the piece, ascending: those that
67 /// hold both sides, and the carriers whose inside is that side. Kept
68 /// sparse (#292): a piece lies in a handful of rings, and a flag for
69 /// every ring on every piece made memory grow as pieces times rings.
70 pub(crate) fn holding(&self, left: bool, out: &mut Vec<usize>) {
71 out.clear();
72 out.extend_from_slice(&self.inside);
73 for &(ring, on_left) in &self.carriers {
74 if on_left == left {
75 let at = out.partition_point(|&r| r < ring);
76 out.insert(at, ring);
77 }
78 }
79 }
80}
81
82/// Where a piece of the subdivision came from.
83#[derive(Debug, Clone, Copy, PartialEq, Eq)]
84pub struct EdgeSource {
85 /// Index of the input ring.
86 pub ring: usize,
87 /// Index of the edge in that ring, as the caller passed it: the edge
88 /// leaving `vertices[edge]`.
89 pub edge: usize,
90 /// Whether the piece runs the same way as that input edge.
91 pub forward: bool,
92}
93
94/// One use of a piece in a region boundary.
95#[derive(Debug, Clone, Copy, PartialEq, Eq)]
96pub struct EdgeUse {
97 /// Index into [`ArcArrangement::edges`].
98 pub edge: usize,
99 /// Whether the boundary traverses the piece from `to` to `from`.
100 pub reversed: bool,
101}
102
103/// A region of the subdivision: an outer boundary and its holes.
104///
105/// The outer boundary runs counter-clockwise and each hole clockwise, so
106/// the region always lies to the left of its boundary.
107#[derive(Debug, Clone, PartialEq)]
108pub struct ArrangementRegion {
109 /// Outer boundary, in travel order.
110 pub outer: Vec<EdgeUse>,
111 /// Hole boundaries, in travel order.
112 pub holes: Vec<Vec<EdgeUse>>,
113}
114
115/// The plane cut by several simple arc rings.
116///
117/// Built once, queried many times: [`Self::regions`] selects any set of
118/// faces by a predicate over ring membership and links them into regions,
119/// all over the same vertices.
120pub struct ArcArrangement {
121 raw: Raw,
122 vertices: Vec<Point2>,
123 edges: Vec<ArrangementEdge>,
124 counts: Vec<usize>,
125}
126
127impl std::fmt::Debug for ArcArrangement {
128 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
129 f.debug_struct("ArcArrangement")
130 .field("vertices", &self.vertices)
131 .field("edges", &self.edges)
132 .finish_non_exhaustive()
133 }
134}
135
136impl ArcArrangement {
137 /// Subdivide the plane by `rings`.
138 ///
139 /// Each ring must pass [`validate_arc_ring`] and be simple; its winding
140 /// does not matter (each is read as the region it encloses). Rings may
141 /// cross, touch and share boundary pieces with each other.
142 ///
143 /// # Errors
144 ///
145 /// Any [`validate_arc_ring`] refusal, with the ring's own reason.
146 pub fn new(rings: &[ArcRing], tolerance: Tolerance) -> Result<Self, OverlayError> {
147 let mut oriented = Vec::with_capacity(rings.len());
148 let mut reversed = Vec::with_capacity(rings.len());
149 for ring in rings {
150 validate_arc_ring(ring, tolerance)?;
151 let flip = arc_orientation(ring) == Sign::Negative;
152 oriented.push(if flip {
153 reverse_arc_ring(ring)
154 } else {
155 ring.clone()
156 });
157 reversed.push(flip);
158 }
159 let mut raw = arrangement::build(&oriented)?;
160 let counts: Vec<usize> = rings.iter().map(|ring| ring.vertices.len()).collect();
161 let edges = raw
162 .edges
163 .iter_mut()
164 .map(|edge| ArrangementEdge {
165 from: edge.from,
166 to: edge.to,
167 bulge: edge.bulge,
168 sources: edge
169 .sources
170 .iter()
171 .map(|&(ring, index, forward)| {
172 // Reversal re-indexes edges: reversed edge `k`
173 // is original edge `n - 2 - k` (mod n), run the
174 // other way.
175 let n = counts[ring];
176 if reversed[ring] {
177 EdgeSource {
178 ring,
179 edge: (2 * n - 2 - index) % n,
180 forward: !forward,
181 }
182 } else {
183 EdgeSource {
184 ring,
185 edge: index,
186 forward,
187 }
188 }
189 })
190 .collect(),
191 inside: std::mem::take(&mut edge.inside),
192 carriers: edge
193 .sources
194 .iter()
195 .map(|&(ring, _, same)| (ring, same))
196 .collect(),
197 })
198 .collect();
199 Ok(Self {
200 vertices: raw.vertex_positions(),
201 raw,
202 edges,
203 counts,
204 })
205 }
206
207 /// Distinct vertices, each an exact point rounded once.
208 pub fn vertices(&self) -> &[Point2] {
209 &self.vertices
210 }
211
212 /// Pieces of the subdivision.
213 pub fn edges(&self) -> &[ArrangementEdge] {
214 &self.edges
215 }
216
217 /// Number of input rings.
218 pub fn ring_count(&self) -> usize {
219 self.counts.len()
220 }
221
222 /// The regions where `inside` holds, as linked boundaries.
223 ///
224 /// `inside` receives one flag per input ring (whether a point lies in
225 /// that ring) and says whether the point belongs to the wanted set. A
226 /// piece bounds the set exactly when `inside` differs across it; it is
227 /// traversed so that the set lies on its left.
228 ///
229 /// # Errors
230 ///
231 /// [`OverlayError::SelfIntersection`] if the boundary cannot be linked,
232 /// which simple input rings cannot produce.
233 pub fn regions(
234 &self,
235 inside: impl Fn(&[bool]) -> bool,
236 ) -> Result<Vec<ArrangementRegion>, OverlayError> {
237 // One buffer of flags, set from a side's rings and cleared after.
238 let mut flags = vec![false; self.counts.len()];
239 self.regions_holding(|rings| {
240 for &ring in rings {
241 flags[ring] = true;
242 }
243 let answer = inside(&flags);
244 for &ring in rings {
245 flags[ring] = false;
246 }
247 answer
248 })
249 }
250
251 /// As [`Self::regions`], with `inside` given the rings that contain a
252 /// point, ascending, instead of a flag for every ring: deciding a
253 /// piece costs the rings it lies in, not every ring (#292).
254 pub(crate) fn regions_holding(
255 &self,
256 mut inside: impl FnMut(&[usize]) -> bool,
257 ) -> Result<Vec<ArrangementRegion>, OverlayError> {
258 let mut rings = Vec::new();
259 let keep: Vec<Option<bool>> = self
260 .edges
261 .iter()
262 .map(|edge| {
263 edge.holding(true, &mut rings);
264 let left = inside(&rings);
265 edge.holding(false, &mut rings);
266 match (left, inside(&rings)) {
267 (true, false) => Some(false),
268 (false, true) => Some(true),
269 _ => None,
270 }
271 })
272 .collect();
273 let uses = |ring: Vec<(usize, bool)>| -> Vec<EdgeUse> {
274 ring.into_iter()
275 .map(|(edge, reversed)| EdgeUse { edge, reversed })
276 .collect()
277 };
278 Ok(self
279 .raw
280 .regions(&keep)?
281 .into_iter()
282 .map(|(outer, holes)| ArrangementRegion {
283 outer: uses(outer),
284 holes: holes.into_iter().map(uses).collect(),
285 })
286 .collect())
287 }
288
289 /// A region boundary as an [`ArcRing`] over the rounded vertices.
290 pub fn ring(&self, uses: &[EdgeUse]) -> ArcRing {
291 ArcRing::new(
292 uses.iter()
293 .map(|u| {
294 let edge = &self.edges[u.edge];
295 let (from, bulge) = if u.reversed {
296 (edge.to, -edge.bulge)
297 } else {
298 (edge.from, edge.bulge)
299 };
300 crate::arc::ArcVertex::bulged(self.vertices[from], bulge)
301 })
302 .collect(),
303 )
304 }
305}