axiolid_arrangement/
query.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! Traversal and measurement over the arrangement.
4//!
5//! Everything here is derived on demand. Nothing is cached, so no edit can
6//! leave a stale answer behind.
7
8use axiolid_core::Point2;
9
10use crate::id::{FaceId, HalfEdgeId, VertexId};
11use crate::Arrangement;
12
13impl Arrangement {
14    /// Half-edges around a face's boundary, counter-clockwise.
15    ///
16    /// Returns empty for a face with no boundary (the unbounded face of an
17    /// empty arrangement).
18    #[must_use]
19    pub fn face_halfedges(&self, face: FaceId) -> Vec<HalfEdgeId> {
20        let Some(start) = self.faces[face.index()].boundary else {
21            return Vec::new();
22        };
23        let mut out = vec![start];
24        let mut current = self.halfedges[start.index()].next;
25        // Bounded by the arena: a corrupted `next` cycle cannot hang the
26        // caller, it just yields a short walk that `validate` will flag.
27        while current != start && out.len() <= self.halfedges.len() {
28            out.push(current);
29            current = self.halfedges[current.index()].next;
30        }
31        out
32    }
33
34    /// Corner positions of a face, counter-clockwise.
35    #[must_use]
36    pub fn face_outline(&self, face: FaceId) -> Vec<Point2> {
37        self.face_halfedges(face)
38            .into_iter()
39            .map(|h| self.vertices[self.halfedges[h.index()].origin.index()].position)
40            .collect()
41    }
42
43    /// Signed area of a face, positive when its boundary runs
44    /// counter-clockwise.
45    ///
46    /// The unbounded face has no meaningful area; it reports 0.0 rather than
47    /// a negative number that a caller might sum into a total.
48    #[must_use]
49    pub fn face_area(&self, face: FaceId) -> f64 {
50        if face == FaceId::OUTER {
51            return 0.0;
52        }
53        let outline = self.face_outline(face);
54        if outline.len() < 3 {
55            return 0.0;
56        }
57        // Shoelace about the first vertex rather than the world origin: same
58        // reasoning as the mass-properties fix, and free here.
59        let base = outline[0];
60        let mut twice = 0.0;
61        for window in outline[1..].windows(2) {
62            let a = window[0] - base;
63            let b = window[1] - base;
64            twice += a.x * b.y - a.y * b.x;
65        }
66        twice / 2.0
67    }
68
69    /// The face on the other side of a half-edge.
70    ///
71    /// Always defined: the unbounded face is a real face, so an edge on the
72    /// outer boundary reports it rather than `None`.
73    #[must_use]
74    pub fn neighbour_across(&self, edge: HalfEdgeId) -> FaceId {
75        let twin = self.halfedges[edge.index()].twin;
76        self.halfedges[twin.index()].face
77    }
78
79    /// Every bounded face, in arena order.
80    ///
81    /// Deliberately excludes the unbounded face: a caller asking for "the
82    /// regions" almost never means the infinite one, and including it is the
83    /// kind of default that produces a wrong total on the first use.
84    pub fn bounded_faces(&self) -> impl Iterator<Item = FaceId> + '_ {
85        (1..self.faces.len()).map(FaceId::from_index)
86    }
87
88    /// Half-edges leaving a vertex, counter-clockwise around it.
89    #[must_use]
90    pub fn vertex_halfedges(&self, vertex: VertexId) -> Vec<HalfEdgeId> {
91        let Some(start) = self.vertices[vertex.index()].outgoing else {
92            return Vec::new();
93        };
94        let mut out = vec![start];
95        // Around a vertex: take the twin (now pointing in), then its next
96        // (pointing out again, one step around).
97        let mut current = self.halfedges[self.halfedges[start.index()].twin.index()].next;
98        while current != start && out.len() <= self.halfedges.len() {
99            out.push(current);
100            current = self.halfedges[self.halfedges[current.index()].twin.index()].next;
101        }
102        out
103    }
104
105    /// Number of edges meeting at a vertex.
106    #[must_use]
107    pub fn degree(&self, vertex: VertexId) -> usize {
108        self.vertex_halfedges(vertex).len()
109    }
110
111    /// Vertex a half-edge leaves from.
112    #[must_use]
113    pub fn halfedge_origin(&self, edge: HalfEdgeId) -> VertexId {
114        self.halfedges[edge.index()].origin
115    }
116
117    /// Face lying to the left of a half-edge.
118    #[must_use]
119    pub fn halfedge_face(&self, edge: HalfEdgeId) -> FaceId {
120        self.halfedges[edge.index()].face
121    }
122}
axiolid_arrangement/query.rs

axiolid_arrangement/
query.rs
