use crate::point::Point;
pub use crate::edge::{Edge, EdgeIntersection, LineIntersection};
use crate::CoordinateType;
use num_traits::{PrimInt, Zero};
use crate::traits::BoundingBox;
use std::fmt::Debug;
impl<T: CoordinateType + PrimInt + Debug> Edge<T> {
pub fn line_intersection_rounded(&self, other: Edge<T>) -> LineIntersection<T, T> {
if self.is_degenerate() {
LineIntersection::None
} else if other.is_degenerate() {
LineIntersection::None
} else {
let ab = self.vector();
let cd = other.vector();
debug_assert!(!ab.is_zero());
debug_assert!(!cd.is_zero());
let s = ab.cross_prod(cd);
if s.is_zero() {
debug_assert!(self.is_parallel(&other));
if self.line_contains_point(other.start) {
debug_assert!(self.is_collinear(&other));
LineIntersection::Collinear
} else {
LineIntersection::None
}
} else {
let ac = other.start - self.start;
let ac_cross_cd = ac.cross_prod(cd);
let exact_scaled_s = self.start * s + ab * ac_cross_cd;
let p: Point<T> = exact_scaled_s / s;
let ca_cross_ab = ac.cross_prod(ab);
debug_assert!({
let exact_scaled_s = other.start * s + cd * ca_cross_ab;
let p2: Point<T> = exact_scaled_s / s;
p == p2
}
);
let positions = if s < T::zero() {
(T::zero() - ac_cross_cd, T::zero() - ca_cross_ab, T::zero() - s)
} else {
(ac_cross_cd, ca_cross_ab, s)
};
LineIntersection::Point(p, positions)
}
}
}
pub fn edge_intersection_rounded(&self, other: &Edge<T>) -> EdgeIntersection<T, T> {
let other = if (self.start < self.end) != (other.start < other.end) {
other.reversed()
} else {
*other
};
debug_assert_eq!(self.start < self.end, other.start < other.end,
"Edges should have the same orientation now.");
let same_start_start = self.start == other.start;
let same_start_end = self.start == other.end;
let same_end_start = self.end == other.start;
let same_end_end = self.end == other.end;
let fully_coincident = (same_start_start & same_end_end) ^ (same_start_end & same_end_start);
let result = if self.is_degenerate() {
if other.contains_point(self.start).inclusive_bounds() {
EdgeIntersection::EndPoint(self.start)
} else {
EdgeIntersection::None
}
} else if other.is_degenerate() {
if self.contains_point(other.start).inclusive_bounds() {
EdgeIntersection::EndPoint(other.start)
} else {
EdgeIntersection::None
}
} else if fully_coincident {
EdgeIntersection::Overlap(*self)
} else if !self.bounding_box().touches(&other.bounding_box()) {
EdgeIntersection::None
} else {
let line_intersection = self.line_intersection_rounded(other);
match line_intersection {
LineIntersection::None => EdgeIntersection::None,
LineIntersection::Point(p, (pos1, pos2, len)) => {
if pos1 >= T::zero() && pos1 <= len
&& pos2 >= T::zero() && pos2 <= len {
if pos1 == T::zero()
|| pos1 == len
|| pos2 == T::zero()
|| pos2 == len {
EdgeIntersection::EndPoint(p)
} else {
EdgeIntersection::Point(p)
}
} else {
EdgeIntersection::None
}
}
LineIntersection::Collinear => {
debug_assert!(self.is_collinear(&other));
let (pa, pb) = self.into();
let (pc, pd) = other.into();
let b = pb - pa;
let c = pc - pa;
let d = pd - pa;
let dist_a = T::zero();
let dist_b = b.dot(b);
let dist_c = b.dot(c);
let dist_d = b.dot(d);
let start1 = (dist_a, pa);
let end1 = (dist_b, pb);
let (start2, end2) = if dist_c < dist_d {
((dist_c, pc), (dist_d, pd))
} else {
((dist_d, pd), (dist_c, pc))
};
let start = if start1.0 < start2.0 {
start2
} else {
start1
};
let end = if end1.0 < end2.0 {
end1
} else {
end2
};
if start.0 < end.0 {
EdgeIntersection::Overlap(Edge::new(start.1, end.1))
} else if start.0 == end.0 {
EdgeIntersection::EndPoint(start.1)
} else {
EdgeIntersection::None
}
}
}
};
debug_assert_eq!(
result == EdgeIntersection::None,
self.edges_intersect(&other).is_no()
);
result
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_line_intersection_rounded() {
let e1 = Edge::new((0, 0), (2, 2));
let e2 = Edge::new((0, 2), (2, 0));
let intersection = e1.line_intersection_rounded(e2);
assert_eq!(intersection, LineIntersection::Point((1, 1).into(), (4, 4, 8)));
let e1 = Edge::new((0, 1), (1, 1));
let e2 = Edge::new((0, 0), (1, 2));
let intersection = e1.line_intersection_rounded(e2);
match intersection {
LineIntersection::Point(p, _) => assert_eq!(p, Point::new(0, 1)),
_ => assert!(false)
}
let e1 = Edge::new((0, 1), (1, 1));
let e2 = Edge::new((0, 0), (1, 3));
let intersection = e1.line_intersection_rounded(e2);
match intersection {
LineIntersection::Point(p, _) => assert_eq!(p, Point::new(0, 1)),
_ => assert!(false)
}
let e1 = Edge::new((0i32, 0), (1, 0));
let e2 = Edge::new((0, 1), (12345677, -1));
let intersection = e1.line_intersection_rounded(e2);
match intersection {
LineIntersection::Point(p, _) => assert_eq!(p, Point::new(12345677 / 2, 0)),
_ => assert!(false)
}
let e1 = Edge::new((0i32, 0), (-1, 0));
let e2 = Edge::new((0, -1), (-12345677, 1));
let intersection = e1.line_intersection_rounded(e2);
match intersection {
LineIntersection::Point(p, _) => assert_eq!(p, Point::new(-12345677 / 2, 0)),
_ => assert!(false)
}
}
#[test]
fn test_edge_intersection_rounded() {
let e1 = Edge::new((-10, 0), (10, 0));
let e2 = Edge::new((-1, -1), (2, 2));
assert_eq!(e1.edge_intersection_rounded(&e2), EdgeIntersection::Point((0, 0).into()));
assert_eq!(e2.edge_intersection_rounded(&e1), EdgeIntersection::Point((0, 0).into()));
let e1 = Edge::new((-10, 0), (10, 0));
let e2 = Edge::new((0, 0), (2, 2));
assert_eq!(e1.edge_intersection_rounded(&e2), EdgeIntersection::EndPoint((0, 0).into()));
assert_eq!(e2.edge_intersection_rounded(&e1), EdgeIntersection::EndPoint((0, 0).into()));
let e1 = Edge::new((0, 0), (10, 0));
let e2 = Edge::new((0, 0), (2, 2));
assert_eq!(e1.edge_intersection_rounded(&e2), EdgeIntersection::EndPoint((0, 0).into()));
assert_eq!(e2.edge_intersection_rounded(&e1), EdgeIntersection::EndPoint((0, 0).into()));
let e1 = Edge::new((0, 0), (1, 0));
let e2 = Edge::new((0, -1), (1, 10));
assert_eq!(e1.edge_intersection_rounded(&e2), EdgeIntersection::Point((0, 0).into()));
assert_eq!(e2.edge_intersection_rounded(&e1), EdgeIntersection::Point((0, 0).into()));
let e1 = Edge::new((-10, 0), (10, 0));
let e2 = Edge::new((1, 1), (2, 2));
assert_eq!(e1.edge_intersection_rounded(&e2), EdgeIntersection::None);
assert_eq!(e2.edge_intersection_rounded(&e1), EdgeIntersection::None);
}
#[test]
fn test_end_point_intersection_at_negative_x() {
let p = |a: isize, b: isize| Point::new(a, b);
let e1 = Edge::new(p(-1, 2), p(0, 0));
let e2 = Edge::new(p(-1, 2), p(0, 2));
assert_eq!(e1.edge_intersection_rounded(&e2),
EdgeIntersection::EndPoint(p(-1, 2)));
}
}