use crate::algorithm::contains::Contains;
use crate::{Line, LineString, Point, Polygon, Rect};
use num_traits::Float;
pub trait Intersects<Rhs = Self> {
fn intersects(&self, rhs: &Rhs) -> bool;
}
impl<T> Intersects<Point<T>> for Line<T>
where
T: Float,
{
fn intersects(&self, p: &Point<T>) -> bool {
let tx = if self.dx() == T::zero() {
None
} else {
Some((p.x() - self.start.x) / self.dx())
};
let ty = if self.dy() == T::zero() {
None
} else {
Some((p.y() - self.start.y) / self.dy())
};
match (tx, ty) {
(None, None) => {
p.0 == self.start
}
(Some(t), None) => {
p.y() == self.start.y && T::zero() <= t && t <= T::one()
}
(None, Some(t)) => {
p.x() == self.start.x && T::zero() <= t && t <= T::one()
}
(Some(t_x), Some(t_y)) => {
(t_x - t_y).abs() <= T::epsilon() && T::zero() <= t_x && t_x <= T::one()
}
}
}
}
impl<T> Intersects<Line<T>> for Point<T>
where
T: Float,
{
fn intersects(&self, line: &Line<T>) -> bool {
line.intersects(self)
}
}
impl<T> Intersects<Line<T>> for Line<T>
where
T: Float,
{
fn intersects(&self, line: &Line<T>) -> bool {
let a1 = self.dx();
let a2 = self.dy();
let b1 = -line.dx();
let b2 = -line.dy();
let c1 = line.start.x - self.start.x;
let c2 = line.start.y - self.start.y;
let d = a1 * b2 - a2 * b1;
if d == T::zero() {
let (self_start, self_end) = self.points();
let (other_start, other_end) = line.points();
self_start.intersects(line)
|| self_end.intersects(line)
|| other_start.intersects(self)
|| other_end.intersects(self)
} else {
let s = (c1 * b2 - c2 * b1) / d;
let t = (a1 * c2 - a2 * c1) / d;
(T::zero() <= s) && (s <= T::one()) && (T::zero() <= t) && (t <= T::one())
}
}
}
impl<T> Intersects<LineString<T>> for Line<T>
where
T: Float,
{
fn intersects(&self, linestring: &LineString<T>) -> bool {
linestring.lines().any(|line| self.intersects(&line))
}
}
impl<T> Intersects<Line<T>> for LineString<T>
where
T: Float,
{
fn intersects(&self, line: &Line<T>) -> bool {
line.intersects(self)
}
}
impl<T> Intersects<Polygon<T>> for Line<T>
where
T: Float,
{
fn intersects(&self, p: &Polygon<T>) -> bool {
p.exterior().intersects(self)
|| p.interiors().iter().any(|inner| inner.intersects(self))
|| p.contains(&self.start_point())
|| p.contains(&self.end_point())
}
}
impl<T> Intersects<Line<T>> for Polygon<T>
where
T: Float,
{
fn intersects(&self, line: &Line<T>) -> bool {
line.intersects(self)
}
}
impl<T> Intersects<LineString<T>> for LineString<T>
where
T: Float,
{
fn intersects(&self, linestring: &LineString<T>) -> bool {
if self.0.is_empty() || linestring.0.is_empty() {
return false;
}
for a in self.lines() {
for b in linestring.lines() {
let u_b = b.dy() * a.dx() - b.dx() * a.dy();
if u_b == T::zero() {
continue;
}
let ua_t = b.dx() * (a.start.y - b.start.y) - b.dy() * (a.start.x - b.start.x);
let ub_t = a.dx() * (a.start.y - b.start.y) - a.dy() * (a.start.x - b.start.x);
let u_a = ua_t / u_b;
let u_b = ub_t / u_b;
if (T::zero() <= u_a)
&& (u_a <= T::one())
&& (T::zero() <= u_b)
&& (u_b <= T::one())
{
return true;
}
}
}
false
}
}
impl<T> Intersects<LineString<T>> for Polygon<T>
where
T: Float,
{
fn intersects(&self, linestring: &LineString<T>) -> bool {
if self.exterior().intersects(linestring)
|| self
.interiors()
.iter()
.any(|inner| inner.intersects(linestring))
{
true
} else {
linestring.points_iter().any(|point| self.contains(&point))
}
}
}
impl<T> Intersects<Polygon<T>> for LineString<T>
where
T: Float,
{
fn intersects(&self, polygon: &Polygon<T>) -> bool {
polygon.intersects(self)
}
}
impl<T> Intersects<Rect<T>> for Rect<T>
where
T: Float,
{
fn intersects(&self, bounding_rect: &Rect<T>) -> bool {
if bounding_rect.contains(self) {
false
} else {
(self.min.x >= bounding_rect.min.x && self.min.x <= bounding_rect.max.x
|| self.max.x >= bounding_rect.min.x && self.max.x <= bounding_rect.max.x)
&& (self.min.y >= bounding_rect.min.y && self.min.y <= bounding_rect.max.y
|| self.max.y >= bounding_rect.min.y && self.max.y <= bounding_rect.max.y)
}
}
}
impl<T> Intersects<Polygon<T>> for Rect<T>
where
T: Float,
{
fn intersects(&self, polygon: &Polygon<T>) -> bool {
polygon.intersects(self)
}
}
impl<T> Intersects<Rect<T>> for Polygon<T>
where
T: Float,
{
fn intersects(&self, bounding_rect: &Rect<T>) -> bool {
let p = Polygon::new(
LineString::from(vec![
(bounding_rect.min.x, bounding_rect.min.y),
(bounding_rect.min.x, bounding_rect.max.y),
(bounding_rect.max.x, bounding_rect.max.y),
(bounding_rect.max.x, bounding_rect.min.y),
(bounding_rect.min.x, bounding_rect.min.y),
]),
vec![],
);
self.intersects(&p)
}
}
impl<T> Intersects<Polygon<T>> for Polygon<T>
where
T: Float,
{
fn intersects(&self, polygon: &Polygon<T>) -> bool {
self.intersects(polygon.exterior()) ||
polygon.interiors().iter().any(|inner_line_string| self.intersects(inner_line_string)) ||
polygon.intersects(self.exterior())
}
}
#[cfg(test)]
mod test {
use crate::algorithm::intersects::Intersects;
use crate::{Coordinate, Line, LineString, Point, Polygon, Rect};
#[test]
fn empty_linestring1_test() {
let linestring = LineString::from(vec![(3., 2.), (7., 6.)]);
assert!(!LineString(Vec::new()).intersects(&linestring));
}
#[test]
fn empty_linestring2_test() {
let linestring = LineString::from(vec![(3., 2.), (7., 6.)]);
assert!(!linestring.intersects(&LineString(Vec::new())));
}
#[test]
fn empty_all_linestring_test() {
assert!(!LineString::<f64>(Vec::new()).intersects(&LineString(Vec::new())));
}
#[test]
fn intersect_linestring_test() {
let linestring = LineString::from(vec![(3., 2.), (7., 6.)]);
assert!(linestring.intersects(&LineString::from(vec![(3., 4.), (8., 4.)])));
}
#[test]
fn parallel_linestrings_test() {
let linestring = LineString::from(vec![(3., 2.), (7., 6.)]);
assert!(!linestring.intersects(&LineString::from(vec![(3., 1.), (7., 5.)])));
}
#[test]
fn linestring_in_polygon_test() {
let linestring = LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]);
let poly = Polygon::new(linestring, Vec::new());
assert!(poly.intersects(&LineString::from(vec![(2., 2.), (3., 3.)])));
}
#[test]
fn linestring_on_boundary_polygon_test() {
let poly = Polygon::new(
LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]),
Vec::new(),
);
assert!(poly.intersects(&LineString::from(vec![(0., 0.), (5., 0.)])));
assert!(poly.intersects(&LineString::from(vec![(5., 0.), (5., 6.)])));
assert!(poly.intersects(&LineString::from(vec![(5., 6.), (0., 6.)])));
assert!(poly.intersects(&LineString::from(vec![(0., 6.), (0., 0.)])));
}
#[test]
fn intersect_linestring_polygon_test() {
let poly = Polygon::new(
LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]),
Vec::new(),
);
assert!(poly.intersects(&LineString::from(vec![(2., 2.), (6., 6.)])));
}
#[test]
fn linestring_outside_polygon_test() {
let poly = Polygon::new(
LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]),
Vec::new(),
);
assert!(!poly.intersects(&LineString::from(vec![(7., 2.), (9., 4.)])));
}
#[test]
fn linestring_in_inner_polygon_test() {
let e = LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]);
let v = vec![LineString::from(vec![
(1., 1.),
(4., 1.),
(4., 4.),
(1., 4.),
(1., 1.),
])];
let poly = Polygon::new(e, v);
assert!(!poly.intersects(&LineString::from(vec![(2., 2.), (3., 3.)])));
assert!(poly.intersects(&LineString::from(vec![(2., 2.), (4., 4.)])));
}
#[test]
fn linestring_traverse_polygon_test() {
let e = LineString::from(vec![(0., 0.), (5., 0.), (5., 6.), (0., 6.), (0., 0.)]);
let v = vec![LineString::from(vec![
(1., 1.),
(4., 1.),
(4., 4.),
(1., 4.),
(1., 1.),
])];
let poly = Polygon::new(e, v);
assert!(poly.intersects(&LineString::from(vec![(2., 0.5), (2., 5.)])));
}
#[test]
fn linestring_in_inner_with_2_inner_polygon_test() {
let e = LineString::from(vec![(2., 2.), (14., 2.), (14., 8.), (2., 8.), (2., 2.)]);
let v = vec![
LineString::from(vec![(4., 3.), (7., 3.), (7., 6.), (4., 6.), (4., 3.)]),
LineString::from(vec![(9., 3.), (12., 3.), (12., 6.), (9., 6.), (9., 3.)]),
];
let poly = Polygon::new(e, v);
assert!(!poly.intersects(&LineString::from(vec![(5., 4.), (6., 5.)])));
assert!(poly.intersects(&LineString::from(vec![(11., 2.5), (11., 7.)])));
assert!(poly.intersects(&LineString::from(vec![(4., 7.), (6., 7.)])));
assert!(poly.intersects(&LineString::from(vec![(8., 1.), (8., 9.)])));
}
#[test]
fn polygons_do_not_intersect() {
let p1 = Polygon::new(
LineString::from(vec![(1., 3.), (3., 3.), (3., 5.), (1., 5.), (1., 3.)]),
Vec::new(),
);
let p2 = Polygon::new(
LineString::from(vec![
(10., 30.),
(30., 30.),
(30., 50.),
(10., 50.),
(10., 30.),
]),
Vec::new(),
);
assert!(!p1.intersects(&p2));
assert!(!p2.intersects(&p1));
}
#[test]
fn polygons_overlap() {
let p1 = Polygon::new(
LineString::from(vec![(1., 3.), (3., 3.), (3., 5.), (1., 5.), (1., 3.)]),
Vec::new(),
);
let p2 = Polygon::new(
LineString::from(vec![(2., 3.), (4., 3.), (4., 7.), (2., 7.), (2., 3.)]),
Vec::new(),
);
assert!(p1.intersects(&p2));
assert!(p2.intersects(&p1));
}
#[test]
fn polygon_contained() {
let p1 = Polygon::new(
LineString::from(vec![(1., 3.), (4., 3.), (4., 6.), (1., 6.), (1., 3.)]),
Vec::new(),
);
let p2 = Polygon::new(
LineString::from(vec![(2., 4.), (3., 4.), (3., 5.), (2., 5.), (2., 4.)]),
Vec::new(),
);
assert!(p1.intersects(&p2));
assert!(p2.intersects(&p1));
}
#[test]
fn polygons_conincident() {
let p1 = Polygon::new(
LineString::from(vec![(1., 3.), (4., 3.), (4., 6.), (1., 6.), (1., 3.)]),
Vec::new(),
);
let p2 = Polygon::new(
LineString::from(vec![(1., 3.), (4., 3.), (4., 6.), (1., 6.), (1., 3.)]),
Vec::new(),
);
assert!(p1.intersects(&p2));
assert!(p2.intersects(&p1));
}
#[test]
fn polygon_intersects_bounding_rect_test() {
let poly = Polygon::new(
LineString::from(vec![(0., 0.), (12., 0.), (12., 8.), (0., 8.), (0., 0.)]),
vec![LineString::from(vec![
(7., 4.),
(11., 4.),
(11., 7.),
(7., 7.),
(7., 4.),
])],
);
let b1 = Rect {
min: Coordinate { x: 11., y: 1. },
max: Coordinate { x: 13., y: 2. },
};
let b2 = Rect {
min: Coordinate { x: 2., y: 2. },
max: Coordinate { x: 8., y: 5. },
};
let b3 = Rect {
min: Coordinate { x: 8., y: 5. },
max: Coordinate { x: 10., y: 6. },
};
let b4 = Rect {
min: Coordinate { x: 1., y: 1. },
max: Coordinate { x: 3., y: 3. },
};
assert!(poly.intersects(&b1));
assert!(poly.intersects(&b2));
assert!(!poly.intersects(&b3));
assert!(poly.intersects(&b4));
assert!(b1.intersects(&poly));
assert!(b2.intersects(&poly));
assert!(!b3.intersects(&poly));
assert!(b4.intersects(&poly));
}
#[test]
fn bounding_rect_test() {
let bounding_rect_xl = Rect {
min: Coordinate { x: -100., y: -200. },
max: Coordinate { x: 100., y: 200. },
};
let bounding_rect_sm = Rect {
min: Coordinate { x: -10., y: -20. },
max: Coordinate { x: 10., y: 20. },
};
let bounding_rect_s2 = Rect {
min: Coordinate { x: 0., y: 0. },
max: Coordinate { x: 20., y: 30. },
};
assert_eq!(false, bounding_rect_xl.intersects(&bounding_rect_sm));
assert_eq!(false, bounding_rect_sm.intersects(&bounding_rect_xl));
assert_eq!(true, bounding_rect_sm.intersects(&bounding_rect_s2));
assert_eq!(true, bounding_rect_s2.intersects(&bounding_rect_sm));
}
#[test]
fn point_intersects_line_test() {
let p0 = Point::new(2., 4.);
let line1 = Line::from([(2., 0.), (2., 5.)]);
let line2 = Line::from([(0., 6.), (1.5, 4.5)]);
let line3 = Line::from([(0., 6.), (3., 3.)]);
let line4 = Line::from([(1., 2.), (5., 3.)]);
let line5 = Line::from([(1., 5.), (5., 6.)]);
let line6 = Line::from([(1., 2.), (5., -3.)]);
let line7 = Line::from([(1., 6.), (5., 5.)]);
assert!(line1.intersects(&p0));
assert!(p0.intersects(&line1));
assert!(!line2.intersects(&p0));
assert!(!p0.intersects(&line2));
assert!(line3.intersects(&p0));
assert!(p0.intersects(&line3));
assert!(!line4.intersects(&p0));
assert!(!p0.intersects(&line4));
assert!(!line5.intersects(&p0));
assert!(!p0.intersects(&line5));
assert!(!line6.intersects(&p0));
assert!(!p0.intersects(&line6));
assert!(!line7.intersects(&p0));
assert!(!p0.intersects(&line7));
}
#[test]
fn line_intersects_line_test() {
let line0 = Line::from([(0., 0.), (3., 4.)]);
let line1 = Line::from([(2., 0.), (2., 5.)]);
let line2 = Line::from([(0., 7.), (5., 4.)]);
let line3 = Line::from([(0., 0.), (-3., -4.)]);
assert!(line0.intersects(&line0));
assert!(line0.intersects(&line1));
assert!(!line0.intersects(&line2));
assert!(line0.intersects(&line3));
assert!(line1.intersects(&line0));
assert!(line1.intersects(&line1));
assert!(!line1.intersects(&line2));
assert!(!line1.intersects(&line3));
assert!(!line2.intersects(&line0));
assert!(!line2.intersects(&line1));
assert!(line2.intersects(&line2));
assert!(!line1.intersects(&line3));
}
#[test]
fn line_intersects_linestring_test() {
let line0 = Line::from([(0., 0.), (3., 4.)]);
let linestring0 = LineString::from(vec![(0., 1.), (1., 0.), (2., 0.)]);
let linestring1 = LineString::from(vec![(0.5, 0.2), (1., 0.), (2., 0.)]);
assert!(line0.intersects(&linestring0));
assert!(!line0.intersects(&linestring1));
assert!(linestring0.intersects(&line0));
assert!(!linestring1.intersects(&line0));
}
#[test]
fn line_intersects_polygon_test() {
let line0 = Line::from([(0.5, 0.5), (2., 1.)]);
let poly0 = Polygon::new(
LineString::from(vec![(0., 0.), (1., 2.), (1., 0.), (0., 0.)]),
vec![],
);
let poly1 = Polygon::new(
LineString::from(vec![(1., -1.), (2., -1.), (2., -2.), (1., -1.)]),
vec![],
);
let poly2 = Polygon::new(
LineString::from(vec![(-1., -1.), (-1., 10.), (10., -1.), (-1., -1.)]),
vec![LineString::from(vec![
(0., 0.),
(3., 4.),
(3., 0.),
(0., 0.),
])],
);
assert!(line0.intersects(&poly0));
assert!(poly0.intersects(&line0));
assert!(!line0.intersects(&poly1));
assert!(!poly1.intersects(&line0));
assert!(!line0.intersects(&poly2));
assert!(!poly2.intersects(&line0));
}
}