axiolid_exact_arrangement/
faces.rs

1//! The faces of the complement of an arrangement.
2//!
3//! The pieces of an [`Arrangement`] cut the plane into faces. Each piece has
4//! a face on either side, and [`faces`] numbers them:
5//!
6//! 1. Contours: a half-edge is a piece with a direction and its face on the
7//!    left. At a vertex the half-edge that follows an incoming one is the
8//!    first met turning clockwise from the way it came (the rule of
9//!    [`trace`](crate::trace)), so the half-edges fall into orbits, one per
10//!    boundary walk. A dangling piece is walked on both its sides.
11//! 2. Components: the pieces join into connected components. The extreme
12//!    vertex of a component (smallest by `x`, then `y`) is a convex corner,
13//!    so exactly one wedge between consecutive pieces there is wider than a
14//!    half turn. The contour that leaves along the piece that starts that
15//!    wedge has the unbounded side of the component on its left: it is the
16//!    component's outer contour.
17//! 3. Faces: every other contour bounds one bounded face of its component,
18//!    numbered from 1 by the smallest half-edge of the contour.
19//! 4. Nesting: a component that lies inside a bounded face of another one
20//!    has that face on the sides of its outer contour. Of the faces that
21//!    hold its extreme vertex the innermost wins, which is the one whose
22//!    component has the greatest extreme vertex, because a nested component
23//!    lies strictly inside the walk around the face.
24//!
25//! A piece with one face on both sides is dangling, or part of a tree.
26
27use axiolid_contracts::{ExecutionOptions, GeomError, GeomResult, Sign};
28
29use crate::arrangement::{Arrangement, PairBudget, PieceId, VertexId};
30use crate::points::{inconsistent, ExactPoints, Location, PointId, RingBox};
31
32/// A face of the complement of an [`Arrangement`].
33#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
34pub struct FaceId(pub usize);
35
36/// The face on each side of every piece.
37#[derive(Debug, Clone, PartialEq, Eq)]
38pub struct Faces {
39    /// Per piece, the faces left and right of `ends[0]` to `ends[1]`.
40    sides: Vec<[FaceId; 2]>,
41    count: usize,
42}
43
44impl Faces {
45    /// The unbounded face.
46    pub const UNBOUNDED: FaceId = FaceId(0);
47
48    /// The number of faces, the unbounded one included.
49    pub fn count(&self) -> usize {
50        self.count
51    }
52
53    /// The face left of `piece`, running from `ends[0]` to `ends[1]`; left
54    /// is in the points' frame (see [`ExactPoints`]), so it is the right in
55    /// `(x, y)` for a store with a negative frame sign.
56    pub fn left(&self, piece: PieceId) -> FaceId {
57        self.sides[piece.0][0]
58    }
59
60    /// The face right of `piece`, running from `ends[0]` to `ends[1]`; right
61    /// is in the points' frame, as for [`Faces::left`].
62    pub fn right(&self, piece: PieceId) -> FaceId {
63        self.sides[piece.0][1]
64    }
65}
66
67/// The half-edge of `piece` that runs from `ends[0]` when `forward`:
68/// `2 * piece`, plus one for the other direction.
69fn half_edge(piece: PieceId, forward: bool) -> usize {
70    2 * piece.0 + usize::from(!forward)
71}
72
73/// Find the root of `item` in a union-find forest.
74fn find(parent: &mut [usize], mut item: usize) -> usize {
75    while parent[item] != item {
76        parent[item] = parent[parent[item]];
77        item = parent[item];
78    }
79    item
80}
81
82/// Number the faces of the complement of `arrangement`.
83///
84/// Face 0 is the unbounded face. Bounded faces are numbered from 1,
85/// ascending by the smallest half-edge (`2 * piece`, plus one for the
86/// backward direction) of their boundary walk. With `V` vertices, `E`
87/// pieces and `C` connected components, the count `F` satisfies
88/// `V - E + F = 1 + C`.
89///
90/// Each containment decided between components counts one pair against
91/// `budget`; cancellation is checked per vertex. A component whose extreme
92/// vertex does not decide its outer contour is `Degenerate`.
93pub fn faces(
94    points: &ExactPoints,
95    arrangement: &Arrangement,
96    budget: &mut PairBudget,
97    options: &ExecutionOptions,
98) -> GeomResult<Faces> {
99    let piece_count = arrangement.pieces.len();
100    let mut next = vec![usize::MAX; 2 * piece_count];
101    let mut fans = Vec::with_capacity(arrangement.vertices.len());
102    for vertex in 0..arrangement.vertices.len() {
103        options.check_cancelled()?;
104        let fan = arrangement.fan(points, VertexId(vertex))?;
105        for (index, &(piece, forward)) in fan.iter().enumerate() {
106            // The piece arrives here along the twin of the one that leaves,
107            // and the boundary goes on along the spoke clockwise of it.
108            let (turn, turn_forward) = fan[(index + fan.len() - 1) % fan.len()];
109            next[half_edge(piece, forward) ^ 1] = half_edge(turn, turn_forward);
110        }
111        fans.push(fan);
112    }
113    let tail = |half: usize| {
114        let ends = arrangement.pieces[half / 2].ends;
115        ends[usize::from(half % 2 == 1)].0
116    };
117
118    // Contours, numbered by their smallest half-edge.
119    let mut contour_of = vec![usize::MAX; 2 * piece_count];
120    let mut contours = Vec::<Vec<usize>>::new();
121    for start in 0..2 * piece_count {
122        if contour_of[start] != usize::MAX {
123            continue;
124        }
125        let mut walk = Vec::new();
126        let mut half = start;
127        loop {
128            contour_of[half] = contours.len();
129            walk.push(half);
130            half = next[half];
131            if half == start {
132                break;
133            }
134            if half == usize::MAX || contour_of[half] != usize::MAX {
135                return Err(inconsistent());
136            }
137        }
138        contours.push(walk);
139    }
140
141    // Components, each with its extreme vertex.
142    let mut parent: Vec<usize> = (0..arrangement.vertices.len()).collect();
143    for piece in &arrangement.pieces {
144        let (low, high) = (
145            find(&mut parent, piece.ends[0].0),
146            find(&mut parent, piece.ends[1].0),
147        );
148        parent[low.max(high)] = low.min(high);
149    }
150    let mut extreme = vec![usize::MAX; arrangement.vertices.len()];
151    for (vertex, fan) in fans.iter().enumerate() {
152        if fan.is_empty() {
153            continue;
154        }
155        let root = find(&mut parent, vertex);
156        let best = extreme[root];
157        if best == usize::MAX
158            || points
159                .lexicographic(
160                    arrangement.vertices[vertex].point,
161                    arrangement.vertices[best].point,
162                )?
163                .is_lt()
164        {
165            extreme[root] = vertex;
166        }
167    }
168    let roots: Vec<usize> = (0..extreme.len())
169        .filter(|&root| extreme[root] != usize::MAX)
170        .collect();
171
172    // The outer contour of each component.
173    let mut is_outer = vec![false; contours.len()];
174    for &root in &roots {
175        let vertex = extreme[root];
176        let fan = &fans[vertex];
177        let here = arrangement.vertices[vertex].point;
178        let far = |&(piece, forward): &(PieceId, bool)| {
179            arrangement.vertices[arrangement.pieces[piece.0].ends[usize::from(forward)].0].point
180        };
181        let mut wide = None;
182        for (index, spoke) in fan.iter().enumerate() {
183            let after = &fan[(index + 1) % fan.len()];
184            let turns_clockwise =
185                fan.len() == 1 || points.orient(here, far(spoke), far(after))? == Sign::Negative;
186            if turns_clockwise {
187                if wide.is_some() {
188                    return Err(GeomError::Degenerate(
189                        "a component has two wedges wider than a half turn at its extreme vertex"
190                            .into(),
191                    ));
192                }
193                wide = Some(index);
194            }
195        }
196        let index = wide.ok_or_else(|| {
197            GeomError::Degenerate("a component has no wedge wider than a half turn".into())
198        })?;
199        let (piece, forward) = fan[index];
200        is_outer[contour_of[half_edge(piece, forward)]] = true;
201    }
202
203    // Bounded faces, then the faces around the nested components.
204    let mut face_of = vec![0usize; contours.len()];
205    let mut count = 1;
206    for (contour, outer) in is_outer.iter().enumerate() {
207        if !outer {
208            face_of[contour] = count;
209            count += 1;
210        }
211    }
212    if roots.len() > 1 {
213        let walks: Vec<Vec<PointId>> = contours
214            .iter()
215            .map(|walk| {
216                walk.iter()
217                    .map(|&half| arrangement.vertices[tail(half)].point)
218                    .collect()
219            })
220            .collect();
221        let boxes: Vec<RingBox> = walks.iter().map(|walk| points.ring_box(walk)).collect();
222        let component_of = |contour: usize| find_root(&parent, tail(contours[contour][0]));
223        let outer_contours: Vec<usize> = (0..contours.len()).filter(|&c| is_outer[c]).collect();
224        for &outer in &outer_contours {
225            options.check_cancelled()?;
226            let root = component_of(outer);
227            let vertex = extreme[root];
228            let here = arrangement.vertices[vertex].point;
229            let here_box = points.ring_box(&[here]);
230            let mut innermost: Option<(usize, usize)> = None;
231            for (contour, walk) in walks.iter().enumerate() {
232                if is_outer[contour]
233                    || component_of(contour) == root
234                    || !here_box.possibly_within(&boxes[contour])
235                {
236                    continue;
237                }
238                options.check_cancelled()?;
239                budget.count()?;
240                match points.locate(here, walk)? {
241                    Location::Inside => {}
242                    Location::Outside => continue,
243                    Location::Boundary => return Err(inconsistent()),
244                }
245                let holder = extreme[component_of(contour)];
246                let deeper = match innermost {
247                    None => true,
248                    Some((_, known)) => points
249                        .lexicographic(
250                            arrangement.vertices[holder].point,
251                            arrangement.vertices[known].point,
252                        )?
253                        .is_gt(),
254                };
255                if deeper {
256                    innermost = Some((contour, holder));
257                }
258            }
259            if let Some((contour, _)) = innermost {
260                face_of[outer] = face_of[contour];
261            }
262        }
263    }
264
265    let sides = (0..piece_count)
266        .map(|piece| {
267            [
268                FaceId(face_of[contour_of[2 * piece]]),
269                FaceId(face_of[contour_of[2 * piece + 1]]),
270            ]
271        })
272        .collect();
273    Ok(Faces { sides, count })
274}
275
276/// The root of `item` without compressing the paths.
277fn find_root(parent: &[usize], mut item: usize) -> usize {
278    while parent[item] != item {
279        item = parent[item];
280    }
281    item
282}
axiolid_exact_arrangement/faces.rs

axiolid_exact_arrangement/
faces.rs
