1use super::{Point, Polygon};
2use crate::section::Section;
3
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
6pub enum Axis {
7 X,
9 Y,
11}
12
13#[derive(Debug, Clone, Copy, PartialEq)]
17pub enum Transform {
18 Translate { dx: f64, dy: f64 },
20 Rotate { angle: f64 },
22 Scale { factor: f64 },
24 MirrorX,
26 MirrorY,
28}
29
30impl Transform {
31 pub fn apply(&self, p: Point) -> Point {
33 match *self {
34 Transform::Translate { dx, dy } => Point::new(p.x + dx, p.y + dy),
35 Transform::Rotate { angle } => {
36 let (s, c) = angle.sin_cos();
37 Point::new(p.x * c - p.y * s, p.x * s + p.y * c)
38 }
39 Transform::Scale { factor } => Point::new(p.x * factor, p.y * factor),
40 Transform::MirrorX => Point::new(p.x, -p.y),
41 Transform::MirrorY => Point::new(-p.x, p.y),
42 }
43 }
44}
45
46#[derive(Debug, Clone)]
51pub struct Geometry {
52 pub outer: Polygon,
54 pub holes: Vec<Polygon>,
56 pub transforms: Vec<Transform>,
58}
59
60impl Geometry {
61 pub fn new(mut outer: Polygon, mut holes: Vec<Polygon>) -> Self {
67 if outer.signed_area() < 0.0 {
68 outer.vertices.reverse();
69 }
70 for hole in &mut holes {
71 if hole.signed_area() > 0.0 {
72 hole.vertices.reverse();
73 }
74 }
75 Self {
76 outer,
77 holes,
78 transforms: Vec::new(),
79 }
80 }
81
82 pub fn from_points(points: Vec<Point>, holes: Vec<Vec<Point>>) -> Self {
86 Self::new(
87 Polygon::new(points),
88 holes.into_iter().map(Polygon::new).collect(),
89 )
90 }
91
92 pub fn from_section(section: &crate::section::Section) -> Self {
94 Self::new(section.outer.clone(), section.holes.clone())
95 }
96
97 pub fn rotate(mut self, angle_degrees: f64) -> Self {
101 self.transforms.push(Transform::Rotate {
102 angle: angle_degrees.to_radians(),
103 });
104 self
105 }
106
107 pub fn rotate_about(mut self, angle_degrees: f64, point: Point) -> Self {
109 self.transforms.push(Transform::Translate {
110 dx: -point.x,
111 dy: -point.y,
112 });
113 self.transforms.push(Transform::Rotate {
114 angle: angle_degrees.to_radians(),
115 });
116 self.transforms.push(Transform::Translate {
117 dx: point.x,
118 dy: point.y,
119 });
120 self
121 }
122
123 pub fn mirror(mut self, axis: Axis) -> Self {
128 self.transforms.push(match axis {
129 Axis::X => Transform::MirrorX,
130 Axis::Y => Transform::MirrorY,
131 });
132 self
133 }
134
135 pub fn shift(mut self, dx: f64, dy: f64) -> Self {
139 self.transforms.push(Transform::Translate { dx, dy });
140 self
141 }
142
143 pub fn align_center(&self) -> Self {
147 let c = self.centroid();
148 let mut g = self.clone();
149 g.transforms
150 .push(Transform::Translate { dx: -c.x, dy: -c.y });
151 g
152 }
153
154 pub fn align_to(&self, other: &Self) -> Self {
160 let (l1, r1, b1, t1) = self.bounds();
161 let (l2, r2, b2, t2) = other.bounds();
162
163 let dx = if (l1 - l2).abs() < (r1 - r2).abs() {
164 l2 - l1
165 } else {
166 r2 - r1
167 };
168 let dy = if (b1 - b2).abs() < (t1 - t2).abs() {
169 b2 - b1
170 } else {
171 t2 - t1
172 };
173
174 if dx == 0.0 && dy == 0.0 {
175 return self.clone();
176 }
177 let mut g = self.clone();
178 g.transforms.push(Transform::Translate { dx, dy });
179 g
180 }
181
182 pub fn offset(&self, amount: f64) -> Option<Self> {
190 let outer = self.apply_transforms().outer.offset(amount)?;
191 let mut holes = Vec::with_capacity(self.holes.len());
192 for h in &self.holes {
193 holes.push(h.offset(-amount)?);
194 }
195 Some(Self {
196 outer,
197 holes,
198 transforms: Vec::new(),
199 })
200 }
201
202 pub fn split_section(&self, a: Point, b: Point) -> (Option<Geometry>, Option<Geometry>) {
208 let g = self.apply_transforms();
209 let (below_outer, above_outer) = g.outer.split_by_line(a, b);
210
211 let mut below_holes = Vec::new();
213 let mut above_holes = Vec::new();
214 for h in &g.holes {
215 let (hb, ha) = h.split_by_line(a, b);
216 if let Some(hb) = hb {
217 below_holes.push(hb);
218 }
219 if let Some(ha) = ha {
220 above_holes.push(ha);
221 }
222 }
223
224 let below = below_outer.map(|o| Geometry {
225 outer: o,
226 holes: below_holes,
227 transforms: Vec::new(),
228 });
229 let above = above_outer.map(|o| Geometry {
230 outer: o,
231 holes: above_holes,
232 transforms: Vec::new(),
233 });
234 (below, above)
235 }
236 pub fn union(&self, other: &Self) -> Result<CompoundGeometry, super::boolean::BooleanError> {
241 self.boolean_op(other, super::boolean::BoolOp::Union)
242 }
243
244 pub fn intersection(
249 &self,
250 other: &Self,
251 ) -> Result<CompoundGeometry, super::boolean::BooleanError> {
252 self.boolean_op(other, super::boolean::BoolOp::Intersection)
253 }
254
255 pub fn subtract(&self, other: &Self) -> Result<CompoundGeometry, super::boolean::BooleanError> {
260 self.boolean_op(other, super::boolean::BoolOp::Difference)
261 }
262
263 fn boolean_op(
264 &self,
265 other: &Self,
266 op: super::boolean::BoolOp,
267 ) -> Result<CompoundGeometry, super::boolean::BooleanError> {
268 let a_trans = self.apply_transforms();
269 let b_trans = other.apply_transforms();
270 let a = Section::new(a_trans.outer, a_trans.holes);
271 let b = Section::new(b_trans.outer, b_trans.holes);
272
273 let results = match op {
274 super::boolean::BoolOp::Union => super::boolean::section_union(&a, &b)?,
275 super::boolean::BoolOp::Intersection => super::boolean::section_intersection(&a, &b)?,
276 super::boolean::BoolOp::Difference => super::boolean::section_difference(&a, &b)?,
277 };
278
279 let geometries = results
280 .into_iter()
281 .map(|sec| Geometry::new(sec.outer, sec.holes))
282 .collect();
283 Ok(CompoundGeometry::new(geometries))
284 }
285
286 pub fn apply_transforms(&self) -> Self {
290 if self.transforms.is_empty() {
291 return self.clone();
292 }
293 let map = |poly: &Polygon| -> Polygon {
294 Polygon::new(
295 poly.vertices
296 .iter()
297 .map(|&v| self.transforms.iter().fold(v, |p, t| t.apply(p)))
298 .collect(),
299 )
300 };
301 Self {
302 outer: map(&self.outer),
303 holes: self.holes.iter().map(map).collect(),
304 transforms: Vec::new(),
305 }
306 }
307
308 pub fn area(&self) -> f64 {
310 let g = if self.transforms.is_empty() {
311 self
312 } else {
313 &self.apply_transforms()
314 };
315 let mut a = g.outer.area();
316 for h in &g.holes {
317 a -= h.area();
318 }
319 a
320 }
321
322 pub fn centroid(&self) -> Point {
324 let g = if self.transforms.is_empty() {
325 self
326 } else {
327 &self.apply_transforms()
328 };
329 let mut sum_x = 0.0;
330 let mut sum_y = 0.0;
331 let mut total = 0.0;
332
333 let outer_c = g.outer.centroid();
334 let outer_a = g.outer.area();
335 sum_x += outer_c.x * outer_a;
336 sum_y += outer_c.y * outer_a;
337 total += outer_a;
338
339 for h in &g.holes {
340 let a = h.area();
341 let c = h.centroid();
342 sum_x -= c.x * a;
343 sum_y -= c.y * a;
344 total -= a;
345 }
346
347 Point::new(sum_x / total, sum_y / total)
348 }
349
350 pub fn bounds(&self) -> (f64, f64, f64, f64) {
352 let g = if self.transforms.is_empty() {
353 self
354 } else {
355 &self.apply_transforms()
356 };
357 let mut min_x = f64::INFINITY;
358 let mut max_x = f64::NEG_INFINITY;
359 let mut min_y = f64::INFINITY;
360 let mut max_y = f64::NEG_INFINITY;
361 for poly in std::iter::once(&g.outer).chain(g.holes.iter()) {
362 for v in &poly.vertices {
363 min_x = min_x.min(v.x);
364 max_x = max_x.max(v.x);
365 min_y = min_y.min(v.y);
366 max_y = max_y.max(v.y);
367 }
368 }
369 (min_x, max_x, min_y, max_y)
370 }
371
372 pub fn perimeter(&self) -> f64 {
374 let g = if self.transforms.is_empty() {
375 self
376 } else {
377 &self.apply_transforms()
378 };
379 g.outer.perimeter() + g.holes.iter().map(|h| h.perimeter()).sum::<f64>()
380 }
381}
382
383#[derive(Debug, Clone)]
398pub struct CompoundGeometry {
399 pub geometries: Vec<Geometry>,
401}
402
403#[derive(Debug, Clone, PartialEq)]
405pub enum CompoundError {
406 OverlappingRegions { a: usize, b: usize },
408 HoleNotInsideOuter { region: usize, hole: usize },
411 NestedHoles { region: usize, a: usize, b: usize },
415}
416
417impl std::fmt::Display for CompoundError {
418 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
419 match self {
420 CompoundError::OverlappingRegions { a, b } => {
421 write!(f, "regions {a} and {b} have overlapping material")
422 }
423 CompoundError::HoleNotInsideOuter { region, hole } => {
424 write!(
425 f,
426 "hole {hole} of region {region} is not fully inside its outer boundary"
427 )
428 }
429 CompoundError::NestedHoles { region, a, b } => {
430 write!(
431 f,
432 "region {region} has hole {b} nested inside hole {a} (holes cannot nest)"
433 )
434 }
435 }
436 }
437}
438
439impl std::error::Error for CompoundError {}
440
441#[derive(Debug, Clone, Copy, PartialEq, Eq)]
443enum BBoxRelation {
444 Disjoint,
446 Touch,
448 Overlap,
450}
451
452fn outer_bbox_relation(a: &Polygon, b: &Polygon) -> BBoxRelation {
456 let bbox = |pts: &[Point]| {
457 pts.iter().fold(
458 (
459 f64::INFINITY,
460 f64::NEG_INFINITY,
461 f64::INFINITY,
462 f64::NEG_INFINITY,
463 ),
464 |(l, r, b, t), p| (l.min(p.x), r.max(p.x), b.min(p.y), t.max(p.y)),
465 )
466 };
467 let (al, ar, ab, at) = bbox(&a.vertices);
468 let (bl, br, bb, bt) = bbox(&b.vertices);
469
470 if ar < bl || br < al || at < bb || bt < ab {
472 return BBoxRelation::Disjoint;
473 }
474
475 let x_touch = ar == bl || br == al;
478 let y_touch = at == bb || bt == ab;
479 if x_touch || y_touch {
480 return BBoxRelation::Touch;
481 }
482
483 BBoxRelation::Overlap
485}
486
487impl CompoundGeometry {
488 pub fn new(geometries: Vec<Geometry>) -> Self {
496 Self { geometries }
497 }
498
499 pub fn new_validated(geometries: Vec<Geometry>) -> Result<Self, CompoundError> {
502 let compound = Self { geometries };
503 compound.validate()?;
504 Ok(compound)
505 }
506
507 #[deprecated(
514 since = "0.1.0",
515 note = "Use dissolved_outer_only() for explicit naming; holes are dropped"
516 )]
517 pub fn dissolved(geometries: Vec<Geometry>) -> Self {
518 Self::dissolved_outer_only(geometries)
519 }
520
521 pub fn dissolved_outer_only(geometries: Vec<Geometry>) -> Self {
526 use super::boolean::{BoolOp, polygon_boolean};
527
528 let mut acc: Vec<Polygon> = geometries
529 .iter()
530 .map(|g| g.apply_transforms().outer)
531 .collect();
532
533 loop {
534 let mut merged: Option<(usize, usize, Vec<Polygon>)> = None;
535 'outer: for i in 0..acc.len() {
536 for j in (i + 1)..acc.len() {
537 if matches!(
538 outer_bbox_relation(&acc[i], &acc[j]),
539 BBoxRelation::Disjoint
540 ) {
541 continue;
542 }
543 let u = polygon_boolean(&acc[i], &acc[j], BoolOp::Union);
544 let u_area: f64 = u.iter().map(|p| p.area().abs()).sum();
545 let sum_area = acc[i].area().abs() + acc[j].area().abs();
546 if u_area < sum_area - 1e-9 {
547 merged = Some((i, j, u));
548 break 'outer;
549 }
550 }
551 }
552 match merged {
553 Some((i, j, u)) => {
554 let last = acc.len() - 1;
555 acc[j] = acc[last].clone();
556 acc.swap_remove(last);
557 acc.splice(i..i + 1, u);
558 }
559 None => break,
560 }
561 }
562
563 let geometries = acc
564 .into_iter()
565 .map(|p| Geometry {
566 outer: p,
567 holes: Vec::new(),
568 transforms: Vec::new(),
569 })
570 .collect();
571 Self { geometries }
572 }
573
574 pub fn validate(&self) -> Result<(), CompoundError> {
580 for (ri, g) in self.geometries.iter().enumerate() {
582 let g = g.apply_transforms();
583 for (hi, hole) in g.holes.iter().enumerate() {
584 let vertices_inside = hole.vertices.iter().all(|v| g.outer.contains_point(*v));
586 if !vertices_inside {
587 return Err(CompoundError::HoleNotInsideOuter {
588 region: ri,
589 hole: hi,
590 });
591 }
592 for i in 0..hole.vertices.len() {
594 let h1 = hole.vertices[i];
595 let h2 = hole.vertices[(i + 1) % hole.vertices.len()];
596 for j in 0..g.outer.vertices.len() {
597 let o1 = g.outer.vertices[j];
598 let o2 = g.outer.vertices[(j + 1) % g.outer.vertices.len()];
599 if segments_interact(h1, h2, o1, o2) {
600 return Err(CompoundError::HoleNotInsideOuter {
601 region: ri,
602 hole: hi,
603 });
604 }
605 }
606 }
607 }
608
609 for a in 0..g.holes.len() {
613 for b in (a + 1)..g.holes.len() {
614 let ha = &g.holes[a];
615 let hb = &g.holes[b];
616 let a_contains_b = hb.vertices.iter().all(|v| ha.contains_point(*v));
617 let b_contains_a = ha.vertices.iter().all(|v| hb.contains_point(*v));
618 if a_contains_b || b_contains_a {
619 return Err(CompoundError::NestedHoles { region: ri, a, b });
620 }
621 }
622 }
623 }
624
625 let n = self.geometries.len();
635 if n < 2 {
636 return Ok(());
637 }
638
639 let applied: Vec<Geometry> = self
640 .geometries
641 .iter()
642 .map(|g| g.apply_transforms())
643 .collect();
644
645 for i in 0..n {
646 for j in (i + 1)..n {
647 let gi = &applied[i];
648 let gj = &applied[j];
649 if regions_overlap_deterministic(gi, gj) {
650 return Err(CompoundError::OverlappingRegions { a: i, b: j });
651 }
652 }
653 }
654 Ok(())
655 }
656
657 pub fn from_sections(sections: &[crate::section::Section]) -> Self {
659 Self {
660 geometries: sections.iter().map(Geometry::from_section).collect(),
661 }
662 }
663
664 pub fn boolean(
674 &self,
675 other: &Self,
676 op: super::boolean::BoolOp,
677 ) -> Result<Self, super::boolean::BooleanError> {
678 match op {
679 super::boolean::BoolOp::Intersection => {
680 let mut out = Vec::new();
684 for ga in &self.geometries {
685 for gb in &other.geometries {
686 let inter = ga.boolean_op(gb, op)?;
687 out.extend(inter.geometries);
688 }
689 }
690 Ok(Self { geometries: out })
691 }
692 super::boolean::BoolOp::Difference => {
693 let mut current: Vec<Geometry> = self.geometries.clone();
695
696 for gb in &other.geometries {
698 let mut next = Vec::new();
699 for ga in ¤t {
700 let diff = ga.boolean_op(gb, op)?;
701 next.extend(diff.geometries);
702 }
703 current = next;
704 if current.is_empty() {
705 break;
706 }
707 }
708 let geometries = current
709 .into_iter()
710 .map(|g| Geometry {
711 outer: g.outer,
712 holes: g.holes,
713 transforms: Vec::new(),
714 })
715 .collect();
716 Ok(Self { geometries })
717 }
718 super::boolean::BoolOp::Union => {
719 let mut acc: Vec<Geometry> = self
721 .geometries
722 .iter()
723 .chain(other.geometries.iter())
724 .cloned()
725 .collect();
726
727 loop {
729 let mut merged: Option<(usize, usize, Vec<Geometry>)> = None;
730 'outer: for i in 0..acc.len() {
731 for j in (i + 1)..acc.len() {
732 if matches!(
733 outer_bbox_relation(&acc[i].outer, &acc[j].outer),
734 BBoxRelation::Disjoint
735 ) {
736 continue;
737 }
738 let union_result =
739 acc[i].boolean_op(&acc[j], super::boolean::BoolOp::Union)?;
740 if union_result.geometries.len() == 1 {
745 merged = Some((i, j, union_result.geometries));
746 break 'outer;
747 }
748 }
749 }
750 match merged {
751 Some((i, j, new_geometries)) => {
752 let last = acc.len() - 1;
753 acc[j] = acc[last].clone();
754 acc.swap_remove(last);
755 acc.splice(i..i + 1, new_geometries);
756 }
757 None => break,
758 }
759 }
760
761 let geometries = acc;
762 Ok(Self { geometries })
763 }
764 }
765 }
766
767 pub fn union(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
769 self.boolean(other, super::boolean::BoolOp::Union)
770 }
771
772 pub fn intersection(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
774 self.boolean(other, super::boolean::BoolOp::Intersection)
775 }
776
777 pub fn subtract(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
779 self.boolean(other, super::boolean::BoolOp::Difference)
780 }
781 pub fn area(&self) -> f64 {
783 self.geometries.iter().map(|g| g.area()).sum()
784 }
785
786 pub fn centroid(&self) -> Point {
788 let mut sum_x = 0.0;
789 let mut sum_y = 0.0;
790 let mut total = 0.0;
791 for g in &self.geometries {
792 let a = g.area();
793 let c = g.centroid();
794 sum_x += c.x * a;
795 sum_y += c.y * a;
796 total += a;
797 }
798 assert!(
799 total.abs() > f64::EPSILON,
800 "CompoundGeometry has zero total area"
801 );
802 Point::new(sum_x / total, sum_y / total)
803 }
804
805 pub fn bounds(&self) -> (f64, f64, f64, f64) {
807 let mut min_x = f64::INFINITY;
808 let mut max_x = f64::NEG_INFINITY;
809 let mut min_y = f64::INFINITY;
810 let mut max_y = f64::NEG_INFINITY;
811 for g in &self.geometries {
812 let (l, r, b, t) = g.bounds();
813 min_x = min_x.min(l);
814 max_x = max_x.max(r);
815 min_y = min_y.min(b);
816 max_y = max_y.max(t);
817 }
818 (min_x, max_x, min_y, max_y)
819 }
820
821 pub fn perimeter(&self) -> f64 {
823 self.geometries.iter().map(|g| g.perimeter()).sum()
824 }
825
826 pub fn polygons(&self) -> Vec<Polygon> {
829 let mut out = Vec::new();
830 for g in &self.geometries {
831 let g = g.apply_transforms();
832 out.push(g.outer);
833 out.extend(g.holes);
834 }
835 out
836 }
837}
838
839impl From<crate::section::Section> for CompoundGeometry {
841 fn from(section: crate::section::Section) -> Self {
842 Self::new(vec![Geometry::new(section.outer, section.holes)])
843 }
844}
845
846fn intersection_point(a1: Point, a2: Point, b1: Point, b2: Point) -> Point {
860 let dx1 = a2.x - a1.x;
863 let dy1 = a2.y - a1.y;
864 let dx2 = b2.x - b1.x;
865 let dy2 = b2.y - b1.y;
866
867 let det = dx1 * dy2 - dy1 * dx2;
868 if det.abs() < 1e-12 {
869 let len2 = dx1 * dx1 + dy1 * dy1;
873 if len2 < 1e-24 {
874 return a1;
876 }
877 let t_b1 = ((b1.x - a1.x) * dx1 + (b1.y - a1.y) * dy1) / len2;
879 let t_b2 = ((b2.x - a1.x) * dx1 + (b2.y - a1.y) * dy1) / len2;
880 let b_lo = t_b1.min(t_b2);
882 let b_hi = t_b1.max(t_b2);
883 let lo = 0.0f64.max(b_lo);
885 let hi = 1.0f64.min(b_hi);
886 if lo <= hi {
887 let t_mid = (lo + hi) * 0.5;
889 return Point::new(a1.x + t_mid * dx1, a1.y + t_mid * dy1);
890 }
891 return Point::new((a1.x + a2.x) * 0.5, (a1.y + a2.y) * 0.5);
893 }
894
895 let t = ((b1.x - a1.x) * dy2 - (b1.y - a1.y) * dx2) / det;
896 let t = t.clamp(0.0, 1.0);
898 Point::new(a1.x + t * dx1, a1.y + t * dy1)
899}
900
901fn regions_overlap_deterministic(a: &Geometry, b: &Geometry) -> bool {
902 let a_outer = &a.outer;
903 let b_outer = &b.outer;
904
905 for i in 0..a_outer.vertices.len() {
909 let a1 = a_outer.vertices[i];
910 let a2 = a_outer.vertices[(i + 1) % a_outer.vertices.len()];
911 for j in 0..b_outer.vertices.len() {
912 let b1 = b_outer.vertices[j];
913 let b2 = b_outer.vertices[(j + 1) % b_outer.vertices.len()];
914 if segments_overlap(a1, a2, b1, b2) {
915 let pt = intersection_point(a1, a2, b1, b2);
919 let in_a_material =
921 a_outer.contains_point(pt) && !a.holes.iter().any(|h| h.contains_point(pt));
922 let in_b_material =
923 b_outer.contains_point(pt) && !b.holes.iter().any(|h| h.contains_point(pt));
924 if in_a_material && in_b_material {
925 return true;
926 }
927 }
928 }
929 }
930
931 for v in &a_outer.vertices {
933 if b_outer.contains_point(*v) && !b.holes.iter().any(|h| h.contains_point(*v)) {
934 return true;
935 }
936 }
937 for v in &b_outer.vertices {
939 if a_outer.contains_point(*v) && !a.holes.iter().any(|h| h.contains_point(*v)) {
940 return true;
941 }
942 }
943
944 let a_in_b = a_outer.vertices.iter().all(|v| b_outer.contains_point(*v));
949 let b_in_a = b_outer.vertices.iter().all(|v| a_outer.contains_point(*v));
950
951 if a_in_b || b_in_a {
952 let inter =
954 super::boolean::polygon_boolean(a_outer, b_outer, super::boolean::BoolOp::Intersection);
955 if inter.is_empty() {
956 return false;
957 }
958 let mut remaining = inter;
961 for hole in a.holes.iter().chain(b.holes.iter()) {
962 let mut next = Vec::new();
963 for p in &remaining {
964 let diff =
965 super::boolean::polygon_boolean(p, hole, super::boolean::BoolOp::Difference);
966 next.extend(diff);
967 }
968 remaining = next;
969 if remaining.is_empty() {
970 break;
971 }
972 }
973 return !remaining.is_empty();
974 }
975
976 false
977}
978
979#[derive(Debug, Clone, Copy, PartialEq)]
981enum SegmentRelation {
982 Disjoint,
984 Touch,
986 ProperCross,
988 CollinearOverlap,
990}
991
992fn segment_relation(a1: Point, a2: Point, b1: Point, b2: Point) -> SegmentRelation {
995 const EPS: f64 = 1e-12;
996
997 fn orient(p: Point, q: Point, r: Point) -> f64 {
998 (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)
999 }
1000
1001 fn on_segment(p: Point, q: Point, r: Point) -> bool {
1002 q.x >= p.x.min(r.x) - EPS
1004 && q.x <= p.x.max(r.x) + EPS
1005 && q.y >= p.y.min(r.y) - EPS
1006 && q.y <= p.y.max(r.y) + EPS
1007 }
1008
1009 fn points_equal(p: Point, q: Point) -> bool {
1010 (p.x - q.x).abs() <= EPS && (p.y - q.y).abs() <= EPS
1011 }
1012
1013 let o1 = orient(a1, a2, b1);
1014 let o2 = orient(a1, a2, b2);
1015 let o3 = orient(b1, b2, a1);
1016 let o4 = orient(b1, b2, a2);
1017
1018 let o1_pos = o1 > EPS;
1020 let o1_neg = o1 < -EPS;
1021 let o2_pos = o2 > EPS;
1022 let o2_neg = o2 < -EPS;
1023 let o3_pos = o3 > EPS;
1024 let o3_neg = o3 < -EPS;
1025 let o4_pos = o4 > EPS;
1026 let o4_neg = o4 < -EPS;
1027
1028 if (o1_pos != o2_pos || o1_neg != o2_neg) && (o3_pos != o4_pos || o3_neg != o4_neg) {
1029 return SegmentRelation::ProperCross;
1030 }
1031
1032 if o1.abs() <= EPS && o2.abs() <= EPS && o3.abs() <= EPS && o4.abs() <= EPS {
1035 let a_min_x = a1.x.min(a2.x);
1037 let a_max_x = a1.x.max(a2.x);
1038 let b_min_x = b1.x.min(b2.x);
1039 let b_max_x = b1.x.max(b2.x);
1040 let a_min_y = a1.y.min(a2.y);
1041 let a_max_y = a1.y.max(a2.y);
1042 let b_min_y = b1.y.min(b2.y);
1043 let b_max_y = b1.y.max(b2.y);
1044
1045 let overlap_x = a_max_x >= b_min_x - EPS && b_max_x >= a_min_x - EPS;
1046 let overlap_y = a_max_y >= b_min_y - EPS && b_max_y >= a_min_y - EPS;
1047
1048 if overlap_x && overlap_y {
1049 let len_a2 = (a2.x - a1.x).powi(2) + (a2.y - a1.y).powi(2);
1055 let _len_b2 = (b2.x - b1.x).powi(2) + (b2.y - b1.y).powi(2);
1056
1057 let t_b1 = if len_a2 > EPS {
1059 ((b1.x - a1.x) * (a2.x - a1.x) + (b1.y - a1.y) * (a2.y - a1.y)) / len_a2
1060 } else {
1061 0.0
1062 };
1063 let t_b2 = if len_a2 > EPS {
1064 ((b2.x - a1.x) * (a2.x - a1.x) + (b2.y - a1.y) * (a2.y - a1.y)) / len_a2
1065 } else {
1066 0.0
1067 };
1068
1069 let b_lo = t_b1.min(t_b2);
1070 let b_hi = t_b1.max(t_b2);
1071
1072 let lo = 0.0f64.max(b_lo);
1074 let hi = 1.0f64.min(b_hi);
1075
1076 if lo <= hi {
1077 let overlap_len = (hi - lo) * len_a2.sqrt();
1078 if overlap_len > EPS {
1079 return SegmentRelation::CollinearOverlap;
1080 } else {
1081 return SegmentRelation::Touch;
1083 }
1084 }
1085 }
1086 return SegmentRelation::Disjoint;
1087 }
1088
1089 if o1.abs() <= EPS && on_segment(a1, b1, a2) {
1092 return if points_equal(b1, a1) || points_equal(b1, a2) {
1093 SegmentRelation::Touch
1094 } else {
1095 SegmentRelation::Disjoint
1096 };
1097 }
1098 if o2.abs() <= EPS && on_segment(a1, b2, a2) {
1100 return if points_equal(b2, a1) || points_equal(b2, a2) {
1101 SegmentRelation::Touch
1102 } else {
1103 SegmentRelation::Disjoint
1104 };
1105 }
1106 if o3.abs() <= EPS && on_segment(b1, a1, b2) {
1108 return if points_equal(a1, b1) || points_equal(a1, b2) {
1109 SegmentRelation::Touch
1110 } else {
1111 SegmentRelation::Disjoint
1112 };
1113 }
1114 if o4.abs() <= EPS && on_segment(b1, a2, b2) {
1116 return if points_equal(a2, b1) || points_equal(a2, b2) {
1117 SegmentRelation::Touch
1118 } else {
1119 SegmentRelation::Disjoint
1120 };
1121 }
1122
1123 SegmentRelation::Disjoint
1124}
1125
1126pub fn segments_interact(a1: Point, a2: Point, b1: Point, b2: Point) -> bool {
1129 !matches!(segment_relation(a1, a2, b1, b2), SegmentRelation::Disjoint)
1130}
1131
1132pub fn segments_overlap(a1: Point, a2: Point, b1: Point, b2: Point) -> bool {
1136 matches!(
1137 segment_relation(a1, a2, b1, b2),
1138 SegmentRelation::ProperCross | SegmentRelation::CollinearOverlap
1139 )
1140}
1141
1142#[cfg(test)]
1143mod tests {
1144 use super::{Point, SegmentRelation, segment_relation, segments_interact, segments_overlap};
1145
1146 #[test]
1147 fn segment_relation_proper_cross() {
1148 let a1 = Point::new(0.0, 0.0);
1150 let a2 = Point::new(10.0, 10.0);
1151 let b1 = Point::new(0.0, 10.0);
1152 let b2 = Point::new(10.0, 0.0);
1153 assert_eq!(
1154 segment_relation(a1, a2, b1, b2),
1155 SegmentRelation::ProperCross
1156 );
1157 assert!(segments_overlap(a1, a2, b1, b2));
1158 assert!(segments_interact(a1, a2, b1, b2));
1159 }
1160
1161 #[test]
1162 fn segment_relation_touch_endpoint() {
1163 let a1 = Point::new(0.0, 0.0);
1165 let a2 = Point::new(5.0, 0.0);
1166 let b1 = Point::new(5.0, 0.0);
1167 let b2 = Point::new(10.0, 0.0);
1168 assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Touch);
1169 assert!(!segments_overlap(a1, a2, b1, b2));
1170 assert!(segments_interact(a1, a2, b1, b2));
1171 }
1172
1173 #[test]
1174 fn segment_relation_collinear_overlap() {
1175 let a1 = Point::new(0.0, 0.0);
1177 let a2 = Point::new(10.0, 0.0);
1178 let b1 = Point::new(5.0, 0.0);
1179 let b2 = Point::new(15.0, 0.0);
1180 assert_eq!(
1181 segment_relation(a1, a2, b1, b2),
1182 SegmentRelation::CollinearOverlap
1183 );
1184 assert!(segments_overlap(a1, a2, b1, b2));
1185 assert!(segments_interact(a1, a2, b1, b2));
1186 }
1187
1188 #[test]
1189 fn segment_relation_collinear_touch() {
1190 let a1 = Point::new(0.0, 0.0);
1192 let a2 = Point::new(5.0, 0.0);
1193 let b1 = Point::new(5.0, 0.0);
1194 let b2 = Point::new(10.0, 0.0);
1195 assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Touch);
1197 assert!(!segments_overlap(a1, a2, b1, b2));
1198 assert!(segments_interact(a1, a2, b1, b2));
1199 }
1200
1201 #[test]
1202 fn segment_relation_disjoint() {
1203 let a1 = Point::new(0.0, 0.0);
1205 let a2 = Point::new(5.0, 0.0);
1206 let b1 = Point::new(6.0, 0.0);
1207 let b2 = Point::new(10.0, 0.0);
1208 assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Disjoint);
1209 assert!(!segments_overlap(a1, a2, b1, b2));
1210 assert!(!segments_interact(a1, a2, b1, b2));
1211 }
1212
1213 #[test]
1214 fn segment_relation_cross_near_endpoint() {
1215 let a1 = Point::new(0.0, 0.0);
1217 let a2 = Point::new(10.0, 10.0);
1218 let b1 = Point::new(0.0, 10.0);
1219 let b2 = Point::new(10.0, 0.0);
1220 assert_eq!(
1221 segment_relation(a1, a2, b1, b2),
1222 SegmentRelation::ProperCross
1223 );
1224 assert!(segments_overlap(a1, a2, b1, b2));
1225 }
1226}