use crate::prelude::*;
use crate::{Closest, Line, LineString, MultiLineString, MultiPoint, MultiPolygon, Point, Polygon};
use num_traits::Float;
use std::iter;
pub trait ClosestPoint<F: Float, Rhs = Point<F>> {
fn closest_point(&self, p: &Rhs) -> Closest<F>;
}
impl<'a, F, C> ClosestPoint<F> for &'a C
where
C: ClosestPoint<F>,
F: Float,
{
fn closest_point(&self, p: &Point<F>) -> Closest<F> {
(*self).closest_point(p)
}
}
impl<F: Float> ClosestPoint<F> for Point<F> {
fn closest_point(&self, p: &Self) -> Closest<F> {
if self == p {
Closest::Intersection(*self)
} else {
Closest::SinglePoint(*self)
}
}
}
impl<F: Float> ClosestPoint<F> for Line<F> {
fn closest_point(&self, p: &Point<F>) -> Closest<F> {
let line_length = self.euclidean_length();
if line_length == F::zero() {
return Closest::Indeterminate;
}
let direction_vector = Point(self.end) - Point(self.start);
let to_p = *p - Point(self.start);
let t = to_p.dot(direction_vector) / direction_vector.dot(direction_vector);
if t < F::zero() {
return Closest::SinglePoint(self.start.into());
} else if t > F::one() {
return Closest::SinglePoint(self.end.into());
}
let x = direction_vector.x();
let y = direction_vector.y();
let displacement = Point::new(t * x, t * y);
let c = Point(self.start) + displacement;
if self.contains(p) {
Closest::Intersection(c)
} else {
Closest::SinglePoint(c)
}
}
}
fn closest_of<C, F, I>(iter: I, p: Point<F>) -> Closest<F>
where
F: Float,
I: IntoIterator<Item = C>,
C: ClosestPoint<F>,
{
let mut best = Closest::Indeterminate;
for line_segment in iter {
let got = line_segment.closest_point(&p);
best = got.best_of_two(&best, p);
}
best
}
impl<F: Float> ClosestPoint<F> for LineString<F> {
fn closest_point(&self, p: &Point<F>) -> Closest<F> {
closest_of(self.lines(), *p)
}
}
impl<F: Float> ClosestPoint<F> for Polygon<F> {
fn closest_point(&self, p: &Point<F>) -> Closest<F> {
let prospectives = self.interiors().iter().chain(iter::once(self.exterior()));
closest_of(prospectives, *p)
}
}
impl<F: Float> ClosestPoint<F> for MultiPolygon<F> {
fn closest_point(&self, p: &Point<F>) -> Closest<F> {
closest_of(self.0.iter(), *p)
}
}
impl<F: Float> ClosestPoint<F> for MultiPoint<F> {
fn closest_point(&self, p: &Point<F>) -> Closest<F> {
closest_of(self.0.iter(), *p)
}
}
impl<F: Float> ClosestPoint<F> for MultiLineString<F> {
fn closest_point(&self, p: &Point<F>) -> Closest<F> {
closest_of(self.0.iter(), *p)
}
}
#[cfg(test)]
mod tests {
use super::*;
macro_rules! closest {
(intersects: $name:ident, $p:expr) => {
closest!($name, $p => Closest::Intersection($p.into()));
};
($name:ident, $p:expr => $should_be:expr) => {
#[test]
fn $name() {
let line: Line<f32> = Line::from([(0., 0.), (100.0, 100.0)]);
let p: Point<f32> = $p.into();
let should_be: Closest<f32> = $should_be;
let got = line.closest_point(&p);
assert_eq!(got, should_be);
}
};
}
closest!(intersects: start_point, (0.0, 0.0));
closest!(intersects: end_point, (100.0, 100.0));
closest!(intersects: mid_point, (50.0, 50.0));
closest!(in_line_far_away, (1000.0, 1000.0) => Closest::SinglePoint(Point::new(100.0, 100.0)));
closest!(perpendicular_from_50_50, (0.0, 100.0) => Closest::SinglePoint(Point::new(50.0, 50.0)));
fn a_square(width: f32) -> LineString<f32> {
LineString::from(vec![
(0.0, 0.0),
(width, 0.0),
(width, width),
(0.0, width),
(0.0, 0.0),
])
}
fn random_looking_points() -> Vec<Point<f32>> {
vec![
(0.0, 0.0),
(100.0, 100.0),
(1000.0, 1000.0),
(100.0, 0.0),
(50.0, 50.0),
(1234.567, -987.6543),
]
.into_iter()
.map(Point::from)
.collect()
}
fn fuzz_two_impls<A, B>(left: A, right: B)
where
A: ClosestPoint<f32>,
B: ClosestPoint<f32>,
{
let some_random_points = random_looking_points();
for (i, random_point) in some_random_points.into_iter().enumerate() {
let p: Point<_> = random_point.into();
let got_from_left = left.closest_point(&p);
let got_from_right = right.closest_point(&p);
assert_eq!(
got_from_left, got_from_right,
"{}: {:?} got {:?} and {:?}",
i, p, got_from_left, got_from_right
);
}
}
#[test]
fn zero_length_line_is_indeterminate() {
let line: Line<f32> = Line::from([(0.0, 0.0), (0.0, 0.0)]);
let p: Point<f32> = Point::new(100.0, 100.0);
let should_be: Closest<f32> = Closest::Indeterminate;
let got = line.closest_point(&p);
assert_eq!(got, should_be);
}
#[test]
fn line_string_with_single_element_behaves_like_line() {
let points = vec![(0.0, 0.0), (100.0, 100.0)];
let line_string = LineString::<f32>::from(points.clone());
let line = Line::new(points[0], points[1]);
fuzz_two_impls(line, line_string);
}
#[test]
fn empty_line_string_is_indeterminate() {
let ls: LineString<f32> = LineString(Vec::new());
let p = Point::new(0.0, 0.0);
let got = ls.closest_point(&p);
assert_eq!(got, Closest::Indeterminate);
}
#[test]
fn simple_polygon_is_same_as_linestring() {
let square: LineString<f32> = a_square(100.0);
let poly = Polygon::new(square.clone(), Vec::new());
fuzz_two_impls(square, poly);
}
fn holy_polygon() -> Polygon<f32> {
let square: LineString<f32> = a_square(100.0);
let ring_1 = a_square(20.0).translate(20.0, 10.0);
let ring_2 = a_square(10.0).translate(70.0, 60.0);
Polygon::new(square.clone(), vec![ring_1, ring_2])
}
#[test]
fn polygon_without_rings_and_point_outside_is_same_as_linestring() {
let poly = holy_polygon();
let p = Point::new(1000.0, 12345.6789);
assert!(
!poly.exterior().contains(&p),
"`p` should be outside the polygon!"
);
let poly_closest = poly.closest_point(&p);
let exterior_closest = poly.exterior().closest_point(&p);
assert_eq!(poly_closest, exterior_closest);
}
#[test]
fn polygon_with_point_on_interior_ring() {
let poly = holy_polygon();
let p = poly.interiors()[0].0[3];
let should_be = Closest::Intersection(p.into());
let got = poly.closest_point(&p.into());
assert_eq!(got, should_be);
}
#[test]
fn polygon_with_point_near_interior_ring() {
let poly = holy_polygon();
let random_ring_corner = poly.interiors()[0].0[3];
let p = Point(random_ring_corner).translate(-3.0, 3.0);
let should_be = Closest::SinglePoint(random_ring_corner.into());
println!("{:?} {:?}", p, random_ring_corner);
let got = poly.closest_point(&p);
assert_eq!(got, should_be);
}
}