axiolid_core/
primitives2.rs

1//! Bounded two-dimensional primitives.
2//!
3//! The XY-plane counterparts of [`crate::primitives3`], following the same
4//! rules: plain data with public fields, no validation in constructors, and no
5//! hidden epsilon. A degenerate value stays representable so the algorithm
6//! consuming it can judge it against its own [`Tolerance`].
7//!
8//! [`Tolerance`]: crate::Tolerance
9
10use crate::{Point2, Scalar, Vec2};
11
12/// Axis-aligned two-dimensional bounding box.
13///
14/// The XY-plane counterpart of [`Aabb`], with the same empty-absorbs-first
15/// behaviour so a fold over points needs no special case for the first one.
16///
17/// [`Aabb`]: crate::Aabb
18#[derive(Debug, Clone, Copy, PartialEq)]
19pub struct Aabb2 {
20    /// Minimum corner.
21    pub min: Point2,
22    /// Maximum corner.
23    pub max: Point2,
24}
25
26impl Aabb2 {
27    /// An empty box that absorbs the first extended point.
28    ///
29    /// Inverted on purpose: `min` starts at positive infinity and `max` at
30    /// negative infinity, so the first [`extend`] overwrites both rather than
31    /// leaving a spurious box around the origin.
32    ///
33    /// [`extend`]: Aabb2::extend
34    pub const fn empty() -> Self {
35        Self {
36            min: Vec2::splat(Scalar::INFINITY),
37            max: Vec2::splat(Scalar::NEG_INFINITY),
38        }
39    }
40
41    /// Construct a non-empty box containing exactly one point.
42    #[inline]
43    pub const fn from_point(point: Point2) -> Self {
44        Self {
45            min: point,
46            max: point,
47        }
48    }
49
50    /// Grow to include a point.
51    #[inline]
52    pub fn extend(&mut self, point: Point2) {
53        self.min = self.min.min(point);
54        self.max = self.max.max(point);
55    }
56
57    /// Grow to include every point in another box.
58    #[inline]
59    pub fn union(&mut self, other: &Self) {
60        self.min = self.min.min(other.min);
61        self.max = self.max.max(other.max);
62    }
63
64    /// Whether both corners are finite coordinates.
65    #[inline]
66    pub fn is_finite(&self) -> bool {
67        self.min.is_finite() && self.max.is_finite()
68    }
69
70    /// Whether the boxes overlap. Touching counts as overlap.
71    #[inline]
72    pub fn intersects(&self, other: &Self) -> bool {
73        self.min.x <= other.max.x
74            && self.max.x >= other.min.x
75            && self.min.y <= other.max.y
76            && self.max.y >= other.min.y
77    }
78
79    /// Whether the box contains a point. The boundary counts as inside.
80    #[inline]
81    pub fn contains(&self, point: Point2) -> bool {
82        point.x >= self.min.x
83            && point.x <= self.max.x
84            && point.y >= self.min.y
85            && point.y <= self.max.y
86    }
87
88    /// Whether no point has been added.
89    #[inline]
90    pub fn is_empty(&self) -> bool {
91        self.min.x > self.max.x
92    }
93
94    /// Diagonal vector, or zero for an empty box.
95    pub fn diagonal(&self) -> Vec2 {
96        if self.is_empty() {
97            Vec2::ZERO
98        } else {
99            self.max - self.min
100        }
101    }
102
103    /// Centre point, or zero for an empty box.
104    #[inline]
105    pub fn center(&self) -> Point2 {
106        if self.is_empty() {
107            Vec2::ZERO
108        } else {
109            (self.min + self.max) * 0.5
110        }
111    }
112
113    /// Enclosed area, or zero for an empty box.
114    pub fn area(&self) -> Scalar {
115        let span = self.diagonal();
116        span.x * span.y
117    }
118}
119
120impl Default for Aabb2 {
121    fn default() -> Self {
122        Self::empty()
123    }
124}
125
126/// A two-dimensional triangle.
127///
128/// Corner order sets the winding, which [`signed_area`] reports: positive is
129/// counter-clockwise. Degenerate triangles are representable.
130///
131/// [`signed_area`]: Triangle2::signed_area
132#[derive(Debug, Clone, Copy, PartialEq)]
133pub struct Triangle2 {
134    /// First corner.
135    pub a: Point2,
136    /// Second corner.
137    pub b: Point2,
138    /// Third corner.
139    pub c: Point2,
140}
141
142impl Triangle2 {
143    /// Construct a triangle without validating it.
144    pub const fn new(a: Point2, b: Point2, c: Point2) -> Self {
145        Self { a, b, c }
146    }
147
148    /// Twice the signed area: positive counter-clockwise, negative clockwise.
149    ///
150    /// Returned doubled and unscaled because this is the same quantity as the
151    /// orientation determinant, so a caller testing which side of `ab` the
152    /// point `c` lies on can use it directly without a multiply that would
153    /// only add rounding.
154    pub fn signed_area2(&self) -> Scalar {
155        let ab = self.b - self.a;
156        let ac = self.c - self.a;
157        ab.perp_dot(ac)
158    }
159
160    /// Signed area: positive counter-clockwise, negative clockwise.
161    pub fn signed_area(&self) -> Scalar {
162        self.signed_area2() * 0.5
163    }
164
165    /// Area, always non-negative.
166    pub fn area(&self) -> Scalar {
167        self.signed_area().abs()
168    }
169
170    /// Centroid of the three corners.
171    pub fn centroid(&self) -> Point2 {
172        (self.a + self.b + self.c) / 3.0
173    }
174}
175
176/// A rectangle in the XY-plane, possibly rotated.
177///
178/// Stored as a corner and two edge vectors so the parallelogram property holds
179/// by construction, matching [`Rectangle3`]. Perpendicularity is not enforced:
180/// a sheared import stays representable and inspectable.
181///
182/// [`Rectangle3`]: crate::Rectangle3
183#[derive(Debug, Clone, Copy, PartialEq)]
184pub struct Rectangle2 {
185    /// Corner the edge vectors start from.
186    pub origin: Point2,
187    /// First edge vector, from `origin`.
188    pub x: Vec2,
189    /// Second edge vector, from `origin`.
190    pub y: Vec2,
191}
192
193impl Rectangle2 {
194    /// Construct from a corner and two edge vectors.
195    pub const fn new(origin: Point2, x: Vec2, y: Vec2) -> Self {
196        Self { origin, x, y }
197    }
198
199    /// An axis-aligned rectangle spanning `bounds`.
200    ///
201    /// Returns `None` for an empty box, because an inverted corner pair has no
202    /// meaningful edge vectors and silently producing a zero-sized rectangle
203    /// at the origin would hide the emptiness from the caller.
204    pub fn from_aabb(bounds: &Aabb2) -> Option<Self> {
205        if bounds.is_empty() {
206            return None;
207        }
208        let span = bounds.diagonal();
209        Some(Self {
210            origin: bounds.min,
211            x: Vec2::new(span.x, 0.0),
212            y: Vec2::new(0.0, span.y),
213        })
214    }
215
216    /// The four corners, in order around the boundary.
217    pub fn corners(&self) -> [Point2; 4] {
218        [
219            self.origin,
220            self.origin + self.x,
221            self.origin + self.x + self.y,
222            self.origin + self.y,
223        ]
224    }
225
226    /// Signed area: positive when the edge vectors are counter-clockwise.
227    pub fn signed_area(&self) -> Scalar {
228        self.x.perp_dot(self.y)
229    }
230
231    /// Area, always non-negative. Equals the parallelogram area when sheared.
232    pub fn area(&self) -> Scalar {
233        self.signed_area().abs()
234    }
235
236    /// Centre point.
237    pub fn center(&self) -> Point2 {
238        self.origin + (self.x + self.y) * 0.5
239    }
240}
241
242/// A simple polygon in the XY-plane, without holes.
243///
244/// The closing edge is implicit, so the last vertex joins the first. Repeating
245/// the first vertex at the end creates a zero-length edge rather than closing
246/// the ring, which is a common source of degenerate imported data.
247///
248/// Simplicity -- no self-intersection -- is assumed and not checked: that is a
249/// tolerance-dependent judgement, and the types here hold data rather than
250/// enforce policy. A polygon set with holes is a different concept; see the
251/// planar overlay crate's region type for that.
252#[derive(Debug, Clone, PartialEq)]
253pub struct Polygon2 {
254    /// Boundary vertices in order. The closing edge is implicit.
255    pub vertices: Vec<Point2>,
256}
257
258impl Polygon2 {
259    /// Construct from boundary vertices in order.
260    pub const fn new(vertices: Vec<Point2>) -> Self {
261        Self { vertices }
262    }
263
264    /// Number of boundary vertices, which equals the number of edges.
265    pub fn len(&self) -> usize {
266        self.vertices.len()
267    }
268
269    /// Whether the polygon has no vertices.
270    pub fn is_empty(&self) -> bool {
271        self.vertices.is_empty()
272    }
273
274    /// Twice the signed area by the shoelace formula.
275    ///
276    /// Summed about the first vertex rather than the origin. The two agree
277    /// mathematically, but a polygon in georeferenced coordinates sits far
278    /// from the origin, where the terms are large and nearly cancel; rebasing
279    /// keeps the terms the size of the polygon instead of the size of the
280    /// coordinate system.
281    ///
282    /// Fewer than three vertices enclose nothing and give zero.
283    pub fn signed_area2(&self) -> Scalar {
284        if self.vertices.len() < 3 {
285            return 0.0;
286        }
287        let base = self.vertices[0];
288        let mut total = 0.0;
289        for pair in self.vertices[1..].windows(2) {
290            total += (pair[0] - base).perp_dot(pair[1] - base);
291        }
292        total
293    }
294
295    /// Signed area: positive counter-clockwise, negative clockwise.
296    pub fn signed_area(&self) -> Scalar {
297        self.signed_area2() * 0.5
298    }
299
300    /// Area, always non-negative.
301    pub fn area(&self) -> Scalar {
302        self.signed_area().abs()
303    }
304
305    /// Whether the vertex order is counter-clockwise.
306    ///
307    /// A degenerate polygon has no winding; this reports `false` for it rather
308    /// than inventing one.
309    pub fn is_counter_clockwise(&self) -> bool {
310        self.signed_area2() > 0.0
311    }
312
313    /// Axis-aligned bounds of the boundary vertices.
314    pub fn bounds(&self) -> Aabb2 {
315        let mut bounds = Aabb2::empty();
316        for vertex in &self.vertices {
317            bounds.extend(*vertex);
318        }
319        bounds
320    }
321}
322
323#[cfg(test)]
324mod tests {
325    use super::*;
326
327    #[test]
328    fn empty_bounds_absorb_the_first_point() {
329        let mut bounds = Aabb2::default();
330        assert!(bounds.is_empty());
331        bounds.extend(Point2::new(3.0, -1.0));
332        assert_eq!(bounds.min, bounds.max);
333        assert!(!bounds.is_empty());
334        assert_eq!(bounds.area(), 0.0);
335    }
336
337    #[test]
338    fn bounds_intersect_on_touch_and_contain_their_boundary() {
339        let mut left = Aabb2::from_point(Point2::ZERO);
340        left.extend(Point2::new(1.0, 1.0));
341        let mut right = Aabb2::from_point(Point2::new(1.0, 0.0));
342        right.extend(Point2::new(2.0, 1.0));
343        assert!(left.intersects(&right), "touching boxes overlap");
344        assert!(left.contains(Point2::new(1.0, 1.0)), "boundary is inside");
345
346        let mut away = Aabb2::from_point(Point2::new(5.0, 5.0));
347        away.extend(Point2::new(6.0, 6.0));
348        assert!(!left.intersects(&away));
349    }
350
351    #[test]
352    fn triangle_signed_area_carries_winding_but_area_does_not() {
353        let ccw = Triangle2::new(Point2::ZERO, Point2::new(4.0, 0.0), Point2::new(0.0, 2.0));
354        assert_eq!(ccw.signed_area(), 4.0);
355        assert!(ccw.signed_area2() > 0.0);
356
357        let cw = Triangle2::new(ccw.a, ccw.c, ccw.b);
358        assert_eq!(cw.signed_area(), -4.0);
359        assert_eq!(cw.area(), ccw.area());
360    }
361
362    #[test]
363    fn collinear_triangle_has_zero_area() {
364        let degenerate = Triangle2::new(Point2::ZERO, Point2::new(1.0, 1.0), Point2::new(3.0, 3.0));
365        assert_eq!(degenerate.signed_area2(), 0.0);
366        assert_eq!(degenerate.area(), 0.0);
367    }
368
369    #[test]
370    fn rectangle_from_bounds_matches_the_box_it_came_from() {
371        let mut bounds = Aabb2::from_point(Point2::new(1.0, 2.0));
372        bounds.extend(Point2::new(4.0, 6.0));
373        let rectangle = Rectangle2::from_aabb(&bounds).expect("non-empty bounds");
374        assert_eq!(rectangle.area(), bounds.area());
375        assert_eq!(rectangle.center(), bounds.center());
376        assert_eq!(rectangle.corners()[2], bounds.max);
377    }
378
379    #[test]
380    fn rectangle_from_empty_bounds_is_refused_rather_than_zero_sized() {
381        assert!(Rectangle2::from_aabb(&Aabb2::empty()).is_none());
382    }
383
384    #[test]
385    fn rotated_rectangle_keeps_its_area() {
386        // A 45-degree rotated unit square: axis-aligned bounds would overstate
387        // the area, which is why Rectangle2 is not stored as an Aabb2.
388        let diagonal = Vec2::new(1.0, 1.0);
389        let rectangle = Rectangle2::new(Point2::ZERO, diagonal, Vec2::new(-1.0, 1.0));
390        assert_eq!(rectangle.area(), 2.0);
391    }
392
393    #[test]
394    fn polygon_winding_flips_with_vertex_order() {
395        let square = Polygon2::new(vec![
396            Point2::ZERO,
397            Point2::new(2.0, 0.0),
398            Point2::new(2.0, 2.0),
399            Point2::new(0.0, 2.0),
400        ]);
401        assert_eq!(square.area(), 4.0);
402        assert!(square.is_counter_clockwise());
403
404        let mut reversed = square.vertices.clone();
405        reversed.reverse();
406        let reversed = Polygon2::new(reversed);
407        assert_eq!(reversed.area(), square.area());
408        assert!(!reversed.is_counter_clockwise());
409        assert_eq!(reversed.signed_area(), -square.signed_area());
410    }
411
412    #[test]
413    fn polygon_with_fewer_than_three_vertices_encloses_nothing() {
414        assert_eq!(Polygon2::new(Vec::new()).signed_area2(), 0.0);
415        assert_eq!(
416            Polygon2::new(vec![Point2::ZERO, Point2::new(1.0, 0.0)]).signed_area2(),
417            0.0
418        );
419        assert!(!Polygon2::new(Vec::new()).is_counter_clockwise());
420    }
421
422    #[test]
423    fn polygon_area_is_translation_invariant_far_from_the_origin() {
424        // Site coordinates routinely sit millions of units out. Summing the
425        // shoelace terms about the origin there loses significant digits.
426        let offset = Vec2::splat(6_000_000.0);
427        let local = Polygon2::new(vec![
428            Point2::ZERO,
429            Point2::new(1.0, 0.0),
430            Point2::new(1.0, 1.0),
431            Point2::new(0.0, 1.0),
432        ]);
433        let far = Polygon2::new(local.vertices.iter().map(|v| *v + offset).collect());
434        assert_eq!(far.area(), local.area());
435    }
436
437    #[test]
438    fn polygon_bounds_cover_every_vertex() {
439        let polygon = Polygon2::new(vec![
440            Point2::new(-1.0, 4.0),
441            Point2::new(3.0, -2.0),
442            Point2::new(0.0, 0.0),
443        ]);
444        let bounds = polygon.bounds();
445        assert_eq!(bounds.min, Point2::new(-1.0, -2.0));
446        assert_eq!(bounds.max, Point2::new(3.0, 4.0));
447        for vertex in &polygon.vertices {
448            assert!(bounds.contains(*vertex));
449        }
450    }
451}
axiolid_core/primitives2.rs

axiolid_core/
primitives2.rs
