1use super::Point;
2
3#[derive(Debug, Clone, PartialEq)]
4pub enum PolygonError {
5 TooFewVertices,
7 TooFewDistinctVertices,
9 NonFiniteVertex(usize),
11 ZeroArea,
13 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 {
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 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 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 pub fn offset(&self, distance: f64) -> Option<Polygon> {
143 self.offset_with_style(distance, JoinStyle::Miter, 2.0)
144 }
145
146 pub fn offset_with_style(
156 &self,
157 distance: f64,
158 join_style: JoinStyle,
159 mitre_limit: f64,
160 ) -> Option<Polygon> {
161 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 if distance < 0.0 && self.area() < (distance * distance) * (n as f64) {
174 }
176
177 let mut out: Vec<Point> = Vec::with_capacity(n * 4); 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 let n1 = (d1y / l1, -d1x / l1);
198 let n2 = (d2y / l2, -d2x / l2);
199
200 let cross = d1x * d2y - d1y * d2x;
202 let dot = d1x * d2x + d1y * d2y;
203 let turn = cross.atan2(dot); if turn > 0.0 {
206 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 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 out.push(m1);
219 out.push(m2);
220 } else {
221 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 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 let diff = if ang2 > ang1 {
248 ang2 - ang1
249 } else {
250 ang2 - ang1 + 2.0 * std::f64::consts::PI
251 };
252 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); 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 }
268 }
269 } else {
270 let denom = d1x * d2y - d1y * d2x;
272 if denom.abs() < 1e-14 {
273 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 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 if poly_area.abs() < f64::EPSILON || poly_area < 0.0 {
296 return None;
297 }
298
299 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 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 pub fn area(&self) -> f64 {
328 self.signed_area().abs()
329 }
330
331 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 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 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 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 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; let mut qx = 0.0; let mut qy = 0.0; 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 / (3.0 * area2), qy / (3.0 * area2))
440 }
441
442 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 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 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 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 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 if point_on_segment(point, p1, p2) {
544 return true;
545 }
546
547 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 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 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 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 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 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 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 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 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 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 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 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 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
769fn 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
781fn 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#[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
798fn cleanup_offset_ring(verts: Vec<Point>, outward: bool) -> Vec<Point> {
801 if verts.len() < 3 {
802 return Vec::new();
803 }
804
805 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 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 if let Some(clean) = remove_self_intersections(&dedup, outward) {
831 return clean;
832 }
833
834 dedup
835}
836
837fn 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 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 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 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 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 let loops = split_into_loops(verts, &intersections);
895 if loops.is_empty() {
896 return Some(verts.to_vec());
897 }
898
899 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 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
919fn 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; }
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
943fn 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 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 for edge_list in &mut edge_intersections {
966 edge_list.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
967 }
968
969 let total_verts = n + num_intersections;
971
972 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 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 let mut adj = vec![Vec::new(); total_verts];
989
990 for edge_idx in 0..n {
992 let a_orig_idx = edge_idx;
993 let b_orig_idx = (edge_idx + 1) % n;
994
995 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 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 for (idx, inter) in intersections.iter().enumerate() {
1016 if let Some(v_a) = inter_vertex_idx[idx] {
1017 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 for i in 0..total_verts {
1036 adj[i].sort();
1037 adj[i].dedup();
1038 adj[i].retain(|&x| x != i);
1039 }
1040
1041 let mut visited_edges = std::collections::HashSet::new();
1043 let mut cycles = Vec::new();
1044
1045 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 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 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 if prev == start && curr == next {
1102 break;
1103 }
1104
1105 if cycle.len() > total_verts * 2 {
1107 break;
1108 }
1109 }
1110
1111 if cycle.len() >= 3 {
1112 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 cycle.pop();
1118 cycles.push(cycle);
1119 }
1120 }
1121 }
1122 }
1123
1124 let mut unique_cycles: Vec<Vec<Point>> = Vec::new();
1126 for cycle in cycles {
1127 if cycle.len() < 3 {
1128 continue;
1129 }
1130
1131 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 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 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
1174fn 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 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 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 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 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 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 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 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), ];
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), Point::new(0.0, 0.0), Point::new(0.0, 0.0), ];
1483 let err = Polygon::try_new(verts).unwrap_err();
1484 assert!(matches!(err, PolygonError::TooFewDistinctVertices));
1485 }
1486}