use lievisual::geometry::{Point, Rect};
pub fn segment_intersects_rect(a: Point, b: Point, rect: &Rect) -> bool {
if rect.contains(a) || rect.contains(b) {
return true;
}
let corners = [
Point::new(rect.min_x(), rect.min_y()),
Point::new(rect.max_x(), rect.min_y()),
Point::new(rect.max_x(), rect.max_y()),
Point::new(rect.min_x(), rect.max_y()),
];
for i in 0..4 {
let c0 = corners[i];
let c1 = corners[(i + 1) % 4];
if segment_intersects_segment(a, b, c0, c1) {
return true;
}
}
false
}
const EPS: f64 = 1e-9;
pub fn segment_intersects_segment(a0: Point, a1: Point, b0: Point, b1: Point) -> bool {
let d1 = cross(a0, a1, b0);
let d2 = cross(a0, a1, b1);
let d3 = cross(b0, b1, a0);
let d4 = cross(b0, b1, a1);
if ((d1 > 0.0 && d2 < 0.0) || (d1 < 0.0 && d2 > 0.0))
&& ((d3 > 0.0 && d4 < 0.0) || (d3 < 0.0 && d4 > 0.0))
{
return true;
}
(d1.abs() < EPS && point_on_segment(a0, a1, b0))
|| (d2.abs() < EPS && point_on_segment(a0, a1, b1))
|| (d3.abs() < EPS && point_on_segment(b0, b1, a0))
|| (d4.abs() < EPS && point_on_segment(b0, b1, a1))
}
fn point_on_segment(a: Point, b: Point, p: Point) -> bool {
p.x >= a.x.min(b.x) - EPS
&& p.x <= a.x.max(b.x) + EPS
&& p.y >= a.y.min(b.y) - EPS
&& p.y <= a.y.max(b.y) + EPS
}
#[inline]
fn cross(a: Point, b: Point, c: Point) -> f64 {
(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn segment_hits_rect_when_crossing() {
let rect = Rect::new(0.0, 0.0, 10.0, 10.0);
assert!(segment_intersects_rect(
Point::new(-5.0, 5.0),
Point::new(15.0, 5.0),
&rect
));
assert!(segment_intersects_rect(
Point::new(5.0, -5.0),
Point::new(5.0, 15.0),
&rect
));
assert!(!segment_intersects_rect(
Point::new(-5.0, -5.0),
Point::new(-1.0, -1.0),
&rect
));
}
#[test]
fn segments_intersect_basic() {
let a0 = Point::new(0.0, 0.0);
let a1 = Point::new(10.0, 10.0);
let b0 = Point::new(0.0, 10.0);
let b1 = Point::new(10.0, 0.0);
assert!(segment_intersects_segment(a0, a1, b0, b1));
let c0 = Point::new(20.0, 20.0);
let c1 = Point::new(20.0, 30.0);
assert!(!segment_intersects_segment(a0, a1, c0, c1));
}
#[test]
fn collinear_segments_only_intersect_when_overlapping() {
let a0 = Point::new(0.0, 0.0);
let a1 = Point::new(10.0, 0.0);
let b0 = Point::new(20.0, 0.0);
let b1 = Point::new(30.0, 0.0);
assert!(!segment_intersects_segment(a0, a1, b0, b1));
let c0 = Point::new(5.0, 0.0);
let c1 = Point::new(15.0, 0.0);
assert!(segment_intersects_segment(a0, a1, c0, c1));
let d0 = Point::new(10.0, 0.0);
let d1 = Point::new(10.0, 10.0);
assert!(segment_intersects_segment(a0, a1, d0, d1));
}
}