Skip to main content

section_properties/geometry/
polygon.rs

1use super::Point;
2
3#[derive(Debug, Clone, PartialEq)]
4pub enum PolygonError {
5    /// Polygon has fewer than 3 vertices.
6    TooFewVertices,
7    /// After deduplication, fewer than 3 distinct vertices remain.
8    TooFewDistinctVertices,
9    /// A vertex has non-finite coordinates.
10    NonFiniteVertex(usize),
11    /// Polygon has zero or near-zero area.
12    ZeroArea,
13    /// Polygon has self-intersections (non-adjacent edges cross).
14    SelfIntersection,
15}
16
17impl std::fmt::Display for PolygonError {
18    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
19        match self {
20            PolygonError::TooFewVertices => write!(f, "polygon needs at least 3 vertices"),
21            PolygonError::TooFewDistinctVertices => {
22                write!(f, "polygon needs at least 3 distinct vertices")
23            }
24            PolygonError::NonFiniteVertex(i) => {
25                write!(f, "vertex {} has non-finite coordinates", i)
26            }
27            PolygonError::ZeroArea => write!(f, "polygon has zero or near-zero area"),
28            PolygonError::SelfIntersection => write!(f, "polygon has self-intersections"),
29        }
30    }
31}
32
33impl std::error::Error for PolygonError {}
34
35#[derive(Debug, Clone, Copy, PartialEq)]
36pub enum JoinStyle {
37    Miter,
38    Round,
39    Bevel,
40}
41
42impl Default for JoinStyle {
43    fn default() -> Self {
44        JoinStyle::Miter
45    }
46}
47
48#[derive(Debug, Clone)]
49pub struct Polygon {
50    pub vertices: Vec<Point>,
51}
52
53impl Polygon {
54    pub fn new(vertices: Vec<Point>) -> Self {
55        assert!(vertices.len() >= 3, "Polygon needs at least 3 vertices");
56
57        for (i, v) in vertices.iter().enumerate() {
58            assert!(
59                v.x.is_finite() && v.y.is_finite(),
60                "Polygon vertex {} is not finite: ({}, {})",
61                i,
62                v.x,
63                v.y
64            );
65        }
66
67        // Remove consecutive duplicate vertices (zero-length edges) and a
68        // trailing vertex that closes back on the first (closed-ring convention).
69        let mut dedup: Vec<Point> = Vec::with_capacity(vertices.len());
70        for v in &vertices {
71            if dedup.last().map_or(true, |p| *p != *v) {
72                dedup.push(*v);
73            }
74        }
75        if dedup.len() > 1 && dedup[0] == *dedup.last().unwrap() {
76            dedup.pop();
77        }
78
79        assert!(
80            dedup.len() >= 3,
81            "Polygon needs at least 3 distinct vertices"
82        );
83
84        let poly = Self { vertices: dedup };
85        assert!(
86            poly.signed_area().abs() > f64::EPSILON,
87            "Polygon has (near-)zero area"
88        );
89
90        poly
91    }
92
93    /// Offset the polygon by `distance` using mitred corners.
94    ///
95    /// Positive distances grow a CCW polygon outward; negative distances shrink
96    /// it. Returns `None` if the offset polygon degenerates (e.g. an inward
97    /// offset larger than the polygon size).
98    ///
99    /// Mirrors shapely's `buffer(distance, join_style=mitre)` used by Python
100    /// `sectionproperties`' `Geometry.offset()`.
101    pub fn offset(&self, distance: f64) -> Option<Polygon> {
102        self.offset_with_style(distance, JoinStyle::Miter, 2.0)
103    }
104
105    /// Offset the polygon with explicit join style and mitre limit.
106    ///
107    /// `join_style` controls corner treatment:
108    /// - `Miter`: Extend offset edges until they intersect (default)
109    /// - `Round`: Arc of radius |distance| (approximated with segments)
110    /// - `Bevel`: Connect offset edges with a single segment
111    ///
112    /// `mitre_limit` (only for Miter) caps the mitre length to `mitre_limit * |distance|`.
113    /// Exceeding corners are bevelled instead. Typical value: 2.0.
114    pub fn offset_with_style(
115        &self,
116        distance: f64,
117        join_style: JoinStyle,
118        mitre_limit: f64,
119    ) -> Option<Polygon> {
120        // Work with CCW orientation so that positive = grow.
121        let ccw: Vec<Point> = if self.signed_area() < 0.0 {
122            self.vertices.iter().rev().copied().collect()
123        } else {
124            self.vertices.clone()
125        };
126        let n = ccw.len();
127        if n < 3 {
128            return None;
129        }
130
131        // Quick rejection: inward offset larger than inradius -> empty.
132        if distance < 0.0 && self.area() < (distance * distance) * (n as f64) {
133            // Cheap heuristic; actual degeneracy caught later.
134        }
135
136        let mut out: Vec<Point> = Vec::with_capacity(n * 4); // room for round/bevel
137        let abs_d = distance.abs();
138
139        for i in 0..n {
140            let p0 = ccw[(i + n - 1) % n];
141            let p1 = ccw[i];
142            let p2 = ccw[(i + 1) % n];
143
144            let d1x = p1.x - p0.x;
145            let d1y = p1.y - p0.y;
146            let d2x = p2.x - p1.x;
147            let d2y = p2.y - p1.y;
148
149            let l1 = (d1x * d1x + d1y * d1y).sqrt();
150            let l2 = (d2x * d2x + d2y * d2y).sqrt();
151            if l1 < f64::EPSILON || l2 < f64::EPSILON {
152                continue;
153            }
154
155            // Outward unit normals (right side of travel direction for CCW).
156            let n1 = (d1y / l1, -d1x / l1);
157            let n2 = (d2y / l2, -d2x / l2);
158
159            // Turn angle: positive = left turn (convex outward for CCW polygon).
160            let cross = d1x * d2y - d1y * d2x;
161            let dot = d1x * d2x + d1y * d2y;
162            let turn = cross.atan2(dot); // (-PI, PI]
163
164            if turn > 0.0 {
165                // Convex corner -> mitre / round / bevel outwards
166                let m1 = Point::new(p1.x + distance * n1.0, p1.y + distance * n1.1);
167                let m2 = Point::new(p1.x + distance * n2.0, p1.y + distance * n2.1);
168
169                match join_style {
170                    JoinStyle::Miter => {
171                        // Mitre length = |distance| / cos(turn/2).
172                        // If > mitre_limit * |distance|, fall back to bevel.
173                        let half = turn * 0.5;
174                        let mitre_len = abs_d / half.cos().max(1e-12);
175                        if mitre_len > mitre_limit * abs_d {
176                            // Bevel: emit m1 then m2.
177                            out.push(m1);
178                            out.push(m2);
179                        } else {
180                            // Proper mitre: intersection of offset lines.
181                            let denom = d1x * d2y - d1y * d2x;
182                            if denom.abs() < 1e-14 {
183                                out.push(m2);
184                            } else {
185                                let ax = p0.x + distance * n1.0;
186                                let ay = p0.y + distance * n1.1;
187                                let bx = p1.x + distance * n2.0;
188                                let by = p1.y + distance * n2.1;
189                                let t = ((bx - ax) * d2y - (by - ay) * d2x) / denom;
190                                out.push(Point::new(ax + t * d1x, ay + t * d1y));
191                            }
192                        }
193                    }
194                    JoinStyle::Bevel => {
195                        out.push(m1);
196                        out.push(m2);
197                    }
198                    JoinStyle::Round => {
199                        // Approximate arc with chord segments.
200                        // Emit points along arc from m1 to m2.
201                        let cx = p1.x;
202                        let cy = p1.y;
203                        let ang1 = (m1.y - cy).atan2(m1.x - cx);
204                        let ang2 = (m2.y - cy).atan2(m2.x - cx);
205                        // CCW arc from ang1 to ang2.
206                        let diff = if ang2 > ang1 {
207                            ang2 - ang1
208                        } else {
209                            ang2 - ang1 + 2.0 * std::f64::consts::PI
210                        };
211                        // Use chord error to determine segment count: e = r * (1 - cos(dθ/2))
212                        // For small dθ: 1 - cos(dθ/2) ≈ dθ²/8, so dθ ≈ sqrt(8*e/r)
213                        // Use max_chord_error = 1e-6 (adjustable for precision needs).
214                        const MAX_CHORD_ERROR: f64 = 1e-6;
215                        let dtheta_max = (8.0 * MAX_CHORD_ERROR / abs_d)
216                            .sqrt()
217                            .min(std::f64::consts::PI / 6.0); // cap at 30°
218                        let segs = ((diff / dtheta_max).ceil() as usize).max(3);
219                        out.push(m1);
220                        for s in 1..segs {
221                            let a = ang1 + diff * (s as f64) / (segs as f64);
222                            out.push(Point::new(cx + abs_d * a.cos(), cy + abs_d * a.sin()));
223                        }
224                        // m2 will be emitted by next iteration or manually here:
225                        // Skip to avoid duplicate; next iteration emits its m1.
226                    }
227                }
228            } else {
229                // Concave corner (or straight) -> simple mitre intersection or bevel.
230                let denom = d1x * d2y - d1y * d2x;
231                if denom.abs() < 1e-14 {
232                    // Collinear edges.
233                    out.push(Point::new(p1.x + distance * n2.0, p1.y + distance * n2.1));
234                } else {
235                    let ax = p0.x + distance * n1.0;
236                    let ay = p0.y + distance * n1.1;
237                    let bx = p1.x + distance * n2.0;
238                    let by = p1.y + distance * n2.1;
239                    let t = ((bx - ax) * d2y - (by - ay) * d2x) / denom;
240                    out.push(Point::new(ax + t * d1x, ay + t * d1y));
241                }
242            }
243        }
244
245        // ---- Self-intersection cleanup & ring reconstruction ----
246        let clean = cleanup_offset_ring(out, distance > 0.0);
247        if clean.is_empty() || clean.len() < 3 {
248            return None;
249        }
250
251        let poly_area = signed_area_raw(&clean);
252        // For outward offset, expect positive area; inward, expect smaller positive area.
253        // Negative area indicates self-intersection (bowtie).
254        if poly_area.abs() < f64::EPSILON || poly_area < 0.0 {
255            return None;
256        }
257
258        // Ensure final polygon has correct orientation (CCW for positive area).
259        let final_vertices = if poly_area > 0.0 {
260            clean
261        } else {
262            clean.into_iter().rev().collect()
263        };
264
265        Some(Polygon::new(final_vertices))
266    }
267
268    /// Calculate the signed area of the polygon.
269    ///
270    /// Counter-clockwise polygon -> positive
271    /// Clockwise polygon -> negative
272    pub fn signed_area(&self) -> f64 {
273        let mut sum = 0.0;
274
275        for i in 0..self.vertices.len() {
276            let p1 = self.vertices[i];
277            let p2 = self.vertices[(i + 1) % self.vertices.len()];
278
279            sum += p1.x * p2.y - p2.x * p1.y;
280        }
281
282        0.5 * sum
283    }
284
285    /// Calculate the absolute area of the polygon.
286    pub fn area(&self) -> f64 {
287        self.signed_area().abs()
288    }
289
290    /// Calculate the centroid of the polygon.
291    pub fn centroid(&self) -> Point {
292        let signed_area = self.signed_area();
293
294        assert!(
295            signed_area.abs() > f64::EPSILON,
296            "Cannot calculate centroid of a degenerate polygon"
297        );
298
299        let mut cx = 0.0;
300        let mut cy = 0.0;
301
302        for i in 0..self.vertices.len() {
303            let p1 = self.vertices[i];
304            let p2 = self.vertices[(i + 1) % self.vertices.len()];
305
306            let cross = p1.x * p2.y - p2.x * p1.y;
307
308            cx += (p1.x + p2.x) * cross;
309            cy += (p1.y + p2.y) * cross;
310        }
311
312        Point::new(cx / (6.0 * signed_area), cy / (6.0 * signed_area))
313    }
314
315    /// Calculate the second moment of area about the global x-axis.
316    pub fn moment_of_inertia_x(&self) -> f64 {
317        let mut sum = 0.0;
318
319        for i in 0..self.vertices.len() {
320            let p1 = self.vertices[i];
321            let p2 = self.vertices[(i + 1) % self.vertices.len()];
322
323            let cross = p1.x * p2.y - p2.x * p1.y;
324
325            sum += (p1.y.powi(2) + p1.y * p2.y + p2.y.powi(2)) * cross;
326        }
327
328        sum / 12.0
329    }
330
331    /// Calculate the second moment of area about the global y-axis.
332    pub fn moment_of_inertia_y(&self) -> f64 {
333        let mut sum = 0.0;
334
335        for i in 0..self.vertices.len() {
336            let p1 = self.vertices[i];
337            let p2 = self.vertices[(i + 1) % self.vertices.len()];
338
339            let cross = p1.x * p2.y - p2.x * p1.y;
340
341            sum += (p1.x.powi(2) + p1.x * p2.x + p2.x.powi(2)) * cross;
342        }
343
344        sum / 12.0
345    }
346
347    /// Calculate the product of area about the global axes.
348    pub fn product_of_inertia_xy(&self) -> f64 {
349        let mut sum = 0.0;
350
351        for i in 0..self.vertices.len() {
352            let p1 = self.vertices[i];
353            let p2 = self.vertices[(i + 1) % self.vertices.len()];
354
355            let cross = p1.x * p2.y - p2.x * p1.y;
356
357            sum += (p1.x * p2.y + 2.0 * p1.x * p1.y + 2.0 * p2.x * p2.y + p2.x * p1.y) * cross;
358        }
359
360        sum / 24.0
361    }
362
363    /// Calculate the second moment of area about the centroidal x-axis.
364    pub fn centroidal_moment_of_inertia_x(&self) -> f64 {
365        let area = self.area();
366        let centroid = self.centroid();
367
368        self.moment_of_inertia_x() - area * centroid.y.powi(2)
369    }
370
371    /// Calculate the second moment of area about the centroidal y-axis.
372    pub fn centroidal_moment_of_inertia_y(&self) -> f64 {
373        let area = self.area();
374        let centroid = self.centroid();
375
376        self.moment_of_inertia_y() - area * centroid.x.powi(2)
377    }
378
379    /// Calculate the product of area about the centroidal axes.
380    pub fn centroidal_product_of_inertia_xy(&self) -> f64 {
381        let area = self.area();
382        let centroid = self.centroid();
383
384        self.product_of_inertia_xy() - area * centroid.x * centroid.y
385    }
386
387    /// Rotate all vertices about the origin by `angle` radians (CCW positive).
388    pub fn rotate(&self, angle: f64) -> Self {
389        Polygon::new(
390            self.vertices
391                .iter()
392                .map(|v| {
393                    Point::new(
394                        v.x * angle.cos() - v.y * angle.sin(),
395                        v.x * angle.sin() + v.y * angle.cos(),
396                    )
397                })
398                .collect(),
399        )
400    }
401
402    /// Check if a point is inside the polygon (ray casting algorithm).
403    pub fn contains_point(&self, point: Point) -> bool {
404        let mut inside = false;
405        let n = self.vertices.len();
406
407        for i in 0..n {
408            let p1 = self.vertices[i];
409            let p2 = self.vertices[(i + 1) % n];
410
411            // Check if point is on the edge
412            if point_on_segment(point, p1, p2) {
413                return true;
414            }
415
416            // Ray casting algorithm
417            if ((p1.y > point.y) != (p2.y > point.y))
418                && (point.x < (p2.x - p1.x) * (point.y - p1.y) / (p2.y - p1.y) + p1.x)
419            {
420                inside = !inside;
421            }
422        }
423
424        inside
425    }
426
427    /// Calculate the perimeter of the polygon.
428    pub fn perimeter(&self) -> f64 {
429        let mut sum = 0.0;
430        let n = self.vertices.len();
431
432        for i in 0..n {
433            let p1 = self.vertices[i];
434            let p2 = self.vertices[(i + 1) % n];
435            let dx = p2.x - p1.x;
436            let dy = p2.y - p1.y;
437            sum += (dx * dx + dy * dy).sqrt();
438        }
439
440        sum
441    }
442
443    /// Maximum fiber distance from centroid in Y direction (for section modulus).
444    pub fn max_fiber_distance_y(&self) -> f64 {
445        let centroid = self.centroid();
446        self.vertices
447            .iter()
448            .map(|v| (v.y - centroid.y).abs())
449            .fold(0.0, f64::max)
450    }
451
452    /// Maximum fiber distance from centroid in X direction (for section modulus).
453    pub fn max_fiber_distance_x(&self) -> f64 {
454        let centroid = self.centroid();
455        self.vertices
456            .iter()
457            .map(|v| (v.x - centroid.x).abs())
458            .fold(0.0, f64::max)
459    }
460    /// Clip the polygon against the half-plane `nx*x + ny*y <= c`
461    /// (`below = true`) or `>= c` (`below = false`), using
462    /// Sutherland-Hodgman clipping. Returns `None` when nothing remains.
463    pub fn clip_halfspace(&self, n_x: f64, n_y: f64, c: f64, below: bool) -> Option<Polygon> {
464        let verts = &self.vertices;
465        if verts.is_empty() {
466            return None;
467        }
468
469        let side = |p: &Point| -> f64 { n_x * p.x + n_y * p.y - c };
470
471        let mut out: Vec<Point> = Vec::new();
472        let s = verts.len();
473        let mut prev = verts[s - 1];
474        let mut prev_inside = if below {
475            side(&prev) <= 0.0
476        } else {
477            side(&prev) >= 0.0
478        };
479
480        for cur in verts.iter() {
481            let cur_inside = if below {
482                side(cur) <= 0.0
483            } else {
484                side(cur) >= 0.0
485            };
486            if prev_inside != cur_inside {
487                // Intersection with the cutting line.
488                let dp = side(&prev);
489                let dc = side(cur);
490                let t = dp / (dp - dc);
491                out.push(Point::new(
492                    prev.x + t * (cur.x - prev.x),
493                    prev.y + t * (cur.y - prev.y),
494                ));
495            }
496            if cur_inside {
497                out.push(*cur);
498            }
499            prev = *cur;
500            prev_inside = cur_inside;
501        }
502
503        if out.len() < 3 {
504            return None;
505        }
506
507        // Drop degenerate slivers safely.
508        let area: f64 = out
509            .iter()
510            .enumerate()
511            .map(|(i, p)| {
512                let q = &out[(i + 1) % out.len()];
513                p.x * q.y - q.x * p.y
514            })
515            .sum::<f64>()
516            / 2.0;
517        if area.abs() < 1e-14 {
518            return None;
519        }
520
521        Some(Polygon::new(out))
522    }
523
524    /// Split the polygon into the two halves lying either side of the line
525    /// through points `a` and `b`.
526    ///
527    /// Returns `(below, above)`; either side may be `None` when the line does
528    /// not cut the polygon. Mirrors Python `bisect_section` helpers used by
529    /// `Section.split_section`.
530    pub fn split_by_line(&self, a: Point, b: Point) -> (Option<Polygon>, Option<Polygon>) {
531        let dx = b.x - a.x;
532        let dy = b.y - a.y;
533        let len = (dx * dx + dy * dy).sqrt().max(1e-15);
534        let n_x = dy / len;
535        let n_y = -dx / len;
536        let c = n_x * a.x + n_y * a.y;
537        (
538            self.clip_halfspace(n_x, n_y, c, true),
539            self.clip_halfspace(n_x, n_y, c, false),
540        )
541    }
542
543    /// Check if the polygon has self-intersections (non-adjacent edges crossing).
544    ///
545    /// Returns `true` if any two non-adjacent edges intersect in their interiors.
546    /// This does not count shared vertices (adjacent edges) as intersections.
547    pub fn has_self_intersections(&self) -> bool {
548        let n = self.vertices.len();
549        if n < 4 {
550            return false;
551        }
552
553        for i in 0..n {
554            let a1 = self.vertices[i];
555            let a2 = self.vertices[(i + 1) % n];
556            for j in (i + 2)..n {
557                // Skip adjacent edges (share a vertex) and first/last pair.
558                if i == 0 && j == n - 1 {
559                    continue;
560                }
561                let b1 = self.vertices[j];
562                let b2 = self.vertices[(j + 1) % n];
563
564                if let Some((t_a, t_b)) = segment_intersection(a1, a2, b1, b2) {
565                    // Exclude intersections at endpoints (already shared vertices).
566                    if t_a > 1e-10 && t_a < 1.0 - 1e-10 && t_b > 1e-10 && t_b < 1.0 - 1e-10 {
567                        return true;
568                    }
569                }
570            }
571        }
572        false
573    }
574
575    /// Validating constructor: returns an error if the polygon has
576    /// self-intersections or is otherwise invalid.
577    ///
578    /// Checks:
579    /// - At least 3 distinct vertices
580    /// - All vertices are finite
581    /// - Non-zero area
582    /// - No self-intersections
583    pub fn try_new(vertices: Vec<Point>) -> Result<Self, PolygonError> {
584        if vertices.len() < 3 {
585            return Err(PolygonError::TooFewVertices);
586        }
587
588        for (i, v) in vertices.iter().enumerate() {
589            if !v.x.is_finite() || !v.y.is_finite() {
590                return Err(PolygonError::NonFiniteVertex(i));
591            }
592        }
593
594        // Remove consecutive duplicate vertices and trailing closed-ring vertex.
595        let mut dedup: Vec<Point> = Vec::with_capacity(vertices.len());
596        for v in &vertices {
597            if dedup.last().map_or(true, |p| *p != *v) {
598                dedup.push(*v);
599            }
600        }
601        if dedup.len() > 1 && dedup[0] == *dedup.last().unwrap() {
602            dedup.pop();
603        }
604
605        if dedup.len() < 3 {
606            return Err(PolygonError::TooFewDistinctVertices);
607        }
608
609        let poly = Self { vertices: dedup };
610
611        if poly.signed_area().abs() <= f64::EPSILON {
612            return Err(PolygonError::ZeroArea);
613        }
614
615        if poly.has_self_intersections() {
616            return Err(PolygonError::SelfIntersection);
617        }
618
619        Ok(poly)
620    }
621}
622
623impl super::boundary::BoundaryExtrema for Polygon {
624    fn extreme_distances(&self, center: Point, direction: Point) -> (f64, f64) {
625        self.vertices
626            .iter()
627            .map(|v| {
628                let dx = v.x - center.x;
629                let dy = v.y - center.y;
630                dx * direction.x + dy * direction.y
631            })
632            .fold((f64::INFINITY, f64::NEG_INFINITY), |(mn, mx), d| {
633                (mn.min(d), mx.max(d))
634            })
635    }
636}
637
638/// Compute signed area of a raw vertex list (assumed closed).
639fn signed_area_raw(verts: &[Point]) -> f64 {
640    let mut sum = 0.0;
641    let n = verts.len();
642    for i in 0..n {
643        let p1 = verts[i];
644        let p2 = verts[(i + 1) % n];
645        sum += p1.x * p2.y - p2.x * p1.y;
646    }
647    0.5 * sum
648}
649
650/// Distance squared between two points.
651fn distance_sq(a: Point, b: Point) -> f64 {
652    let dx = a.x - b.x;
653    let dy = a.y - b.y;
654    dx * dx + dy * dy
655}
656
657/// Internal intersection representation for self-intersection cleanup.
658#[allow(dead_code)]
659struct Intersection {
660    edge_a: usize,
661    edge_b: usize,
662    t_a: f64,
663    t_b: f64,
664    point: Point,
665}
666
667/// Remove zero-length edges, near-duplicate vertices, and fix self-intersections
668/// in the offset ring. Returns a cleaned vertex list (still CCW if possible).
669fn cleanup_offset_ring(verts: Vec<Point>, outward: bool) -> Vec<Point> {
670    if verts.len() < 3 {
671        return Vec::new();
672    }
673
674    // 1. Remove consecutive near-duplicate vertices.
675    let eps = 1e-12;
676    let mut dedup: Vec<Point> = Vec::with_capacity(verts.len());
677    for v in &verts {
678        if dedup
679            .last()
680            .map_or(true, |p| distance_sq(*p, *v) > eps * eps)
681        {
682            dedup.push(*v);
683        }
684    }
685    // Close check: first vs last
686    if dedup.len() > 1 && distance_sq(dedup[0], *dedup.last().unwrap()) < eps * eps {
687        dedup.pop();
688    }
689    if dedup.len() < 3 {
690        return Vec::new();
691    }
692
693    // 2. Detect and remove self-intersections by finding simple polygon loops.
694    // TODO: Current implementation is a pragmatic fallback, not topologically correct.
695    // split_into_loops() is a stub; "largest loop" heuristic fails for complex
696    // concave sections (cold-formed C/Z/Σ) where true offset has multiple valid regions.
697    // Proper fix: implement Vatti/Greiner-Hormann clipping or integrate Clipper/GEOS
698    // for true polygon buffer / ring reconstruction.
699    if let Some(clean) = remove_self_intersections(&dedup, outward) {
700        return clean;
701    }
702
703    dedup
704}
705
706/// Find self-intersections and return the largest valid simple loop.
707fn remove_self_intersections(verts: &[Point], outward: bool) -> Option<Vec<Point>> {
708    let n = verts.len();
709    if n < 4 {
710        return Some(verts.to_vec());
711    }
712
713    // Find all intersection points between non-adjacent edges.
714    let mut intersections = Vec::new();
715
716    for i in 0..n {
717        let a1 = verts[i];
718        let a2 = verts[(i + 1) % n];
719        for j in (i + 2)..n {
720            // Skip adjacent edges (share a vertex) and first/last pair.
721            if i == 0 && j == n - 1 {
722                continue;
723            }
724            let b1 = verts[j];
725            let b2 = verts[(j + 1) % n];
726
727            if let Some((t_a, t_b)) = segment_intersection(a1, a2, b1, b2) {
728                // Exclude intersections at endpoints (already shared vertices).
729                if t_a > 1e-10 && t_a < 1.0 - 1e-10 && t_b > 1e-10 && t_b < 1.0 - 1e-10 {
730                    let px = a1.x + t_a * (a2.x - a1.x);
731                    let py = a1.y + t_a * (a2.y - a1.y);
732                    intersections.push(Intersection {
733                        edge_a: i,
734                        edge_b: j,
735                        t_a,
736                        t_b,
737                        point: Point::new(px, py),
738                    });
739                }
740            }
741        }
742    }
743
744    if intersections.is_empty() {
745        return Some(verts.to_vec());
746    }
747
748    // Sort intersections by edge_a, then t_a.
749    intersections.sort_by(|a, b| {
750        a.edge_a
751            .cmp(&b.edge_a)
752            .then(a.t_a.partial_cmp(&b.t_a).unwrap())
753    });
754
755    // Build split points per edge.
756    // We'll reconstruct the polygon by walking along edges and inserting intersection vertices.
757    // For simplicity and robustness in engineering contexts, we use a different approach:
758    // sample the polygon and use winding to keep the "correct" region.
759    // But here we just keep the largest simple sub-loop by area.
760    // This is a pragmatic fix for typical offset self-intersections.
761
762    // Split into loops at intersections.
763    let loops = split_into_loops(verts, &intersections);
764    if loops.is_empty() {
765        return Some(verts.to_vec());
766    }
767
768    // Pick the loop with largest absolute area that has correct orientation.
769    let mut best: Option<Vec<Point>> = None;
770    let mut best_area = 0.0;
771    for loop_verts in loops {
772        if loop_verts.len() < 3 {
773            continue;
774        }
775        let area = signed_area_raw(&loop_verts);
776        let abs_area = area.abs();
777        // Outward offset should be CCW (positive); inward offset also positive but smaller.
778        let correct_orient = if outward { area > 0.0 } else { area > 0.0 };
779        if correct_orient && abs_area > best_area {
780            best_area = abs_area;
781            best = Some(loop_verts);
782        }
783    }
784
785    best
786}
787
788/// Check if two segments intersect and return (t_a, t_b) parameters.
789fn segment_intersection(a1: Point, a2: Point, b1: Point, b2: Point) -> Option<(f64, f64)> {
790    let dx1 = a2.x - a1.x;
791    let dy1 = a2.y - a1.y;
792    let dx2 = b2.x - b1.x;
793    let dy2 = b2.y - b1.y;
794
795    let denom = dx1 * dy2 - dy1 * dx2;
796    if denom.abs() < 1e-14 {
797        return None; // Parallel or collinear
798    }
799
800    let dx3 = b1.x - a1.x;
801    let dy3 = b1.y - a1.y;
802    let t_a = (dx3 * dy2 - dy3 * dx2) / denom;
803    let t_b = (dx3 * dy1 - dy3 * dx1) / denom;
804
805    if t_a >= 0.0 && t_a <= 1.0 && t_b >= 0.0 && t_b <= 1.0 {
806        Some((t_a, t_b))
807    } else {
808        None
809    }
810}
811
812/// Split a self-intersecting polygon into simple loops at intersection points.
813///
814/// This implements a practical version of the Vatti/Greiner-Hormann algorithm:
815/// 1. Insert intersection vertices into edge sequences
816/// 2. Build a directed graph of edge segments between vertices
817/// 3. At intersections, follow the "left-hand rule" to trace outer boundaries
818/// 4. Extract all simple cycles via graph traversal
819fn split_into_loops(verts: &[Point], intersections: &[Intersection]) -> Vec<Vec<Point>> {
820    if intersections.is_empty() {
821        return vec![verts.to_vec()];
822    }
823
824    let n = verts.len();
825    let num_intersections = intersections.len();
826
827    // Build edge_intersections: for each edge, list of (t, intersection_idx)
828    let mut edge_intersections: Vec<Vec<(f64, usize)>> = vec![Vec::new(); n];
829    for (idx, inter) in intersections.iter().enumerate() {
830        edge_intersections[inter.edge_a].push((inter.t_a, idx));
831    }
832
833    // Sort intersections on each edge by parameter t
834    for edge_list in &mut edge_intersections {
835        edge_list.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
836    }
837
838    // Total vertices = n original + num_intersections
839    let total_verts = n + num_intersections;
840
841    // Build vertex array: first n are original, then intersection points
842    let mut vertex_point = Vec::with_capacity(total_verts);
843    for &p in verts {
844        vertex_point.push(p);
845    }
846    for inter in intersections {
847        vertex_point.push(inter.point);
848    }
849
850    // Map from (edge_idx, intersection_idx) -> vertex index
851    let mut inter_vertex_idx = vec![None; num_intersections];
852    for (idx, _inter) in intersections.iter().enumerate() {
853        inter_vertex_idx[idx] = Some(n + idx);
854    }
855
856    // Build adjacency list
857    let mut adj = vec![Vec::new(); total_verts];
858
859    // Connect consecutive vertices along each original edge
860    for edge_idx in 0..n {
861        let a_orig_idx = edge_idx;
862        let b_orig_idx = (edge_idx + 1) % n;
863
864        // Collect all vertices on this edge: start, intersections..., end
865        let mut edge_verts = vec![a_orig_idx];
866
867        for &(_t, inter_idx) in &edge_intersections[edge_idx] {
868            if let Some(v_idx) = inter_vertex_idx[inter_idx] {
869                edge_verts.push(v_idx);
870            }
871        }
872        edge_verts.push(b_orig_idx);
873
874        // Connect consecutive vertices
875        for i in 0..edge_verts.len() - 1 {
876            let v1 = edge_verts[i];
877            let v2 = edge_verts[i + 1];
878            adj[v1].push(v2);
879            adj[v2].push(v1);
880        }
881    }
882
883    // Add cross-connections at intersections
884    for (idx, inter) in intersections.iter().enumerate() {
885        if let Some(v_a) = inter_vertex_idx[idx] {
886            // Find the corresponding vertex on the other edge
887            // The intersection appears on both edges with possibly different t
888            // Find the other edge's intersection with the same point
889            for (other_idx, other_inter) in intersections.iter().enumerate() {
890                if other_idx != idx
891                    && (other_inter.point.x - inter.point.x).abs() < 1e-10
892                    && (other_inter.point.y - inter.point.y).abs() < 1e-10
893                {
894                    if let Some(v_b) = inter_vertex_idx[other_idx] {
895                        adj[v_a].push(v_b);
896                        adj[v_b].push(v_a);
897                    }
898                }
899            }
900        }
901    }
902
903    // Remove duplicates and self-loops
904    for i in 0..total_verts {
905        adj[i].sort();
906        adj[i].dedup();
907        adj[i].retain(|&x| x != i);
908    }
909
910    // Extract simple cycles using edge-based traversal
911    let mut visited_edges = std::collections::HashSet::new();
912    let mut cycles = Vec::new();
913
914    // Helper to get edge key
915    let edge_key = |a: usize, b: usize| (a.min(b), a.max(b));
916
917    for start in 0..total_verts {
918        for &next in &adj[start] {
919            let ekey = edge_key(start, next);
920            if visited_edges.contains(&ekey) {
921                continue;
922            }
923
924            let mut cycle = Vec::new();
925            let mut curr = start;
926            let mut prev = next;
927
928            loop {
929                cycle.push(vertex_point[curr]);
930                visited_edges.insert(edge_key(curr, prev));
931
932                // Find next vertex
933                let neighbors = &adj[prev];
934                if neighbors.len() == 2 {
935                    let next_v = if neighbors[0] == curr {
936                        neighbors[1]
937                    } else {
938                        neighbors[0]
939                    };
940                    curr = prev;
941                    prev = next_v;
942                } else if neighbors.len() > 2 {
943                    // At intersection - apply left-hand rule for CCW outer boundary
944                    let a = vertex_point[curr];
945                    let b = vertex_point[prev];
946                    let dir = Point::new(b.x - a.x, b.y - a.y);
947
948                    let mut best_next = neighbors[0];
949                    let mut best_cross = f64::NEG_INFINITY;
950
951                    for &cand in neighbors {
952                        if cand == curr {
953                            continue;
954                        }
955                        let c = vertex_point[cand];
956                        let next_dir = Point::new(c.x - b.x, c.y - b.y);
957                        let cross = dir.x * next_dir.y - dir.y * next_dir.x;
958                        if cross > best_cross {
959                            best_cross = cross;
960                            best_next = cand;
961                        }
962                    }
963                    curr = prev;
964                    prev = best_next;
965                } else {
966                    break;
967                }
968
969                // Check if we've returned to start
970                if prev == start && curr == next {
971                    break;
972                }
973
974                // Prevent infinite loops
975                if cycle.len() > total_verts * 2 {
976                    break;
977                }
978            }
979
980            if cycle.len() >= 3 {
981                // Check if closed
982                let first = cycle[0];
983                let last = cycle[cycle.len() - 1];
984                if (first.x - last.x).abs() < 1e-10 && (first.y - last.y).abs() < 1e-10 {
985                    // Remove duplicate last point
986                    cycle.pop();
987                    cycles.push(cycle);
988                }
989            }
990        }
991    }
992
993    // Filter cycles: remove duplicates
994    let mut unique_cycles: Vec<Vec<Point>> = Vec::new();
995    for cycle in cycles {
996        if cycle.len() < 3 {
997            continue;
998        }
999
1000        // Normalize cycle: start from leftmost-bottommost vertex
1001        let mut min_idx = 0;
1002        for i in 1..cycle.len() {
1003            if cycle[i].x < cycle[min_idx].x
1004                || (cycle[i].x == cycle[min_idx].x && cycle[i].y < cycle[min_idx].y)
1005            {
1006                min_idx = i;
1007            }
1008        }
1009
1010        // Rotate to canonical form
1011        let mut canonical = Vec::with_capacity(cycle.len());
1012        for i in 0..cycle.len() {
1013            canonical.push(cycle[(min_idx + i) % cycle.len()]);
1014        }
1015
1016        // Check if already have this cycle
1017        let mut is_dup = false;
1018        for existing in &unique_cycles {
1019            if existing.len() == canonical.len() {
1020                let mut match_ = true;
1021                for i in 0..canonical.len() {
1022                    if (existing[i].x - canonical[i].x).abs() > 1e-10
1023                        || (existing[i].y - canonical[i].y).abs() > 1e-10
1024                    {
1025                        match_ = false;
1026                        break;
1027                    }
1028                }
1029                if match_ {
1030                    is_dup = true;
1031                    break;
1032                }
1033            }
1034        }
1035        if !is_dup {
1036            unique_cycles.push(canonical);
1037        }
1038    }
1039
1040    unique_cycles
1041}
1042
1043/// Helper function to check if a point is on a line segment.
1044///
1045/// The tolerance is scale-aware: it is proportional to the segment length
1046/// squared, which has the same units as the cross product (area) and the
1047/// dot product (length²).  This ensures correct behaviour for geometries
1048/// of any scale – the fixed absolute tolerance `1e-10` was only appropriate
1049/// for coordinates of order 1.
1050fn point_on_segment(p: Point, a: Point, b: Point) -> bool {
1051    let dx = b.x - a.x;
1052    let dy = b.y - a.y;
1053    let seg_len_sq = dx * dx + dy * dy;
1054    if seg_len_sq < 1e-30 {
1055        let dpx = p.x - a.x;
1056        let dpy = p.y - a.y;
1057        return dpx * dpx + dpy * dpy < 1e-30;
1058    }
1059    let tol = 1e-10 * seg_len_sq;
1060    let cross = (p.x - a.x) * dy - (p.y - a.y) * dx;
1061    if cross.abs() > tol {
1062        return false;
1063    }
1064    let dot = (p.x - a.x) * (p.x - b.x) + (p.y - a.y) * (p.y - b.y);
1065    dot <= tol
1066}
1067
1068#[cfg(test)]
1069mod tests {
1070    use super::*;
1071
1072    #[test]
1073    fn rectangle_area() {
1074        let polygon = Polygon::new(vec![
1075            Point::new(0.0, 0.0),
1076            Point::new(10.0, 0.0),
1077            Point::new(10.0, 5.0),
1078            Point::new(0.0, 5.0),
1079        ]);
1080
1081        assert_eq!(polygon.area(), 50.0);
1082    }
1083
1084    #[test]
1085    fn triangle_area() {
1086        let polygon = Polygon::new(vec![
1087            Point::new(0.0, 0.0),
1088            Point::new(4.0, 0.0),
1089            Point::new(0.0, 3.0),
1090        ]);
1091
1092        assert_eq!(polygon.area(), 6.0);
1093    }
1094
1095    #[test]
1096    fn rectangle_centroid() {
1097        let polygon = Polygon::new(vec![
1098            Point::new(0.0, 0.0),
1099            Point::new(10.0, 0.0),
1100            Point::new(10.0, 5.0),
1101            Point::new(0.0, 5.0),
1102        ]);
1103
1104        let centroid = polygon.centroid();
1105
1106        assert!((centroid.x - 5.0).abs() < 1e-12);
1107        assert!((centroid.y - 2.5).abs() < 1e-12);
1108    }
1109
1110    #[test]
1111    fn triangle_centroid() {
1112        let polygon = Polygon::new(vec![
1113            Point::new(0.0, 0.0),
1114            Point::new(4.0, 0.0),
1115            Point::new(0.0, 3.0),
1116        ]);
1117
1118        let centroid = polygon.centroid();
1119
1120        assert!((centroid.x - 4.0 / 3.0).abs() < 1e-12);
1121        assert!((centroid.y - 1.0).abs() < 1e-12);
1122    }
1123
1124    #[test]
1125    fn clockwise_polygon_has_same_centroid() {
1126        let polygon = Polygon::new(vec![
1127            Point::new(0.0, 0.0),
1128            Point::new(0.0, 5.0),
1129            Point::new(10.0, 5.0),
1130            Point::new(10.0, 0.0),
1131        ]);
1132
1133        let centroid = polygon.centroid();
1134
1135        assert!((centroid.x - 5.0).abs() < 1e-12);
1136        assert!((centroid.y - 2.5).abs() < 1e-12);
1137    }
1138
1139    #[test]
1140    fn rectangle_global_moments_of_inertia() {
1141        let polygon = Polygon::new(vec![
1142            Point::new(0.0, 0.0),
1143            Point::new(10.0, 0.0),
1144            Point::new(10.0, 5.0),
1145            Point::new(0.0, 5.0),
1146        ]);
1147
1148        let ix = polygon.moment_of_inertia_x();
1149        let iy = polygon.moment_of_inertia_y();
1150        let ixy = polygon.product_of_inertia_xy();
1151
1152        assert!((ix - 416.6666666666667).abs() < 1e-10);
1153        assert!((iy - 1666.6666666666667).abs() < 1e-10);
1154        assert!((ixy - 625.0).abs() < 1e-10);
1155    }
1156
1157    #[test]
1158    fn rectangle_centroidal_moments_of_inertia() {
1159        let polygon = Polygon::new(vec![
1160            Point::new(0.0, 0.0),
1161            Point::new(10.0, 0.0),
1162            Point::new(10.0, 5.0),
1163            Point::new(0.0, 5.0),
1164        ]);
1165
1166        let ix = polygon.centroidal_moment_of_inertia_x();
1167        let iy = polygon.centroidal_moment_of_inertia_y();
1168        let ixy = polygon.centroidal_product_of_inertia_xy();
1169
1170        assert!((ix - 104.16666666666667).abs() < 1e-10);
1171        assert!((iy - 416.6666666666667).abs() < 1e-10);
1172        assert!(ixy.abs() < 1e-10);
1173    }
1174
1175    #[test]
1176    fn triangle_centroidal_moments_of_inertia() {
1177        let polygon = Polygon::new(vec![
1178            Point::new(0.0, 0.0),
1179            Point::new(4.0, 0.0),
1180            Point::new(0.0, 3.0),
1181        ]);
1182
1183        let ix = polygon.centroidal_moment_of_inertia_x();
1184        let iy = polygon.centroidal_moment_of_inertia_y();
1185        let ixy = polygon.centroidal_product_of_inertia_xy();
1186
1187        assert!((ix - 3.0).abs() < 1e-10);
1188        assert!((iy - 5.333333333333333).abs() < 1e-10);
1189        assert!((ixy + 2.0).abs() < 1e-10);
1190    }
1191
1192    #[test]
1193    fn boundary_extrema_rectangle() {
1194        use super::super::boundary::BoundaryExtrema;
1195
1196        // 10×5 rectangle at origin.
1197        let rect = Polygon::new(vec![
1198            Point::new(0.0, 0.0),
1199            Point::new(10.0, 0.0),
1200            Point::new(10.0, 5.0),
1201            Point::new(0.0, 5.0),
1202        ]);
1203        let center = Point::new(5.0, 2.5);
1204
1205        let (y_min, y_max) = rect.extreme_y(center);
1206        assert!((y_min + 2.5).abs() < 1e-12);
1207        assert!((y_max - 2.5).abs() < 1e-12);
1208
1209        let (x_min, x_max) = rect.extreme_x(center);
1210        assert!((x_min + 5.0).abs() < 1e-12);
1211        assert!((x_max - 5.0).abs() < 1e-12);
1212    }
1213
1214    #[test]
1215    fn boundary_extrema_rotated_direction() {
1216        use super::super::boundary::BoundaryExtrema;
1217
1218        // Unit square at origin.
1219        let sq = Polygon::new(vec![
1220            Point::new(0.0, 0.0),
1221            Point::new(1.0, 0.0),
1222            Point::new(1.0, 1.0),
1223            Point::new(0.0, 1.0),
1224        ]);
1225        let center = Point::new(0.5, 0.5);
1226
1227        // 45-degree direction: (cos45, sin45).
1228        let dir = Point::new(
1229            std::f64::consts::FRAC_1_SQRT_2,
1230            std::f64::consts::FRAC_1_SQRT_2,
1231        );
1232        let (lo, hi) = sq.extreme_distances(center, dir);
1233        // Extreme points are (0,0) and (1,1); distances from center are ±√2/2.
1234        let expected = std::f64::consts::FRAC_1_SQRT_2;
1235        assert!((lo + expected).abs() < 1e-12);
1236        assert!((hi - expected).abs() < 1e-12);
1237    }
1238
1239    #[test]
1240    fn has_self_intersections_simple_rect() {
1241        let rect = Polygon::new(vec![
1242            Point::new(0.0, 0.0),
1243            Point::new(10.0, 0.0),
1244            Point::new(10.0, 5.0),
1245            Point::new(0.0, 5.0),
1246        ]);
1247        assert!(!rect.has_self_intersections());
1248    }
1249
1250    #[test]
1251    fn has_self_intersections_bowtie() {
1252        // Bow-tie with non-zero area: (0,0)-(10,0)-(0,10)-(8,8)
1253        // Edge 1 (10,0)-(0,10) crosses Edge 3 (8,8)-(0,0)
1254        let bowtie = Polygon::new(vec![
1255            Point::new(0.0, 0.0),
1256            Point::new(10.0, 0.0),
1257            Point::new(0.0, 10.0),
1258            Point::new(8.0, 8.0),
1259        ]);
1260        assert!(bowtie.has_self_intersections());
1261    }
1262
1263    #[test]
1264    fn has_self_intersections_hourglass() {
1265        // Hourglass: (0,0)-(10,0)-(5,5)-(10,10)-(0,10)
1266        // Edge 1 (10,0)-(5,5) crosses Edge 4 (0,10)-(0,0) ? No
1267        // Actually: Edge 0 (0,0)-(10,0) and Edge 2 (5,5)-(10,10) are parallel
1268        // Edge 1 (10,0)-(5,5) and Edge 3 (10,10)-(0,10) don't cross in interiors
1269        // This hourglass doesn't self-intersect in interior.
1270        // Use a proper crossing: (0,0)-(10,0)-(5,5)-(10,10)-(0,10)
1271        // Wait, this doesn't cross. Let me use a proper self-intersecting pentagon.
1272        // (0,0) -> (10,0) -> (5,10) -> (10,10) -> (0,10)
1273        // Edges: 0:(0,0)-(10,0), 1:(10,0)-(5,10), 2:(5,10)-(10,10), 3:(10,10)-(0,10), 4:(0,10)-(0,0)
1274        // Check 0 vs 2: (0,0)-(10,0) and (5,10)-(10,10) - parallel
1275        // Check 1 vs 3: (10,0)-(5,10) and (10,10)-(0,10) - cross?
1276        // dx1=-5, dy1=10; dx2=-10, dy2=0
1277        // denom = 50; t_a=2 (outside)
1278        // Hmm, let's use a simpler self-intersecting shape.
1279        // Triangle with a "spike" that crosses: (0,0)-(10,0)-(0,10)-(5,5)
1280        // Wait that's 4 vertices. Let's use: (0,0)-(10,0)-(0,10)-(8,8) which we know works.
1281        let hourglass = Polygon::new(vec![
1282            Point::new(0.0, 0.0),
1283            Point::new(10.0, 0.0),
1284            Point::new(0.0, 10.0),
1285            Point::new(8.0, 8.0),
1286        ]);
1287        assert!(hourglass.has_self_intersections());
1288    }
1289
1290    #[test]
1291    fn try_new_valid_polygon() {
1292        let verts = vec![
1293            Point::new(0.0, 0.0),
1294            Point::new(10.0, 0.0),
1295            Point::new(10.0, 5.0),
1296            Point::new(0.0, 5.0),
1297        ];
1298        let poly = Polygon::try_new(verts).unwrap();
1299        assert_eq!(poly.area(), 50.0);
1300        assert!(!poly.has_self_intersections());
1301    }
1302
1303    #[test]
1304    fn try_new_rejects_bowtie() {
1305        // Same bow-tie as above: (0,0)-(10,0)-(0,10)-(8,8)
1306        let verts = vec![
1307            Point::new(0.0, 0.0),
1308            Point::new(10.0, 0.0),
1309            Point::new(0.0, 10.0),
1310            Point::new(8.0, 8.0),
1311        ];
1312        let err = Polygon::try_new(verts).unwrap_err();
1313        assert!(matches!(err, PolygonError::SelfIntersection));
1314    }
1315
1316    #[test]
1317    fn try_new_rejects_too_few_vertices() {
1318        let err = Polygon::try_new(vec![Point::new(0.0, 0.0), Point::new(1.0, 0.0)]).unwrap_err();
1319        assert!(matches!(err, PolygonError::TooFewVertices));
1320    }
1321
1322    #[test]
1323    fn try_new_rejects_zero_area() {
1324        let verts = vec![
1325            Point::new(0.0, 0.0),
1326            Point::new(1.0, 0.0),
1327            Point::new(2.0, 0.0), // Collinear = zero area
1328        ];
1329        let err = Polygon::try_new(verts).unwrap_err();
1330        assert!(matches!(err, PolygonError::ZeroArea));
1331    }
1332
1333    #[test]
1334    fn try_new_rejects_non_finite() {
1335        let verts = vec![
1336            Point::new(0.0, 0.0),
1337            Point::new(1.0, 0.0),
1338            Point::new(f64::NAN, 1.0),
1339        ];
1340        let err = Polygon::try_new(verts).unwrap_err();
1341        assert!(matches!(err, PolygonError::NonFiniteVertex(2)));
1342    }
1343
1344    #[test]
1345    fn try_new_rejects_duplicate_vertices() {
1346        let verts = vec![
1347            Point::new(0.0, 0.0),
1348            Point::new(0.0, 0.0), // Duplicate
1349            Point::new(0.0, 0.0), // Another duplicate
1350            Point::new(0.0, 0.0), // Another duplicate
1351        ];
1352        let err = Polygon::try_new(verts).unwrap_err();
1353        assert!(matches!(err, PolygonError::TooFewDistinctVertices));
1354    }
1355}