fj_kernel/objects/full/
cycle.rs

1use std::slice;
2
3use fj_math::{Scalar, Winding};
4use itertools::Itertools;
5
6use crate::{geometry::curve::Curve, objects::HalfEdge, storage::Handle};
7
8/// A cycle of connected half-edges
9#[derive(Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
10pub struct Cycle {
11    half_edges: Vec<Handle<HalfEdge>>,
12}
13
14impl Cycle {
15    /// Create an instance of `Cycle`
16    pub fn new(half_edges: impl IntoIterator<Item = Handle<HalfEdge>>) -> Self {
17        let half_edges = half_edges.into_iter().collect::<Vec<_>>();
18        Self { half_edges }
19    }
20
21    /// Access the half-edges that make up the cycle
22    pub fn half_edges(&self) -> HalfEdgesOfCycle {
23        self.half_edges.iter()
24    }
25
26    /// Access the half-edge with the provided index
27    pub fn nth_half_edge(&self, index: usize) -> Option<&Handle<HalfEdge>> {
28        self.half_edges.get(index)
29    }
30
31    /// Access the half-edge after the provided one
32    ///
33    /// # Panics
34    ///
35    /// Panics, if the provided half-edge is not part of this cycle.
36    pub fn half_edge_after(
37        &self,
38        half_edge: &Handle<HalfEdge>,
39    ) -> Option<&Handle<HalfEdge>> {
40        self.index_of(half_edge).map(|index| {
41            let next_index = (index + 1) % self.half_edges.len();
42            &self.half_edges[next_index]
43        })
44    }
45
46    /// Return the index of the provided half-edge, if it is in this cycle
47    pub fn index_of(&self, half_edge: &Handle<HalfEdge>) -> Option<usize> {
48        self.half_edges
49            .iter()
50            .position(|edge| edge.id() == half_edge.id())
51    }
52
53    /// Return the number of half-edges in the cycle
54    pub fn len(&self) -> usize {
55        self.half_edges.len()
56    }
57
58    /// Indicate whether the cycle is empty
59    pub fn is_empty(&self) -> bool {
60        self.half_edges.is_empty()
61    }
62
63    /// Indicate the cycle's winding, assuming a right-handed coordinate system
64    ///
65    /// Please note that this is not *the* winding of the cycle, only one of the
66    /// two possible windings, depending on the direction you look at the
67    /// surface that the cycle is defined on from.
68    pub fn winding(&self) -> Winding {
69        // The cycle could be made up of one or two circles. If that is the
70        // case, the winding of the cycle is determined by the winding of the
71        // first circle.
72        if self.half_edges.len() < 3 {
73            let first = self
74                .half_edges()
75                .next()
76                .expect("Invalid cycle: expected at least one half-edge");
77
78            let [a, b] = first.boundary();
79            let edge_direction_positive = a < b;
80
81            let circle = match first.curve() {
82                Curve::Circle(circle) => circle,
83                Curve::Line(_) => unreachable!(
84                    "Invalid cycle: less than 3 edges, but not all are circles"
85                ),
86            };
87            let cross_positive = circle.a().cross2d(&circle.b()) > Scalar::ZERO;
88
89            if edge_direction_positive == cross_positive {
90                return Winding::Ccw;
91            } else {
92                return Winding::Cw;
93            }
94        }
95
96        // Now that we got the special case out of the way, we can treat the
97        // cycle as a polygon:
98        // https://stackoverflow.com/a/1165943
99
100        let mut sum = Scalar::ZERO;
101
102        for (a, b) in self.half_edges.iter().circular_tuple_windows() {
103            let [a, b] = [a, b].map(|half_edge| half_edge.start_position());
104
105            sum += (b.u - a.u) * (b.v + a.v);
106        }
107
108        if sum > Scalar::ZERO {
109            return Winding::Cw;
110        }
111        if sum < Scalar::ZERO {
112            return Winding::Ccw;
113        }
114
115        unreachable!("Encountered invalid cycle: {self:#?}");
116    }
117}
118
119/// An iterator over the half-edges of a [`Cycle`]
120///
121/// Returned by [`Cycle::half_edges`].
122pub type HalfEdgesOfCycle<'a> = slice::Iter<'a, Handle<HalfEdge>>;
fj_kernel/objects/full/cycle.rs

fj_kernel/objects/full/
cycle.rs
