use crate::predicates::{Orientation, line_intersection, orient2d};
use crate::primitives::{Aabb2, Point2, PointSegmentRelation, Segment2, point_in_collinear_range};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SegmentIntersectionKind {
None,
Proper,
EndpointTouch,
CollinearTouch,
CollinearOverlap,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum SegmentIntersection2 {
None,
Point(Point2),
Overlap(Segment2),
}
enum Classification {
None,
Proper,
EndpointTouch(Point2),
CollinearTouch(Point2),
CollinearOverlap(Point2, Point2),
}
fn opposite_signs(x: Orientation, y: Orientation) -> bool {
matches!(
(x, y),
(Orientation::Clockwise, Orientation::CounterClockwise)
| (Orientation::CounterClockwise, Orientation::Clockwise)
)
}
fn classify(s1: Segment2, s2: Segment2) -> Classification {
if !Aabb2::from_segment(s1).overlaps(&Aabb2::from_segment(s2)) {
return Classification::None;
}
let (a, b) = (s1.a(), s1.b());
let (c, d) = (s2.a(), s2.b());
if s1.is_zero_length() && s2.is_zero_length() {
return if a == c {
Classification::EndpointTouch(a)
} else {
Classification::None
};
}
if s1.is_zero_length() {
return match s2.relation_to(a) {
PointSegmentRelation::NotOnSegment => Classification::None,
_ => Classification::EndpointTouch(a),
};
}
if s2.is_zero_length() {
return match s1.relation_to(c) {
PointSegmentRelation::NotOnSegment => Classification::None,
_ => Classification::EndpointTouch(c),
};
}
let d1 = orient2d(c, d, a);
let d2 = orient2d(c, d, b);
if d1 == Orientation::Collinear && d2 == Orientation::Collinear {
return collinear_overlap(s1, s2);
}
let d3 = orient2d(a, b, c);
let d4 = orient2d(a, b, d);
if opposite_signs(d1, d2) && opposite_signs(d3, d4) {
return Classification::Proper;
}
if d1 == Orientation::Collinear && point_in_collinear_range(c, d, a) {
return Classification::EndpointTouch(a);
}
if d2 == Orientation::Collinear && point_in_collinear_range(c, d, b) {
return Classification::EndpointTouch(b);
}
if d3 == Orientation::Collinear && point_in_collinear_range(a, b, c) {
return Classification::EndpointTouch(c);
}
if d4 == Orientation::Collinear && point_in_collinear_range(a, b, d) {
return Classification::EndpointTouch(d);
}
Classification::None
}
fn collinear_overlap(s1: Segment2, s2: Segment2) -> Classification {
let (a, b) = (s1.a(), s1.b());
let (c, d) = (s2.a(), s2.b());
let use_x = a.x() != b.x();
let axis = |p: Point2| if use_x { p.x() } else { p.y() };
let sorted = |p: Point2, q: Point2| if axis(p) <= axis(q) { (p, q) } else { (q, p) };
let (lo1, hi1) = sorted(a, b);
let (lo2, hi2) = sorted(c, d);
let lo = if axis(lo1) >= axis(lo2) { lo1 } else { lo2 };
let hi = if axis(hi1) <= axis(hi2) { hi1 } else { hi2 };
if axis(lo) > axis(hi) {
Classification::None
} else if axis(lo) == axis(hi) {
Classification::CollinearTouch(lo)
} else {
Classification::CollinearOverlap(lo, hi)
}
}
pub fn segment_intersection_kind(s1: Segment2, s2: Segment2) -> SegmentIntersectionKind {
match classify(s1, s2) {
Classification::None => SegmentIntersectionKind::None,
Classification::Proper => SegmentIntersectionKind::Proper,
Classification::EndpointTouch(_) => SegmentIntersectionKind::EndpointTouch,
Classification::CollinearTouch(_) => SegmentIntersectionKind::CollinearTouch,
Classification::CollinearOverlap(_, _) => SegmentIntersectionKind::CollinearOverlap,
}
}
pub fn segment_intersection(s1: Segment2, s2: Segment2) -> SegmentIntersection2 {
match classify(s1, s2) {
Classification::None => SegmentIntersection2::None,
Classification::Proper => SegmentIntersection2::Point(proper_intersection_point(s1, s2)),
Classification::EndpointTouch(p) | Classification::CollinearTouch(p) => {
SegmentIntersection2::Point(p)
}
Classification::CollinearOverlap(p, q) => {
SegmentIntersection2::Overlap(Segment2::new(p, q))
}
}
}
fn proper_intersection_point(s1: Segment2, s2: Segment2) -> Point2 {
line_intersection(s1.a(), s1.b(), s2.a(), s2.b())
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
fn s(ax: f64, ay: f64, bx: f64, by: f64) -> Segment2 {
Segment2::new(p(ax, ay), p(bx, by))
}
#[test]
fn proper_crossing() {
let s1 = s(0.0, 0.0, 4.0, 4.0);
let s2 = s(0.0, 4.0, 4.0, 0.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::Proper
);
assert_eq!(
segment_intersection(s1, s2),
SegmentIntersection2::Point(p(2.0, 2.0))
);
}
#[test]
fn disjoint_rejected_by_aabb() {
let s1 = s(0.0, 0.0, 1.0, 0.0);
let s2 = s(5.0, 5.0, 6.0, 6.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::None
);
assert_eq!(segment_intersection(s1, s2), SegmentIntersection2::None);
}
#[test]
fn shared_endpoint() {
let s1 = s(0.0, 0.0, 1.0, 1.0);
let s2 = s(0.0, 0.0, 1.0, -1.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::EndpointTouch
);
assert_eq!(
segment_intersection(s1, s2),
SegmentIntersection2::Point(p(0.0, 0.0))
);
}
#[test]
fn t_junction_touches_interior() {
let s1 = s(0.0, 0.0, 4.0, 0.0);
let s2 = s(2.0, 0.0, 2.0, 3.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::EndpointTouch
);
assert_eq!(
segment_intersection(s1, s2),
SegmentIntersection2::Point(p(2.0, 0.0))
);
}
#[test]
fn collinear_touch_end_to_end() {
let s1 = s(0.0, 0.0, 2.0, 0.0);
let s2 = s(2.0, 0.0, 4.0, 0.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::CollinearTouch
);
assert_eq!(
segment_intersection(s1, s2),
SegmentIntersection2::Point(p(2.0, 0.0))
);
}
#[test]
fn collinear_overlap() {
let s1 = s(0.0, 0.0, 4.0, 0.0);
let s2 = s(2.0, 0.0, 6.0, 0.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::CollinearOverlap
);
assert_eq!(
segment_intersection(s1, s2),
SegmentIntersection2::Overlap(s(2.0, 0.0, 4.0, 0.0))
);
}
#[test]
fn collinear_no_overlap() {
let s1 = s(0.0, 0.0, 1.0, 0.0);
let s2 = s(2.0, 0.0, 3.0, 0.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::None
);
}
#[test]
fn parallel_non_collinear_never_intersects() {
let s1 = s(0.0, 0.0, 4.0, 0.0);
let s2 = s(0.0, 1.0, 4.0, 1.0);
assert_eq!(
segment_intersection_kind(s1, s2),
SegmentIntersectionKind::None
);
}
#[test]
fn zero_length_segments() {
let point_seg = s(2.0, 2.0, 2.0, 2.0);
let same_point = s(2.0, 2.0, 2.0, 2.0);
let different_point = s(9.0, 9.0, 9.0, 9.0);
let through = s(0.0, 0.0, 4.0, 4.0);
let elsewhere = s(0.0, 0.0, 1.0, 0.0);
assert_eq!(
segment_intersection_kind(point_seg, same_point),
SegmentIntersectionKind::EndpointTouch
);
assert_eq!(
segment_intersection_kind(point_seg, different_point),
SegmentIntersectionKind::None
);
assert_eq!(
segment_intersection_kind(point_seg, through),
SegmentIntersectionKind::EndpointTouch
);
assert_eq!(
segment_intersection_kind(point_seg, elsewhere),
SegmentIntersectionKind::None
);
}
#[test]
fn symmetry() {
let cases = [
(s(0.0, 0.0, 4.0, 4.0), s(0.0, 4.0, 4.0, 0.0)),
(s(0.0, 0.0, 1.0, 1.0), s(0.0, 0.0, 1.0, -1.0)),
(s(0.0, 0.0, 4.0, 0.0), s(2.0, 0.0, 2.0, 3.0)),
(s(0.0, 0.0, 2.0, 0.0), s(2.0, 0.0, 4.0, 0.0)),
(s(0.0, 0.0, 4.0, 0.0), s(2.0, 0.0, 6.0, 0.0)),
];
for (s1, s2) in cases {
assert_eq!(
segment_intersection_kind(s1, s2),
segment_intersection_kind(s2, s1),
"asymmetric for {s1:?}, {s2:?}"
);
}
}
}