oxigdal_noalloc/
ring.rs

1//! Fixed-capacity closed ring type for `no_std`, `no_alloc` environments.
2//!
3//! [`FixedRing`] stores up to `N` vertices inline, representing a closed ring
4//! (the last vertex is implicitly connected back to the first). Provides
5//! signed area (shoelace), winding direction, and point-in-ring (ray casting).
6
7use crate::{NoAllocError, Point2D};
8
9/// A fixed-capacity closed ring backed by an inline array.
10///
11/// The ring is implicitly closed: the edge from `vertices[len-1]` back to
12/// `vertices[0]` is always present when the ring has 3+ vertices.
13pub struct FixedRing<const N: usize> {
14    vertices: [Point2D; N],
15    len: usize,
16}
17
18impl<const N: usize> FixedRing<N> {
19    /// Creates an empty `FixedRing`.
20    #[must_use]
21    #[inline]
22    pub fn new() -> Self {
23        Self {
24            vertices: [Point2D::new(0.0, 0.0); N],
25            len: 0,
26        }
27    }
28
29    /// Attempts to append a vertex. Returns `Ok(())` on success or
30    /// `Err(NoAllocError::CapacityExceeded)` if the ring is full.
31    #[inline]
32    pub fn push(&mut self, p: Point2D) -> Result<(), NoAllocError> {
33        if self.len >= N {
34            return Err(NoAllocError::CapacityExceeded);
35        }
36        self.vertices[self.len] = p;
37        self.len += 1;
38        Ok(())
39    }
40
41    /// Returns the number of vertices.
42    #[must_use]
43    #[inline]
44    pub fn len(&self) -> usize {
45        self.len
46    }
47
48    /// Returns `true` if the ring has no vertices.
49    #[must_use]
50    #[inline]
51    pub fn is_empty(&self) -> bool {
52        self.len == 0
53    }
54
55    /// Returns a slice of the current vertices.
56    #[must_use]
57    #[inline]
58    pub fn vertices(&self) -> &[Point2D] {
59        &self.vertices[..self.len]
60    }
61
62    /// Returns the vertex at the given index, or `None` if out of bounds.
63    #[must_use]
64    #[inline]
65    pub fn get(&self, index: usize) -> Option<&Point2D> {
66        if index < self.len {
67            Some(&self.vertices[index])
68        } else {
69            None
70        }
71    }
72
73    /// Computes the signed area using the shoelace formula.
74    ///
75    /// Positive for counter-clockwise winding, negative for clockwise.
76    /// Returns `0.0` if the ring has fewer than 3 vertices.
77    #[must_use]
78    pub fn signed_area(&self) -> f64 {
79        if self.len < 3 {
80            return 0.0;
81        }
82        let verts = self.vertices();
83        let mut sum = 0.0_f64;
84        let mut i = 0;
85        while i < self.len {
86            let j = if i + 1 < self.len { i + 1 } else { 0 };
87            sum += verts[i].x * verts[j].y;
88            sum -= verts[j].x * verts[i].y;
89            i += 1;
90        }
91        sum * 0.5
92    }
93
94    /// Computes the absolute area using the shoelace formula.
95    #[must_use]
96    #[inline]
97    pub fn area(&self) -> f64 {
98        let sa = self.signed_area();
99        if sa < 0.0 { -sa } else { sa }
100    }
101
102    /// Returns `true` if the ring's vertices are ordered counter-clockwise.
103    ///
104    /// A ring with fewer than 3 vertices is considered neither CW nor CCW
105    /// and returns `false`.
106    #[must_use]
107    #[inline]
108    pub fn is_counter_clockwise(&self) -> bool {
109        self.signed_area() > 0.0
110    }
111
112    /// Returns `true` if the ring's vertices are ordered clockwise.
113    #[must_use]
114    #[inline]
115    pub fn is_clockwise(&self) -> bool {
116        self.signed_area() < 0.0
117    }
118
119    /// Tests whether a point lies inside or on the boundary of the ring
120    /// using the ray-casting algorithm.
121    ///
122    /// A horizontal ray from the point toward +X is tested against each edge
123    /// of the ring. An odd number of crossings means the point is inside.
124    ///
125    /// Returns `false` for rings with fewer than 3 vertices.
126    #[must_use]
127    pub fn contains_point(&self, p: Point2D) -> bool {
128        if self.len < 3 {
129            return false;
130        }
131        let verts = self.vertices();
132        let mut inside = false;
133        let mut j = self.len - 1;
134        let mut i = 0;
135        while i < self.len {
136            let vi = &verts[i];
137            let vj = &verts[j];
138
139            // Check if the edge (vj -> vi) crosses the horizontal ray from p
140            let yi_above = vi.y > p.y;
141            let yj_above = vj.y > p.y;
142            if yi_above != yj_above {
143                // Compute the X coordinate of the edge at y = p.y
144                let slope_inv = (vj.x - vi.x) / (vj.y - vi.y);
145                let x_intersect = vi.x + (p.y - vi.y) * slope_inv;
146                if p.x < x_intersect {
147                    inside = !inside;
148                }
149            }
150            j = i;
151            i += 1;
152        }
153        inside
154    }
155
156    /// Computes the perimeter (sum of edge lengths including the closing edge).
157    ///
158    /// Returns `0.0` for rings with fewer than 2 vertices.
159    #[must_use]
160    pub fn perimeter(&self) -> f64 {
161        if self.len < 2 {
162            return 0.0;
163        }
164        let verts = self.vertices();
165        let mut total = 0.0_f64;
166        let mut i = 0;
167        while i < self.len {
168            let j = if i + 1 < self.len { i + 1 } else { 0 };
169            total += verts[i].distance_to(&verts[j]);
170            i += 1;
171        }
172        total
173    }
174
175    /// Returns the capacity of this ring.
176    #[must_use]
177    #[inline]
178    pub const fn capacity(&self) -> usize {
179        N
180    }
181
182    /// Clears all vertices, resetting the length to zero.
183    #[inline]
184    pub fn clear(&mut self) {
185        self.len = 0;
186    }
187}
188
189impl<const N: usize> Default for FixedRing<N> {
190    fn default() -> Self {
191        Self::new()
192    }
193}
194
195#[cfg(test)]
196mod tests {
197    use super::*;
198
199    fn make_ccw_square() -> FixedRing<8> {
200        let mut ring: FixedRing<8> = FixedRing::new();
201        // CCW square: (0,0) -> (1,0) -> (1,1) -> (0,1)
202        let _ = ring.push(Point2D::new(0.0, 0.0));
203        let _ = ring.push(Point2D::new(1.0, 0.0));
204        let _ = ring.push(Point2D::new(1.0, 1.0));
205        let _ = ring.push(Point2D::new(0.0, 1.0));
206        ring
207    }
208
209    fn make_cw_square() -> FixedRing<8> {
210        let mut ring: FixedRing<8> = FixedRing::new();
211        // CW square: (0,0) -> (0,1) -> (1,1) -> (1,0)
212        let _ = ring.push(Point2D::new(0.0, 0.0));
213        let _ = ring.push(Point2D::new(0.0, 1.0));
214        let _ = ring.push(Point2D::new(1.0, 1.0));
215        let _ = ring.push(Point2D::new(1.0, 0.0));
216        ring
217    }
218
219    #[test]
220    fn test_new_empty() {
221        let ring: FixedRing<10> = FixedRing::new();
222        assert!(ring.is_empty());
223        assert_eq!(ring.len(), 0);
224        assert_eq!(ring.capacity(), 10);
225    }
226
227    #[test]
228    fn test_push_and_get() {
229        let mut ring: FixedRing<4> = FixedRing::new();
230        assert!(ring.push(Point2D::new(1.0, 2.0)).is_ok());
231        assert!(ring.push(Point2D::new(3.0, 4.0)).is_ok());
232        assert_eq!(ring.len(), 2);
233
234        let p = ring.get(0).expect("index 0 exists");
235        assert!((p.x - 1.0).abs() < f64::EPSILON);
236        assert!(ring.get(5).is_none());
237    }
238
239    #[test]
240    fn test_capacity_exceeded() {
241        let mut ring: FixedRing<2> = FixedRing::new();
242        assert!(ring.push(Point2D::new(0.0, 0.0)).is_ok());
243        assert!(ring.push(Point2D::new(1.0, 1.0)).is_ok());
244        assert_eq!(
245            ring.push(Point2D::new(2.0, 2.0)),
246            Err(NoAllocError::CapacityExceeded)
247        );
248    }
249
250    #[test]
251    fn test_signed_area_ccw() {
252        let ring = make_ccw_square();
253        let area = ring.signed_area();
254        assert!(
255            (area - 1.0).abs() < 1e-10,
256            "CCW square should have positive area ~1.0, got {area}"
257        );
258    }
259
260    #[test]
261    fn test_signed_area_cw() {
262        let ring = make_cw_square();
263        let area = ring.signed_area();
264        assert!(
265            (area - (-1.0)).abs() < 1e-10,
266            "CW square should have negative area ~-1.0, got {area}"
267        );
268    }
269
270    #[test]
271    fn test_area_absolute() {
272        let ccw = make_ccw_square();
273        let cw = make_cw_square();
274        assert!((ccw.area() - 1.0).abs() < 1e-10);
275        assert!((cw.area() - 1.0).abs() < 1e-10);
276    }
277
278    #[test]
279    fn test_area_degenerate() {
280        let ring: FixedRing<10> = FixedRing::new();
281        assert!((ring.area() - 0.0).abs() < f64::EPSILON);
282
283        let mut ring2: FixedRing<10> = FixedRing::new();
284        let _ = ring2.push(Point2D::new(0.0, 0.0));
285        let _ = ring2.push(Point2D::new(1.0, 1.0));
286        assert!((ring2.area() - 0.0).abs() < f64::EPSILON);
287    }
288
289    #[test]
290    fn test_is_ccw_cw() {
291        let ccw = make_ccw_square();
292        let cw = make_cw_square();
293        assert!(ccw.is_counter_clockwise());
294        assert!(!ccw.is_clockwise());
295        assert!(cw.is_clockwise());
296        assert!(!cw.is_counter_clockwise());
297    }
298
299    #[test]
300    fn test_contains_point_inside() {
301        let ring = make_ccw_square();
302        assert!(ring.contains_point(Point2D::new(0.5, 0.5)));
303        assert!(ring.contains_point(Point2D::new(0.1, 0.9)));
304    }
305
306    #[test]
307    fn test_contains_point_outside() {
308        let ring = make_ccw_square();
309        assert!(!ring.contains_point(Point2D::new(2.0, 0.5)));
310        assert!(!ring.contains_point(Point2D::new(-0.1, 0.5)));
311        assert!(!ring.contains_point(Point2D::new(0.5, -0.1)));
312        assert!(!ring.contains_point(Point2D::new(0.5, 1.1)));
313    }
314
315    #[test]
316    fn test_contains_point_degenerate() {
317        let ring: FixedRing<10> = FixedRing::new();
318        assert!(!ring.contains_point(Point2D::new(0.0, 0.0)));
319    }
320
321    #[test]
322    fn test_contains_point_triangle() {
323        let mut ring: FixedRing<8> = FixedRing::new();
324        let _ = ring.push(Point2D::new(0.0, 0.0));
325        let _ = ring.push(Point2D::new(4.0, 0.0));
326        let _ = ring.push(Point2D::new(2.0, 3.0));
327        assert!(ring.contains_point(Point2D::new(2.0, 1.0)));
328        assert!(!ring.contains_point(Point2D::new(0.0, 3.0)));
329    }
330
331    #[test]
332    fn test_perimeter() {
333        let ring = make_ccw_square();
334        assert!((ring.perimeter() - 4.0).abs() < 1e-10);
335    }
336
337    #[test]
338    fn test_perimeter_degenerate() {
339        let ring: FixedRing<10> = FixedRing::new();
340        assert!((ring.perimeter() - 0.0).abs() < f64::EPSILON);
341    }
342
343    #[test]
344    fn test_clear() {
345        let mut ring = make_ccw_square();
346        ring.clear();
347        assert!(ring.is_empty());
348    }
349
350    #[test]
351    fn test_default() {
352        let ring: FixedRing<5> = FixedRing::default();
353        assert!(ring.is_empty());
354    }
355
356    #[test]
357    fn test_vertices_slice() {
358        let ring = make_ccw_square();
359        let verts = ring.vertices();
360        assert_eq!(verts.len(), 4);
361    }
362
363    #[test]
364    fn test_contains_point_cw_ring() {
365        // Ray casting works regardless of winding direction
366        let ring = make_cw_square();
367        assert!(ring.contains_point(Point2D::new(0.5, 0.5)));
368        assert!(!ring.contains_point(Point2D::new(2.0, 2.0)));
369    }
370}
oxigdal_noalloc/ring.rs

oxigdal_noalloc/
ring.rs
