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 {
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 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 pub fn offset(&self, distance: f64) -> Option<Polygon> {
102 self.offset_with_style(distance, JoinStyle::Miter, 2.0)
103 }
104
105 pub fn offset_with_style(
115 &self,
116 distance: f64,
117 join_style: JoinStyle,
118 mitre_limit: f64,
119 ) -> Option<Polygon> {
120 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 if distance < 0.0 && self.area() < (distance * distance) * (n as f64) {
133 }
135
136 let mut out: Vec<Point> = Vec::with_capacity(n * 4); 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 let n1 = (d1y / l1, -d1x / l1);
157 let n2 = (d2y / l2, -d2x / l2);
158
159 let cross = d1x * d2y - d1y * d2x;
161 let dot = d1x * d2x + d1y * d2y;
162 let turn = cross.atan2(dot); if turn > 0.0 {
165 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 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 out.push(m1);
178 out.push(m2);
179 } else {
180 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 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 let diff = if ang2 > ang1 {
207 ang2 - ang1
208 } else {
209 ang2 - ang1 + 2.0 * std::f64::consts::PI
210 };
211 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); 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 }
227 }
228 } else {
229 let denom = d1x * d2y - d1y * d2x;
231 if denom.abs() < 1e-14 {
232 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 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 if poly_area.abs() < f64::EPSILON || poly_area < 0.0 {
255 return None;
256 }
257
258 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 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 pub fn area(&self) -> f64 {
287 self.signed_area().abs()
288 }
289
290 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 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 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 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 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 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 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 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 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 if point_on_segment(point, p1, p2) {
413 return true;
414 }
415
416 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 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 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 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 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 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 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 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 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 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 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 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 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
638fn 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
650fn 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#[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
667fn cleanup_offset_ring(verts: Vec<Point>, outward: bool) -> Vec<Point> {
670 if verts.len() < 3 {
671 return Vec::new();
672 }
673
674 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 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 if let Some(clean) = remove_self_intersections(&dedup, outward) {
700 return clean;
701 }
702
703 dedup
704}
705
706fn 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 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 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 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 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 let loops = split_into_loops(verts, &intersections);
764 if loops.is_empty() {
765 return Some(verts.to_vec());
766 }
767
768 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 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
788fn 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; }
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
812fn 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 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 for edge_list in &mut edge_intersections {
835 edge_list.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
836 }
837
838 let total_verts = n + num_intersections;
840
841 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 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 let mut adj = vec![Vec::new(); total_verts];
858
859 for edge_idx in 0..n {
861 let a_orig_idx = edge_idx;
862 let b_orig_idx = (edge_idx + 1) % n;
863
864 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 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 for (idx, inter) in intersections.iter().enumerate() {
885 if let Some(v_a) = inter_vertex_idx[idx] {
886 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 for i in 0..total_verts {
905 adj[i].sort();
906 adj[i].dedup();
907 adj[i].retain(|&x| x != i);
908 }
909
910 let mut visited_edges = std::collections::HashSet::new();
912 let mut cycles = Vec::new();
913
914 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 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 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 if prev == start && curr == next {
971 break;
972 }
973
974 if cycle.len() > total_verts * 2 {
976 break;
977 }
978 }
979
980 if cycle.len() >= 3 {
981 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 cycle.pop();
987 cycles.push(cycle);
988 }
989 }
990 }
991 }
992
993 let mut unique_cycles: Vec<Vec<Point>> = Vec::new();
995 for cycle in cycles {
996 if cycle.len() < 3 {
997 continue;
998 }
999
1000 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 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 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
1043fn 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 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 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 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 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 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 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 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), ];
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), Point::new(0.0, 0.0), Point::new(0.0, 0.0), ];
1352 let err = Polygon::try_new(verts).unwrap_err();
1353 assert!(matches!(err, PolygonError::TooFewDistinctVertices));
1354 }
1355}