axiolid_arrangement/
build.rs

1// SPDX-License-Identifier: MPL-2.0
2
3//! Building an arrangement from polygon boundaries.
4
5use axiolid_core::Point2;
6
7use crate::entity::{Face, HalfEdge, Vertex};
8use crate::id::{FaceId, HalfEdgeId, VertexId};
9use crate::Arrangement;
10
11/// Why an arrangement could not be built.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13#[non_exhaustive]
14pub enum BuildError {
15    /// Fewer than three distinct corners were supplied.
16    DegenerateBoundary,
17    /// The boundary encloses no area.
18    ZeroArea,
19}
20
21impl core::fmt::Display for BuildError {
22    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
23        match self {
24            Self::DegenerateBoundary => write!(f, "a face needs at least three corners"),
25            Self::ZeroArea => write!(f, "the boundary encloses no area"),
26        }
27    }
28}
29
30impl core::error::Error for BuildError {}
31
32impl Arrangement {
33    /// Build a single bounded face from a closed polygon.
34    ///
35    /// Corners are taken counter-clockwise; a clockwise ring is reversed so
36    /// the bounded face is the one inside it. Silently accepting either
37    /// winding is the right call here because "which side is inside" is
38    /// unambiguous for a simple closed ring, and forcing callers to normalise
39    /// first only moves the same code outward.
40    ///
41    /// # Errors
42    ///
43    /// [`BuildError::DegenerateBoundary`] or [`BuildError::ZeroArea`].
44    pub fn from_polygon(corners: &[Point2]) -> Result<Self, BuildError> {
45        if corners.len() < 3 {
46            return Err(BuildError::DegenerateBoundary);
47        }
48        let mut ring: Vec<Point2> = corners.to_vec();
49        if signed_area(&ring) < 0.0 {
50            ring.reverse();
51        }
52        if signed_area(&ring) <= 0.0 {
53            return Err(BuildError::ZeroArea);
54        }
55
56        let mut arrangement = Self::new();
57        let n = ring.len();
58        for &corner in &ring {
59            arrangement.vertices.push(Vertex {
60                position: corner,
61                outgoing: None,
62            });
63        }
64
65        // Half-edge `2i` runs corner i -> i+1 with the bounded face on its
66        // left; `2i + 1` is its twin, bordering the unbounded face.
67        let inner = FaceId::from_index(1);
68        for i in 0..n {
69            let next_i = (i + 1) % n;
70            let prev_i = (i + n - 1) % n;
71            arrangement.halfedges.push(HalfEdge {
72                origin: VertexId::from_index(i),
73                twin: HalfEdgeId::from_index(2 * i + 1),
74                next: HalfEdgeId::from_index(2 * next_i),
75                prev: HalfEdgeId::from_index(2 * prev_i),
76                face: inner,
77            });
78            arrangement.halfedges.push(HalfEdge {
79                origin: VertexId::from_index(next_i),
80                twin: HalfEdgeId::from_index(2 * i),
81                // The outer boundary runs the opposite way around.
82                next: HalfEdgeId::from_index(2 * prev_i + 1),
83                prev: HalfEdgeId::from_index(2 * next_i + 1),
84                face: FaceId::OUTER,
85            });
86            arrangement.vertices[i].outgoing = Some(HalfEdgeId::from_index(2 * i));
87        }
88
89        arrangement.faces.push(Face {
90            boundary: Some(HalfEdgeId::from_index(0)),
91        });
92        arrangement.faces[0].boundary = Some(HalfEdgeId::from_index(1));
93        Ok(arrangement)
94    }
95}
96
97/// Shoelace area of a ring, about its first corner.
98fn signed_area(ring: &[Point2]) -> f64 {
99    let base = ring[0];
100    let mut twice = 0.0;
101    for window in ring[1..].windows(2) {
102        let a = window[0] - base;
103        let b = window[1] - base;
104        twice += a.x * b.y - a.y * b.x;
105    }
106    twice / 2.0
107}
axiolid_arrangement/build.rs

axiolid_arrangement/
build.rs
