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