axiolid_exact_arrangement/
trace.rs

1//! Rings of labelled half-edges, outer boundaries and their holes.
2//!
3//! The caller says which pieces bound a class (a region of one label) and on
4//! which side the class lies: a half-edge is a piece with a direction and the
5//! class on its left. [`trace`] closes them into rings and nests them:
6//!
7//! 1. Cycles: at a vertex the half-edge that follows an incoming one is the
8//!    first boundary of the class met turning clockwise from the way it came
9//!    (the pieces at a vertex are ordered by [`Arrangement::fan`]), so a
10//!    vertex where a region pinches is resolved per fan.
11//! 2. Each cycle is an outer ring or a hole by the exact turn at its extreme
12//!    vertex.
13//! 3. Vertices that the caller does not need are dropped when they lie
14//!    strictly between their neighbours on a line.
15//! 4. Each hole belongs to the innermost outer ring that holds it, decided
16//!    with exact point location.
17
18use std::collections::{BTreeMap, BTreeSet};
19
20use axiolid_contracts::{ExecutionOptions, GeomError, GeomResult, Sign};
21
22use crate::arrangement::{Arrangement, PairBudget, PieceId, VertexId};
23use crate::points::{inconsistent, ExactPoints, Location, PointId, RingBox};
24
25/// A piece with a direction: from `ends[0]` to `ends[1]` when `forward`.
26#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
27pub struct HalfEdge {
28    /// The piece.
29    pub piece: PieceId,
30    /// Whether it runs from `ends[0]` to `ends[1]`.
31    pub forward: bool,
32}
33
34/// A closed boundary of a class.
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub struct TracedRing {
37    /// The half-edges of the cycle, before vertices were dropped.
38    pub half_edges: Vec<HalfEdge>,
39    /// The vertices kept, in the order of the cycle.
40    pub vertices: Vec<VertexId>,
41    /// Whether the ring is a hole (clockwise in the frame) rather than an
42    /// outer boundary.
43    pub hole: bool,
44}
45
46/// An outer ring and its holes, as indices into the rings of [`trace`].
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct TracedRegion {
49    /// The outer ring.
50    pub outer: usize,
51    /// The holes, ascending.
52    pub holes: Vec<usize>,
53}
54
55/// The eight lexicographic orders tried for the extreme vertex of a ring:
56/// which axis is major, and whether each runs ascending.
57const EXTREME_ORDERS: [(usize, bool, bool); 8] = [
58    (0, true, true),
59    (0, true, false),
60    (0, false, true),
61    (0, false, false),
62    (1, true, true),
63    (1, true, false),
64    (1, false, true),
65    (1, false, false),
66];
67
68/// Whether the cycle is an outer boundary (counter-clockwise in the frame),
69/// by the exact turn at its extreme vertex.
70///
71/// The minimum of a lexicographic order is a convex corner. The first order
72/// whose minimum the ring visits once decides; a ring that touches itself at
73/// every extreme (a weakly simple ring) is refused.
74fn is_outer(arrangement: &Arrangement, exact: &ExactPoints, ring: &[usize]) -> GeomResult<bool> {
75    let point = |index: usize| arrangement.vertices[ring[index % ring.len()]].point;
76    for (major, major_up, minor_up) in EXTREME_ORDERS {
77        let order = |left: usize, right: usize| -> GeomResult<std::cmp::Ordering> {
78            let (a, b) = (point(left), point(right));
79            let first = exact.compare(a, b, major)?;
80            let first = if major_up { first } else { first.reverse() };
81            if first.is_ne() {
82                return Ok(first);
83            }
84            let second = exact.compare(a, b, 1 - major)?;
85            Ok(if minor_up { second } else { second.reverse() })
86        };
87        let mut smallest = 0;
88        for index in 1..ring.len() {
89            if order(index, smallest)?.is_lt() {
90                smallest = index;
91            }
92        }
93        let mut visits = 0;
94        for index in 0..ring.len() {
95            if order(index, smallest)?.is_eq() {
96                visits += 1;
97            }
98        }
99        if visits != 1 {
100            continue;
101        }
102        let count = ring.len();
103        return match exact.orient(
104            point(smallest + count - 1),
105            point(smallest),
106            point(smallest + 1),
107        )? {
108            Sign::Positive => Ok(true),
109            Sign::Negative => Ok(false),
110            _ => Err(GeomError::Degenerate(
111                "a ring has a spike at its extreme vertex".into(),
112            )),
113        };
114    }
115    Err(GeomError::Degenerate(
116        "a ring visits every extreme vertex twice".into(),
117    ))
118}
119
120/// Drop vertices that lie strictly between their neighbours on a line and
121/// that `keep` does not ask for; a spike is refused.
122fn simplify(
123    arrangement: &Arrangement,
124    exact: &ExactPoints,
125    ring: &mut Vec<usize>,
126    keep: &dyn Fn(VertexId) -> bool,
127    options: &ExecutionOptions,
128) -> GeomResult<()> {
129    let collapsed = || GeomError::Degenerate("a ring collapsed under simplification".into());
130    let mut index = 0usize;
131    let mut clean = 0usize;
132    while clean < ring.len() {
133        options.check_cancelled()?;
134        if ring.len() < 3 {
135            return Err(collapsed());
136        }
137        let at = index % ring.len();
138        let (previous, vertex, next) = (
139            ring[(at + ring.len() - 1) % ring.len()],
140            ring[at],
141            ring[(at + 1) % ring.len()],
142        );
143        let point = |vertex: usize| arrangement.vertices[vertex].point;
144        if exact.orient(point(previous), point(vertex), point(next))? != Sign::Zero {
145            clean += 1;
146            index = at + 1;
147            continue;
148        }
149        if !exact.strictly_between(point(previous), point(vertex), point(next))? {
150            return Err(GeomError::Degenerate(
151                "a ring has a zero-width spike".into(),
152            ));
153        }
154        if keep(VertexId(vertex)) {
155            clean += 1;
156            index = at + 1;
157            continue;
158        }
159        ring.remove(at);
160        clean = 0;
161        index = (at + ring.len().saturating_sub(1)) % ring.len().max(1);
162    }
163    if ring.len() < 3 {
164        return Err(collapsed());
165    }
166    Ok(())
167}
168
169/// Whether `inner` lies in `outer`: its vertices not on the boundary agree.
170/// `Degenerate` when they do not, or when none decides.
171fn within(exact: &ExactPoints, inner: &[PointId], outer: &[PointId]) -> GeomResult<bool> {
172    let (mut inside, mut outside) = (false, false);
173    for &node in inner {
174        match exact.locate(node, outer)? {
175            Location::Inside => inside = true,
176            Location::Outside => outside = true,
177            Location::Boundary => {}
178        }
179    }
180    match (inside, outside) {
181        (true, false) => Ok(true),
182        (false, true) => Ok(false),
183        _ => Err(GeomError::Degenerate(
184            "rings cross or touch without a deciding vertex".into(),
185        )),
186    }
187}
188
189/// Close `half_edges`, which all carry one class on their left, into rings
190/// and nest them.
191///
192/// `keep` says which vertices a ring must keep even where it runs straight
193/// through them, typically those where other boundary meets. Each pair of
194/// rings whose containment is decided counts against `budget`. Returns the
195/// rings in the order of their first half-edge by `(from, to)` vertex, and the
196/// regions, one per outer ring in that order.
197pub fn trace(
198    points: &ExactPoints,
199    arrangement: &Arrangement,
200    half_edges: &[HalfEdge],
201    keep: &dyn Fn(VertexId) -> bool,
202    budget: &mut PairBudget,
203    options: &ExecutionOptions,
204) -> GeomResult<(Vec<TracedRing>, Vec<TracedRegion>)> {
205    let mut by_ends = BTreeMap::<(usize, usize), HalfEdge>::new();
206    for &half_edge in half_edges {
207        let ends = arrangement.pieces[half_edge.piece.0].ends;
208        let (from, to) = if half_edge.forward {
209            (ends[0].0, ends[1].0)
210        } else {
211            (ends[1].0, ends[0].0)
212        };
213        by_ends.insert((from, to), half_edge);
214    }
215    let mut fans = BTreeMap::<usize, Vec<(PieceId, bool)>>::new();
216    let mut seen = BTreeSet::<(usize, usize)>::new();
217    let mut cycles = Vec::<(Vec<(usize, usize)>, Vec<usize>, bool)>::new();
218    for &start in by_ends.keys() {
219        if seen.contains(&start) {
220            continue;
221        }
222        let mut edges = Vec::new();
223        let mut ring = Vec::new();
224        let mut edge = start;
225        loop {
226            options.check_cancelled()?;
227            seen.insert(edge);
228            edges.push(edge);
229            ring.push(edge.0);
230            let after = next_vertex(points, arrangement, &mut fans, &by_ends, edge)?;
231            edge = (edge.1, after);
232            if edge == start {
233                break;
234            }
235            if !by_ends.contains_key(&edge) || seen.contains(&edge) || ring.len() > by_ends.len() {
236                return Err(inconsistent());
237            }
238        }
239        let outer = is_outer(arrangement, points, &ring)?;
240        simplify(arrangement, points, &mut ring, keep, options)?;
241        cycles.push((edges, ring, outer));
242    }
243
244    let rings: Vec<Vec<PointId>> = cycles
245        .iter()
246        .map(|(_, ring, _)| {
247            ring.iter()
248                .map(|&vertex| arrangement.vertices[vertex].point)
249                .collect()
250        })
251        .collect();
252    let boxes: Vec<RingBox> = rings.iter().map(|ring| points.ring_box(ring)).collect();
253    let mut owner = vec![None::<usize>; cycles.len()];
254    for (hole, (_, _, outer)) in cycles.iter().enumerate() {
255        if *outer {
256            continue;
257        }
258        let mut containers = Vec::new();
259        for (candidate, (_, _, other_outer)) in cycles.iter().enumerate() {
260            if !other_outer || !boxes[hole].possibly_within(&boxes[candidate]) {
261                continue;
262            }
263            options.check_cancelled()?;
264            budget.count()?;
265            if within(points, &rings[hole], &rings[candidate])? {
266                containers.push(candidate);
267            }
268        }
269        let mut innermost = Vec::new();
270        for &candidate in &containers {
271            let mut holds_all = true;
272            for &other in &containers {
273                if other == candidate {
274                    continue;
275                }
276                budget.count()?;
277                if !within(points, &rings[candidate], &rings[other])? {
278                    holds_all = false;
279                    break;
280                }
281            }
282            if holds_all {
283                innermost.push(candidate);
284            }
285        }
286        match innermost.as_slice() {
287            [only] => owner[hole] = Some(*only),
288            _ => {
289                return Err(GeomError::Degenerate(
290                    "a hole has no single innermost outer boundary".into(),
291                ))
292            }
293        }
294    }
295    if owner
296        .iter()
297        .zip(&cycles)
298        .any(|(owned, (_, _, outer))| !outer && owned.is_none())
299    {
300        return Err(GeomError::Degenerate(
301            "a component has a hole but no outer boundary".into(),
302        ));
303    }
304    let regions = cycles
305        .iter()
306        .enumerate()
307        .filter(|(_, (_, _, outer))| *outer)
308        .map(|(index, _)| TracedRegion {
309            outer: index,
310            holes: owner
311                .iter()
312                .enumerate()
313                .filter(|(_, owned)| **owned == Some(index))
314                .map(|(hole, _)| hole)
315                .collect(),
316        })
317        .collect();
318    let rings = cycles
319        .into_iter()
320        .map(|(edges, ring, outer)| TracedRing {
321            half_edges: edges.iter().map(|ends| by_ends[ends]).collect(),
322            vertices: ring.into_iter().map(VertexId).collect(),
323            hole: !outer,
324        })
325        .collect();
326    Ok((rings, regions))
327}
328
329/// Refuse a class that winds more than once at some point.
330///
331/// Every point has winding 0 or 1 for the class when each outer ring lies in
332/// as many outer rings as holes of the class, and each hole in one more
333/// outer ring than holes. Counts each ring's containment in every other ring
334/// whose box can hold it; each decided containment counts against `budget`.
335pub fn check_winding(
336    points: &ExactPoints,
337    arrangement: &Arrangement,
338    rings: &[TracedRing],
339    regions: &[TracedRegion],
340    budget: &mut PairBudget,
341    options: &ExecutionOptions,
342) -> GeomResult<()> {
343    if regions.iter().any(|region| {
344        rings[region.outer].hole || region.holes.iter().any(|&hole| !rings[hole].hole)
345    }) {
346        return Err(inconsistent());
347    }
348    let outlines: Vec<Vec<PointId>> = rings
349        .iter()
350        .map(|ring| {
351            ring.vertices
352                .iter()
353                .map(|vertex| arrangement.vertices[vertex.0].point)
354                .collect()
355        })
356        .collect();
357    let boxes: Vec<RingBox> = outlines.iter().map(|ring| points.ring_box(ring)).collect();
358    for (index, ring) in rings.iter().enumerate() {
359        let (mut outers, mut holes) = (0i64, 0i64);
360        for (other, container) in rings.iter().enumerate() {
361            if other == index || !boxes[index].possibly_within(&boxes[other]) {
362                continue;
363            }
364            options.check_cancelled()?;
365            budget.count()?;
366            if within(points, &outlines[index], &outlines[other])? {
367                if container.hole {
368                    holes += 1;
369                } else {
370                    outers += 1;
371                }
372            }
373        }
374        if outers - holes != i64::from(ring.hole) {
375            return Err(GeomError::Degenerate(
376                "a class winds twice after snap rounding".into(),
377            ));
378        }
379    }
380    Ok(())
381}
382
383/// The vertex the boundary leaves `edge.1` for, after it came along `edge`:
384/// the first half-edge met turning clockwise from the way it came.
385fn next_vertex(
386    points: &ExactPoints,
387    arrangement: &Arrangement,
388    fans: &mut BTreeMap<usize, Vec<(PieceId, bool)>>,
389    half_edges: &BTreeMap<(usize, usize), HalfEdge>,
390    (from, at): (usize, usize),
391) -> GeomResult<usize> {
392    let fan = match fans.entry(at) {
393        std::collections::btree_map::Entry::Occupied(known) => known.into_mut(),
394        std::collections::btree_map::Entry::Vacant(vacant) => {
395            vacant.insert(arrangement.fan(points, VertexId(at))?)
396        }
397    };
398    let to_of = |&(piece, forward): &(PieceId, bool)| {
399        arrangement.pieces[piece.0].ends[usize::from(forward)].0
400    };
401    let index = fan
402        .iter()
403        .position(|spoke| to_of(spoke) == from)
404        .ok_or_else(inconsistent)?;
405    for step in 1..=fan.len() {
406        let to = to_of(&fan[(index + fan.len() - step) % fan.len()]);
407        if half_edges.contains_key(&(at, to)) {
408            return Ok(to);
409        }
410    }
411    Err(inconsistent())
412}
axiolid_exact_arrangement/trace.rs

axiolid_exact_arrangement/
trace.rs
