Skip to main content

mathverse_geometry/
shapes2d.rs

1//! 2D shapes: point, circle, triangle, rectangle, polygon, ellipse.
2
3use mathverse_core::constants::{PI, TAU};
4
5/// 2D point.
6#[derive(Debug, Clone, Copy, PartialEq)]
7pub struct Point2 {
8    pub x: f64,
9    pub y: f64,
10}
11
12impl Point2 {
13    pub fn new(x: f64, y: f64) -> Self {
14        Point2 { x, y }
15    }
16    /// Euclidean distance to another point.
17    pub fn distance_to(self, other: Point2) -> f64 {
18        let dx = self.x - other.x;
19        let dy = self.y - other.y;
20        (dx * dx + dy * dy).sqrt()
21    }
22    /// Translate by `(dx, dy)`.
23    pub fn translate(self, dx: f64, dy: f64) -> Point2 {
24        Point2::new(self.x + dx, self.y + dy)
25    }
26    /// Uniform scale about the origin.
27    pub fn scale(self, s: f64) -> Point2 {
28        Point2::new(self.x * s, self.y * s)
29    }
30    /// Rotate by `angle` radians counterclockwise about the origin.
31    pub fn rotate(self, angle: f64) -> Point2 {
32        let (s, c) = angle.sin_cos();
33        Point2::new(c * self.x - s * self.y, s * self.x + c * self.y)
34    }
35    /// Rotate by `angle` radians about `center`.
36    pub fn rotate_around(self, angle: f64, center: Point2) -> Point2 {
37        self.translate(-center.x, -center.y).rotate(angle).translate(center.x, center.y)
38    }
39}
40
41/// Circle.
42#[derive(Debug, Clone, Copy, PartialEq)]
43pub struct Circle {
44    pub center: Point2,
45    pub radius: f64,
46}
47
48impl Circle {
49    /// Panics if `radius < 0`.
50    pub fn new(center: Point2, radius: f64) -> Circle {
51        assert!(radius >= 0.0, "circle radius must be non-negative");
52        Circle { center, radius }
53    }
54    pub fn area(&self) -> f64 {
55        PI * self.radius * self.radius
56    }
57    pub fn perimeter(&self) -> f64 {
58        TAU * self.radius
59    }
60    pub fn centroid(&self) -> Point2 {
61        self.center
62    }
63    pub fn contains(&self, p: Point2) -> bool {
64        self.center.distance_to(p) <= self.radius
65    }
66    /// Whether this circle overlaps `other` (touch counts).
67    pub fn intersects(&self, other: &Circle) -> bool {
68        self.center.distance_to(other.center) <= self.radius + other.radius
69    }
70    /// Intersection points with another circle: 0, 1, or 2.
71    /// Coincident circles yield `[]`.
72    pub fn intersection_points(&self, other: &Circle) -> Vec<Point2> {
73        let d = self.center.distance_to(other.center);
74        let (r1, r2) = (self.radius, other.radius);
75        if d > r1 + r2 || d < (r1 - r2).abs() || d == 0.0 {
76            return vec![];
77        }
78        let a = (r1 * r1 - r2 * r2 + d * d) / (2.0 * d);
79        let h2 = r1 * r1 - a * a;
80        let p = self.center.translate(a * (other.center.x - self.center.x) / d, a * (other.center.y - self.center.y) / d);
81        if h2 <= 1e-14 {
82            return vec![p];
83        }
84        let h = h2.sqrt();
85        let dx = h * (other.center.y - self.center.y) / d;
86        let dy = h * (other.center.x - self.center.x) / d;
87        vec![Point2::new(p.x + dx, p.y - dy), Point2::new(p.x - dx, p.y + dy)]
88    }
89}
90
91/// Triangle given by three vertices.
92#[derive(Debug, Clone, Copy, PartialEq)]
93pub struct Triangle {
94    pub a: Point2,
95    pub b: Point2,
96    pub c: Point2,
97}
98
99impl Triangle {
100    pub fn new(a: Point2, b: Point2, c: Point2) -> Triangle {
101        Triangle { a, b, c }
102    }
103    /// Shoelace formula; area is always positive.
104    pub fn area(&self) -> f64 {
105        ((self.b.x - self.a.x) * (self.c.y - self.a.y) - (self.c.x - self.a.x) * (self.b.y - self.a.y)).abs() / 2.0
106    }
107    pub fn perimeter(&self) -> f64 {
108        self.a.distance_to(self.b) + self.b.distance_to(self.c) + self.c.distance_to(self.a)
109    }
110    pub fn centroid(&self) -> Point2 {
111        Point2::new((self.a.x + self.b.x + self.c.x) / 3.0, (self.a.y + self.b.y + self.c.y) / 3.0)
112    }
113}
114
115/// Axis-aligned rectangle, `(x, y)` is the top-left corner.
116#[derive(Debug, Clone, Copy, PartialEq)]
117pub struct Rectangle {
118    pub x: f64,
119    pub y: f64,
120    pub width: f64,
121    pub height: f64,
122}
123
124impl Rectangle {
125    /// Panics if `width < 0` or `height < 0`.
126    pub fn new(x: f64, y: f64, width: f64, height: f64) -> Rectangle {
127        assert!(width >= 0.0 && height >= 0.0, "rectangle dimensions must be non-negative");
128        Rectangle { x, y, width, height }
129    }
130    pub fn area(&self) -> f64 {
131        self.width * self.height
132    }
133    pub fn perimeter(&self) -> f64 {
134        2.0 * (self.width + self.height)
135    }
136    pub fn centroid(&self) -> Point2 {
137        Point2::new(self.x + self.width / 2.0, self.y + self.height / 2.0)
138    }
139    pub fn contains(&self, p: Point2) -> bool {
140        p.x >= self.x && p.x <= self.x + self.width && p.y >= self.y && p.y <= self.y + self.height
141    }
142    /// Overlap of two axis-aligned rectangles.
143    pub fn intersects(&self, other: &Rectangle) -> bool {
144        self.x < other.x + other.width
145            && other.x < self.x + self.width
146            && self.y < other.y + other.height
147            && other.y < self.y + self.height
148    }
149    /// Rotate by `angle` radians about the centroid, returning the resulting `Polygon`.
150    pub fn rotated_polygon(&self, angle: f64) -> Polygon {
151        let c = self.centroid();
152        let corners = [
153            Point2::new(self.x, self.y),
154            Point2::new(self.x + self.width, self.y),
155            Point2::new(self.x + self.width, self.y + self.height),
156            Point2::new(self.x, self.y + self.height),
157        ];
158        Polygon::new(corners.iter().map(|p| p.rotate_around(angle, c)).collect())
159    }
160}
161
162/// Polygon from an ordered vertex list (not closed; the last vertex joins the first).
163#[derive(Debug, Clone, PartialEq)]
164pub struct Polygon {
165    pub points: Vec<Point2>,
166}
167
168impl Polygon {
169    /// Panics if fewer than 3 points.
170    pub fn new(points: Vec<Point2>) -> Polygon {
171        assert!(points.len() >= 3, "polygon needs at least 3 points");
172        Polygon { points }
173    }
174    /// Shoelace formula; works for convex and simple concave polygons.
175    pub fn area(&self) -> f64 {
176        let mut s = 0.0;
177        let n = self.points.len();
178        for i in 0..n {
179            let (a, b) = (self.points[i], self.points[(i + 1) % n]);
180            s += a.x * b.y - b.x * a.y;
181        }
182        s.abs() / 2.0
183    }
184    pub fn perimeter(&self) -> f64 {
185        let n = self.points.len();
186        (0..n).map(|i| self.points[i].distance_to(self.points[(i + 1) % n])).sum()
187    }
188    /// Area-weighted centroid.
189    pub fn centroid(&self) -> Point2 {
190        let n = self.points.len();
191        let mut cx = 0.0;
192        let mut cy = 0.0;
193        let mut a2 = 0.0;
194        for i in 0..n {
195            let (p, q) = (self.points[i], self.points[(i + 1) % n]);
196            let cross = p.x * q.y - q.x * p.y;
197            a2 += cross;
198            cx += (p.x + q.x) * cross;
199            cy += (p.y + q.y) * cross;
200        }
201        if a2 == 0.0 {
202            return Point2::new(0.0, 0.0);
203        }
204        Point2::new(cx / (3.0 * a2), cy / (3.0 * a2))
205    }
206
207    /// Returns `true` if the point lies inside the polygon.
208    ///
209    /// Uses the even-odd ray-casting rule; points exactly on the boundary
210    /// are considered inside. Works for both convex and concave simple
211    /// polygons (self-intersecting polygons are not well-defined).
212    pub fn contains(&self, p: Point2) -> bool {
213        let n = self.points.len();
214        if n < 3 {
215            return false;
216        }
217
218        // Boundary check: if the point lies on any edge, treat it as inside.
219        for i in 0..n {
220            if Self::point_on_segment(p, self.points[i], self.points[(i + 1) % n]) {
221                return true;
222            }
223        }
224
225        // Even-odd ray casting along +x.
226        let mut inside = false;
227        let mut j = n - 1;
228        for i in 0..n {
229            let (a, b) = (self.points[i], self.points[j]);
230            let crosses_half_plane = (a.y > p.y) != (b.y > p.y);
231            if crosses_half_plane {
232                let x_intersect = (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x;
233                if p.x < x_intersect {
234                    inside = !inside;
235                }
236            }
237            j = i;
238        }
239        inside
240    }
241
242    /// Returns `true` if `p` lies on the closed segment `a`-`b`.
243    fn point_on_segment(p: Point2, a: Point2, b: Point2) -> bool {
244        const EPS: f64 = 1e-12;
245        let cross = (p.x - a.x) * (b.y - a.y) - (p.y - a.y) * (b.x - a.x);
246        if cross.abs() > EPS {
247            return false;
248        }
249        p.x >= a.x.min(b.x) - EPS
250            && p.x <= a.x.max(b.x) + EPS
251            && p.y >= a.y.min(b.y) - EPS
252            && p.y <= a.y.max(b.y) + EPS
253    }
254}
255
256/// Ellipse with semi-axes `rx`, `ry`, axis-aligned about `center`.
257#[derive(Debug, Clone, Copy, PartialEq)]
258pub struct Ellipse {
259    pub center: Point2,
260    pub rx: f64,
261    pub ry: f64,
262}
263
264impl Ellipse {
265    /// Panics if `rx < 0` or `ry < 0`.
266    pub fn new(center: Point2, rx: f64, ry: f64) -> Ellipse {
267        assert!(rx >= 0.0 && ry >= 0.0, "ellipse semi-axes must be non-negative");
268        Ellipse { center, rx, ry }
269    }
270    pub fn area(&self) -> f64 {
271        PI * self.rx * self.ry
272    }
273    /// Ramanujan's approximation (error < 0.04% for all eccentricities).
274    pub fn perimeter(&self) -> f64 {
275        let s = self.rx + self.ry;
276        PI * (3.0 * s - ((3.0 * self.rx + self.ry) * (self.rx + 3.0 * self.ry)).sqrt())
277    }
278    pub fn centroid(&self) -> Point2 {
279        self.center
280    }
281    pub fn contains(&self, p: Point2) -> bool {
282        let dx = (p.x - self.center.x) / self.rx;
283        let dy = (p.y - self.center.y) / self.ry;
284        dx * dx + dy * dy <= 1.0
285    }
286}
287
288#[cfg(test)]
289mod tests {
290    use super::*;
291
292    #[test]
293    fn point_ops() {
294        let p = Point2::new(1.0, 2.0);
295        assert_eq!(p.distance_to(Point2::new(4.0, 6.0)), 5.0);
296        assert_eq!(p.translate(2.0, -1.0), Point2::new(3.0, 1.0));
297        assert_eq!(p.scale(2.0), Point2::new(2.0, 4.0));
298        let r = Point2::new(1.0, 0.0).rotate(PI / 2.0);
299        assert!((r.x - 0.0).abs() < 1e-12 && (r.y - 1.0).abs() < 1e-12);
300        assert_eq!(p.rotate_around(PI, Point2::new(1.0, 2.0)), Point2::new(1.0, 2.0));
301    }
302
303    #[test]
304    fn circle() {
305        let c = Circle::new(Point2::new(0.0, 0.0), 2.0);
306        assert!((c.area() - 4.0 * PI).abs() < 1e-12);
307        assert!((c.perimeter() - 4.0 * PI).abs() < 1e-12);
308        assert!(c.contains(Point2::new(1.0, 1.0)));
309        assert!(!c.contains(Point2::new(2.0, 2.0)));
310        // intersection: unit circles at (0,0) and (1,0) cross at (0.5, ±√3/2)
311        let a = Circle::new(Point2::new(0.0, 0.0), 1.0);
312        let b = Circle::new(Point2::new(1.0, 0.0), 1.0);
313        assert!(a.intersects(&b));
314        let pts = a.intersection_points(&b);
315        assert_eq!(pts.len(), 2);
316        for p in &pts {
317            assert!((p.x - 0.5).abs() < 1e-12);
318            assert!((p.y.abs() - 3.0f64.sqrt() / 2.0).abs() < 1e-12);
319        }
320        // tangent circles: one point
321        let c = Circle::new(Point2::new(2.0, 0.0), 1.0);
322        assert_eq!(a.intersection_points(&c).len(), 1);
323        // separated: none
324        let d = Circle::new(Point2::new(5.0, 0.0), 1.0);
325        assert!(!a.intersects(&d));
326        assert!(a.intersection_points(&d).is_empty());
327    }
328
329    #[test]
330    fn triangle() {
331        let t = Triangle::new(Point2::new(0.0, 0.0), Point2::new(4.0, 0.0), Point2::new(0.0, 3.0));
332        assert_eq!(t.area(), 6.0);
333        assert_eq!(t.perimeter(), 12.0);
334        let c = t.centroid();
335        assert!((c.x - 4.0 / 3.0).abs() < 1e-12 && (c.y - 1.0).abs() < 1e-12);
336    }
337
338    #[test]
339    fn rectangle() {
340        let r = Rectangle::new(0.0, 0.0, 3.0, 4.0);
341        assert_eq!(r.area(), 12.0);
342        assert_eq!(r.perimeter(), 14.0);
343        assert_eq!(r.centroid(), Point2::new(1.5, 2.0));
344        assert!(r.contains(Point2::new(1.0, 2.0)));
345        assert!(!r.contains(Point2::new(-1.0, 0.0)));
346        assert!(r.intersects(&Rectangle::new(2.0, 2.0, 2.0, 2.0)));
347        assert!(!r.intersects(&Rectangle::new(4.0, 4.0, 1.0, 1.0)));
348    }
349
350    #[test]
351    fn polygon() {
352        let sq = Polygon::new(vec![
353            Point2::new(0.0, 0.0),
354            Point2::new(2.0, 0.0),
355            Point2::new(2.0, 2.0),
356            Point2::new(0.0, 2.0),
357        ]);
358        assert_eq!(sq.area(), 4.0);
359        assert_eq!(sq.perimeter(), 8.0);
360        assert_eq!(sq.centroid(), Point2::new(1.0, 1.0));
361    }
362
363    #[test]
364    fn polygon_contains() {
365        let sq = Polygon::new(vec![
366            Point2::new(0.0, 0.0),
367            Point2::new(2.0, 0.0),
368            Point2::new(2.0, 2.0),
369            Point2::new(0.0, 2.0),
370        ]);
371        assert!(sq.contains(Point2::new(1.0, 1.0)));
372        assert!(!sq.contains(Point2::new(3.0, 1.0)));
373        assert!(!sq.contains(Point2::new(1.0, -1.0)));
374        // Boundary counts as inside.
375        assert!(sq.contains(Point2::new(0.0, 1.0)));
376        assert!(sq.contains(Point2::new(2.0, 2.0)));
377        // Concave polygon (L-shape).
378        let l = Polygon::new(vec![
379            Point2::new(0.0, 0.0),
380            Point2::new(3.0, 0.0),
381            Point2::new(3.0, 3.0),
382            Point2::new(2.0, 3.0),
383            Point2::new(2.0, 1.0),
384            Point2::new(0.0, 1.0),
385        ]);
386        assert!(l.contains(Point2::new(0.5, 0.5)));
387        assert!(l.contains(Point2::new(2.5, 2.5)));
388        assert!(l.contains(Point2::new(2.5, 0.5)));
389        // Outside the notch of the L.
390        assert!(!l.contains(Point2::new(1.0, 2.0)));
391        assert!(!l.contains(Point2::new(2.5, 3.5)));
392    }
393
394    #[test]
395    fn ellipse() {
396        let e = Ellipse::new(Point2::new(0.0, 0.0), 2.0, 1.0);
397        assert!((e.area() - 2.0 * PI).abs() < 1e-12);
398        assert!(e.contains(Point2::new(1.9, 0.0)));
399        assert!(!e.contains(Point2::new(2.1, 0.0)));
400        assert!(!e.contains(Point2::new(0.0, 1.1)));
401    }
402}