use super::kernels::*;
use crate::prelude::*;
use crate::*;
use num_traits::Signed;
fn above<T>(u: Coordinate<T>, vi: Coordinate<T>, vj: Coordinate<T>) -> bool
where
T: CoordinateType + Signed + HasKernel,
{
T::Ker::dot_product_sign(u, vi - vj) == Orientation::CounterClockwise
}
#[allow(dead_code)]
fn below<T>(u: Coordinate<T>, vi: Coordinate<T>, vj: Coordinate<T>) -> bool
where
T: CoordinateType + Signed + HasKernel,
{
T::Ker::dot_product_sign(u, vi - vj) == Orientation::Clockwise
}
fn find_extreme_indices<T, F>(func: F, polygon: &Polygon<T>) -> Result<Extremes, ()>
where
T: HasKernel + Signed,
F: Fn(Coordinate<T>, &Polygon<T>) -> Result<usize, ()>,
{
if !polygon.exterior().is_convex() {
return Err(());
}
let directions: Vec<Coordinate<_>> = vec![
(T::zero(), -T::one()).into(),
(T::one(), T::zero()).into(),
(T::zero(), T::one()).into(),
(-T::one(), T::zero()).into(),
];
Ok(directions
.into_iter()
.map(|p| func(p, polygon).unwrap())
.collect::<Vec<usize>>()
.into())
}
fn polymax_naive_indices<T>(u: Coordinate<T>, poly: &Polygon<T>) -> Result<usize, ()>
where
T: HasKernel + Signed,
{
let vertices = &poly.exterior().0;
let mut max: usize = 0;
for (i, _) in vertices.iter().enumerate() {
if above(u, vertices[i], vertices[max]) {
max = i;
}
}
Ok(max)
}
pub trait ExtremeIndices {
fn extreme_indices(&self) -> Result<Extremes, ()>;
}
impl<T> ExtremeIndices for Polygon<T>
where
T: Signed + HasKernel,
{
fn extreme_indices(&self) -> Result<Extremes, ()> {
find_extreme_indices(polymax_naive_indices, self)
}
}
impl<T> ExtremeIndices for MultiPolygon<T>
where
T: Signed + HasKernel,
{
fn extreme_indices(&self) -> Result<Extremes, ()> {
find_extreme_indices(polymax_naive_indices, &self.convex_hull())
}
}
impl<T> ExtremeIndices for MultiPoint<T>
where
T: Signed + HasKernel,
{
fn extreme_indices(&self) -> Result<Extremes, ()> {
find_extreme_indices(polymax_naive_indices, &self.convex_hull())
}
}
pub trait ExtremePoints {
type Scalar: CoordinateType;
fn extreme_points(&self) -> ExtremePoint<Self::Scalar>;
}
impl<T, G> ExtremePoints for G
where
T: Signed + HasKernel,
G: ConvexHull<Scalar = T> + ExtremeIndices,
{
type Scalar = T;
fn extreme_points(&self) -> ExtremePoint<T> {
let ch = self.convex_hull();
let indices = ch.extreme_indices().unwrap();
ExtremePoint {
ymin: Point(ch.exterior().0[indices.ymin]),
xmax: Point(ch.exterior().0[indices.xmax]),
ymax: Point(ch.exterior().0[indices.ymax]),
xmin: Point(ch.exterior().0[indices.xmin]),
}
}
}
#[cfg(test)]
mod test {
use super::*;
use crate::{point, polygon};
#[test]
fn test_polygon_extreme_x() {
let poly1 = polygon![
(x: 1.0, y: 0.0),
(x: 2.0, y: 1.0),
(x: 1.0, y: 2.0),
(x: 0.0, y: 1.0),
(x: 1.0, y: 0.0)
];
let min_x = polymax_naive_indices(Coordinate { x: -1., y: 0. }, &poly1).unwrap();
let correct = 3_usize;
assert_eq!(min_x, correct);
}
#[test]
#[should_panic]
fn test_extreme_indices_bad_polygon() {
let poly1 = polygon![
(x: 1.0, y: 0.0),
(x: 1.3, y: 1.),
(x: 2.0, y: 1.0),
(x: 1.75, y: 1.75),
(x: 1.0, y: 2.0),
(x: 0.0, y: 1.0),
(x: 1.0, y: 0.0)
];
let extremes = find_extreme_indices(polymax_naive_indices, &poly1).unwrap();
let correct = Extremes {
ymin: 0,
xmax: 1,
ymax: 3,
xmin: 4,
};
assert_eq!(extremes, correct);
}
#[test]
fn test_extreme_indices_good_polygon() {
let poly1 = polygon![
(x: 1.0, y: 0.0),
(x: 1.3, y: 1.),
(x: 2.0, y: 1.0),
(x: 1.75, y: 1.75),
(x: 1.0, y: 2.0),
(x: 0.0, y: 1.0),
(x: 1.0, y: 0.0)
];
let extremes = find_extreme_indices(polymax_naive_indices, &poly1.convex_hull()).unwrap();
let correct = Extremes {
ymin: 0,
xmax: 1,
ymax: 3,
xmin: 4,
};
assert_eq!(extremes, correct);
}
#[test]
fn test_polygon_extreme_wrapper_convex() {
let poly1 = polygon![
(x: 1.0, y: 0.0),
(x: 2.0, y: 1.0),
(x: 1.75, y: 1.75),
(x: 1.0, y: 2.0),
(x: 0.0, y: 1.0),
(x: 1.0, y: 0.0)
];
let extremes = find_extreme_indices(polymax_naive_indices, &poly1.convex_hull()).unwrap();
let correct = Extremes {
ymin: 0,
xmax: 1,
ymax: 3,
xmin: 4,
};
assert_eq!(extremes, correct);
}
#[test]
fn test_polygon_extreme_point_x() {
let poly1 = polygon![
(x: 1.0, y: 0.0),
(x: 2.0, y: 1.0),
(x: 1.0, y: 2.0),
(x: 0.0, y: 1.0),
(x: 1.0, y: 0.0)
];
let extremes = poly1.extreme_points();
let correct = point!(x: 0.0, y: 1.0);
assert_eq!(extremes.xmin, correct);
}
}