#![doc(
html_logo_url = "https://cdn.rawgit.com/urschrei/polylabel-rs/7a07336e85572eb5faaf0657c2383d7de5620cd8/ell.svg",
html_root_url = "https://docs.rs/polylabel-rs/"
)]
use geo::prelude::*;
use geo::{Point, Polygon};
use num_traits::{Float, FromPrimitive, Signed};
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::iter::Sum;
pub mod errors;
use errors::PolylabelError;
mod ffi;
pub use crate::ffi::{polylabel_ffi, Array, Position, WrapperArray};
#[derive(Debug)]
struct Qcell<T>
where
T: Float + Signed,
{
centroid: Point<T>,
extent: T,
distance: T,
max_distance: T,
}
impl<T> Qcell<T>
where
T: Float + Signed,
{
fn new(x: T, y: T, h: T, distance: T, max_distance: T) -> Qcell<T> {
Qcell {
centroid: Point::new(x, y),
extent: h,
distance,
max_distance,
}
}
}
impl<T> Ord for Qcell<T>
where
T: Float + Signed,
{
fn cmp(&self, other: &Qcell<T>) -> std::cmp::Ordering {
self.max_distance.partial_cmp(&other.max_distance).unwrap()
}
}
impl<T> PartialOrd for Qcell<T>
where
T: Float + Signed,
{
fn partial_cmp(&self, other: &Qcell<T>) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<T> Eq for Qcell<T> where T: Float + Signed {}
impl<T> PartialEq for Qcell<T>
where
T: Float + Signed,
{
fn eq(&self, other: &Qcell<T>) -> bool
where
T: Float,
{
self.max_distance == other.max_distance
}
}
fn signed_distance<T>(x: &T, y: &T, polygon: &Polygon<T>) -> T
where
T: Float,
{
let point = Point::new(*x, *y);
let inside = polygon.contains(&point);
let distance = point.euclidean_distance(polygon.exterior());
if inside {
distance
} else {
-distance
}
}
fn add_quad<T>(
mpq: &mut BinaryHeap<Qcell<T>>,
cell: &Qcell<T>,
new_height: &T,
polygon: &Polygon<T>,
) where
T: Float + Signed,
{
let two = T::one() + T::one();
let centroid_x = cell.centroid.x();
let centroid_y = cell.centroid.y();
for combo in &[
(centroid_x - *new_height, centroid_y - *new_height),
(centroid_x + *new_height, centroid_y - *new_height),
(centroid_x - *new_height, centroid_y + *new_height),
(centroid_x + *new_height, centroid_y + *new_height),
] {
let new_dist = signed_distance(&combo.0, &combo.1, polygon);
mpq.push(Qcell::new(
combo.0,
combo.1,
*new_height,
new_dist,
new_dist + *new_height * two.sqrt(),
));
}
}
pub fn polylabel<T>(polygon: &Polygon<T>, tolerance: &T) -> Result<Point<T>, PolylabelError>
where
T: Float + FromPrimitive + Signed + Sum,
{
if polygon.area() == T::zero() {
return Ok(Point::new(T::zero(), T::zero()));
}
let two = T::one() + T::one();
let centroid = polygon
.centroid()
.ok_or_else(|| PolylabelError::CentroidCalculation)?;
let bbox = polygon
.bounding_rect()
.ok_or_else(|| PolylabelError::RectCalculation)?;
let width = bbox.max.x - bbox.min.x;
let height = bbox.max.y - bbox.min.y;
let cell_size = width.min(height);
if cell_size == T::zero() {
return Ok(Point::new(bbox.min.x, bbox.min.y));
}
let mut h = cell_size / two;
let distance = signed_distance(¢roid.x(), ¢roid.y(), polygon);
let max_distance = distance + T::zero() * two.sqrt();
let mut best_cell = Qcell::new(
centroid.x(),
centroid.y(),
T::zero(),
distance,
max_distance,
);
let bbox_cell_dist = signed_distance(
&(bbox.min.x + width / two),
&(bbox.min.y + height / two),
polygon,
);
let bbox_cell = Qcell {
centroid: Point::new(bbox.min.x + width / two, bbox.min.y + height / two),
extent: T::zero(),
distance: bbox_cell_dist,
max_distance: bbox_cell_dist + T::zero() * two.sqrt(),
};
if bbox_cell.distance > best_cell.distance {
best_cell = bbox_cell;
}
let mut cell_queue: BinaryHeap<Qcell<T>> = BinaryHeap::new();
let mut x = bbox.min.x;
let mut y;
while x < bbox.max.x {
y = bbox.min.y;
while y < bbox.max.y {
let latest_dist = signed_distance(&(x + h), &(y + h), polygon);
cell_queue.push(Qcell {
centroid: Point::new(x + h, y + h),
extent: h,
distance: latest_dist,
max_distance: latest_dist + h * two.sqrt(),
});
y = y + cell_size;
}
x = x + cell_size;
}
while !cell_queue.is_empty() {
let cell = cell_queue.pop().ok_or_else(|| PolylabelError::EmptyQueue)?;
if cell.distance > best_cell.distance {
best_cell.centroid = Point::new(cell.centroid.x(), cell.centroid.y());
best_cell.extent = cell.extent;
best_cell.distance = cell.distance;
best_cell.max_distance = cell.max_distance;
}
if cell.max_distance - best_cell.distance <= *tolerance {
continue;
}
h = cell.extent / two;
add_quad(&mut cell_queue, &cell, &h, polygon);
}
Ok(Point::new(best_cell.centroid.x(), best_cell.centroid.y()))
}
#[cfg(test)]
mod tests {
use super::{polylabel, Qcell};
use geo::prelude::*;
use geo::{Point, Polygon};
use std::collections::BinaryHeap;
#[test]
fn test_polylabel() {
let coords = include!("poly1.rs");
let poly = Polygon::new(coords.into(), vec![]);
let res = polylabel(&poly, &10.000).unwrap();
assert_eq!(res, Point::new(59.35615556364569, 121.83919629746435));
}
#[test]
fn test_concave() {
let coords = include!("poly2.rs");
let poly = Polygon::new(coords.into(), vec![]);
let res = polylabel(&poly, &1.0).unwrap();
assert!(poly.contains(&res));
}
#[test]
fn test_london() {
let coords = include!("poly3.rs");
let poly = Polygon::new(coords.into(), vec![]);
let res = polylabel(&poly, &0.001).unwrap();
assert_eq!(res, Point::new(-0.45556816445920356, 51.54848888202887));
}
#[test]
fn polygon_l_test() {
let coords = vec![
(0.0, 0.0),
(4.0, 0.0),
(4.0, 1.0),
(1.0, 1.0),
(1.0, 4.0),
(0.0, 4.0),
(0.0, 0.0),
];
let poly = Polygon::new(coords.into(), vec![]);
let res = polylabel(&poly, &0.10).unwrap();
assert_eq!(res, Point::new(0.5625, 0.5625));
}
#[test]
fn degenerate_polygon_test() {
let a_coords = vec![(0.0, 0.0), (1.0, 0.0), (2.0, 0.0), (0.0, 0.0)];
let a_poly = Polygon::new(a_coords.into(), vec![]);
let a_res = polylabel(&a_poly, &1.0).unwrap();
assert_eq!(a_res, Point::new(0.0, 0.0));
}
#[test]
fn degenerate_polygon_test_2() {
let b_coords = vec![(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (1.0, 0.0), (0.0, 0.0)];
let b_poly = Polygon::new(b_coords.into(), vec![]);
let b_res = polylabel(&b_poly, &1.0).unwrap();
assert_eq!(b_res, Point::new(0.0, 0.0));
}
#[test]
fn test_queue() {
let a = Qcell {
centroid: Point::new(1.0, 2.0),
extent: 3.0,
distance: 4.0,
max_distance: 8.0,
};
let b = Qcell {
centroid: Point::new(1.0, 2.0),
extent: 3.0,
distance: 4.0,
max_distance: 7.0,
};
let c = Qcell {
centroid: Point::new(1.0, 2.0),
extent: 3.0,
distance: 4.0,
max_distance: 9.0,
};
let mut v = vec![];
v.push(a);
v.push(b);
v.push(c);
let mut q = BinaryHeap::from(v);
assert_eq!(q.pop().unwrap().max_distance, 9.0);
assert_eq!(q.pop().unwrap().max_distance, 8.0);
assert_eq!(q.pop().unwrap().max_distance, 7.0);
}
}