use crate::{
CoordFloat, EuclideanLength, Line, LineInterpolatePoint, LineString, MultiLineString,
MultiPolygon, Point, Polygon, Rect, Triangle,
};
pub trait Densify<F: CoordFloat> {
type Output;
fn densify(&self, max_distance: F) -> Self::Output;
}
fn densify_line<T: CoordFloat>(line: Line<T>, container: &mut Vec<Point<T>>, max_distance: T) {
assert!(max_distance > T::zero());
container.push(line.start_point());
let num_segments = (line.euclidean_length() / max_distance)
.ceil()
.to_u64()
.unwrap();
let frac = T::one() / T::from(num_segments).unwrap();
for segment_idx in 1..num_segments {
let ratio = frac * T::from(segment_idx).unwrap();
let interpolated_point = line
.line_interpolate_point(ratio)
.expect("ratio should be between 0..1");
container.push(interpolated_point);
}
}
impl<T> Densify<T> for MultiPolygon<T>
where
T: CoordFloat,
Line<T>: EuclideanLength<T>,
LineString<T>: EuclideanLength<T>,
{
type Output = MultiPolygon<T>;
fn densify(&self, max_distance: T) -> Self::Output {
MultiPolygon::new(
self.iter()
.map(|polygon| polygon.densify(max_distance))
.collect(),
)
}
}
impl<T> Densify<T> for Polygon<T>
where
T: CoordFloat,
Line<T>: EuclideanLength<T>,
LineString<T>: EuclideanLength<T>,
{
type Output = Polygon<T>;
fn densify(&self, max_distance: T) -> Self::Output {
let densified_exterior = self.exterior().densify(max_distance);
let densified_interiors = self
.interiors()
.iter()
.map(|ring| ring.densify(max_distance))
.collect();
Polygon::new(densified_exterior, densified_interiors)
}
}
impl<T> Densify<T> for MultiLineString<T>
where
T: CoordFloat,
Line<T>: EuclideanLength<T>,
LineString<T>: EuclideanLength<T>,
{
type Output = MultiLineString<T>;
fn densify(&self, max_distance: T) -> Self::Output {
MultiLineString::new(
self.iter()
.map(|linestring| linestring.densify(max_distance))
.collect(),
)
}
}
impl<T> Densify<T> for LineString<T>
where
T: CoordFloat,
Line<T>: EuclideanLength<T>,
LineString<T>: EuclideanLength<T>,
{
type Output = LineString<T>;
fn densify(&self, max_distance: T) -> Self::Output {
let mut new_line = vec![];
self.lines()
.for_each(|line| densify_line(line, &mut new_line, max_distance));
new_line.push(self.points().last().unwrap());
LineString::from(new_line)
}
}
impl<T> Densify<T> for Line<T>
where
T: CoordFloat,
Line<T>: EuclideanLength<T>,
LineString<T>: EuclideanLength<T>,
{
type Output = LineString<T>;
fn densify(&self, max_distance: T) -> Self::Output {
let mut new_line = vec![];
densify_line(*self, &mut new_line, max_distance);
new_line.push(self.end_point());
LineString::from(new_line)
}
}
impl<T> Densify<T> for Triangle<T>
where
T: CoordFloat,
Line<T>: EuclideanLength<T>,
LineString<T>: EuclideanLength<T>,
{
type Output = Polygon<T>;
fn densify(&self, max_distance: T) -> Self::Output {
self.to_polygon().densify(max_distance)
}
}
impl<T> Densify<T> for Rect<T>
where
T: CoordFloat,
Line<T>: EuclideanLength<T>,
LineString<T>: EuclideanLength<T>,
{
type Output = Polygon<T>;
fn densify(&self, max_distance: T) -> Self::Output {
self.to_polygon().densify(max_distance)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{coord, Coord};
#[test]
fn test_polygon_densify() {
let linestring: LineString<f64> =
vec![[-5.0, 0.0], [0.0, 5.0], [5.0, 0.0], [-5.0, 0.0]].into();
let interior: LineString<f64> =
vec![[-3.0, 0.0], [0.0, 3.0], [3.0, 0.0], [-3.0, 0.0]].into();
let polygon = Polygon::new(linestring, vec![interior]);
let correct_ext: LineString<f64> = LineString(vec![
Coord { x: -5.0, y: 0.0 },
Coord { x: -3.75, y: 1.25 },
Coord { x: -2.5, y: 2.5 },
Coord { x: -1.25, y: 3.75 },
Coord { x: 0.0, y: 5.0 },
Coord { x: 1.25, y: 3.75 },
Coord { x: 2.5, y: 2.5 },
Coord { x: 3.75, y: 1.25 },
Coord { x: 5.0, y: 0.0 },
Coord { x: 3.0, y: 0.0 },
Coord { x: 1.0, y: 0.0 },
Coord {
x: -1.0000000000000009,
y: 0.0,
},
Coord { x: -3.0, y: 0.0 },
Coord { x: -5.0, y: 0.0 },
]);
let correct_int: LineString<f64> = LineString(vec![
Coord { x: -3.0, y: 0.0 },
Coord { x: -2.0, y: 1.0 },
Coord { x: -1.0, y: 2.0 },
Coord { x: 0.0, y: 3.0 },
Coord { x: 1.0, y: 2.0 },
Coord { x: 2.0, y: 1.0 },
Coord { x: 3.0, y: 0.0 },
Coord { x: 1.0, y: 0.0 },
Coord { x: -1.0, y: 0.0 },
Coord { x: -3.0, y: 0.0 },
]);
let correct_polygon = Polygon::new(correct_ext, vec![correct_int]);
let max_dist = 2.0;
let densified = polygon.densify(max_dist);
assert_eq!(densified, correct_polygon);
}
#[test]
fn test_linestring_densify() {
let linestring: LineString<f64> =
vec![[-1.0, 0.0], [0.0, 0.0], [0.0, 6.0], [1.0, 8.0]].into();
let correct: LineString<f64> = vec![
[-1.0, 0.0],
[0.0, 0.0],
[0.0, 2.0],
[0.0, 4.0],
[0.0, 6.0],
[0.5, 7.0],
[1.0, 8.0],
]
.into();
let max_dist = 2.0;
let densified = linestring.densify(max_dist);
assert_eq!(densified, correct);
}
#[test]
fn test_line_densify() {
let line: Line<f64> = Line::new(coord! {x: 0.0, y: 6.0}, coord! {x: 1.0, y: 8.0});
let correct: LineString<f64> = vec![[0.0, 6.0], [0.5, 7.0], [1.0, 8.0]].into();
let max_dist = 2.0;
let densified = line.densify(max_dist);
assert_eq!(densified, correct);
}
}