Trait geo::algorithm::simplifyvw::SimplifyVWPreserve
[−]
[src]
pub trait SimplifyVWPreserve<T, Epsilon = T> { fn simplifyvw_preserve(&self, epsilon: &T) -> Self
where
T: Float + SpadeFloat; }
Simplifies a geometry, preserving its topology by removing self-intersections
Required Methods
fn simplifyvw_preserve(&self, epsilon: &T) -> Self where
T: Float + SpadeFloat,
T: Float + SpadeFloat,
Returns the simplified representation of a geometry, using a topology-preserving variant of the Visvalingam-Whyatt algorithm.
See here for a graphical explanation.
The topology-preserving algorithm uses an R* tree to efficiently find candidate line segments which are tested for intersection with a given triangle. If intersections are found, the previous point (i.e. the left component of the current triangle) is also removed, altering the geometry and removing the intersection.
In the example below, (135.0, 68.0)
would be retained by the standard algorithm,
forming triangle (0, 1, 3),
which intersects with the segments (280.0, 19.0), (117.0, 48.0)
and (117.0, 48.0), (300,0, 40.0)
. By removing it,
a new triangle with indices (0, 3, 4)
is formed, which does not cause a self-intersection.
Note: it is possible for the simplification algorithm to displace a Polygon's interior ring outside its shell.
Note: if removal of a point causes a self-intersection, but the geometry only has n + 2
points remaining (4 for a LineString
, 6 for a Polygon
), the point is retained and the
simplification process ends. This is because there is no guarantee that removal of two points will remove
the intersection, but removal of further points would leave too few points to form a valid geometry.
use geo::{Point, LineString}; use geo::algorithm::simplifyvw::{SimplifyVWPreserve}; let mut vec = Vec::new(); vec.push(Point::new(10., 60.)); vec.push(Point::new(135., 68.)); vec.push(Point::new(94., 48.)); vec.push(Point::new(126., 31.)); vec.push(Point::new(280., 19.)); vec.push(Point::new(117., 48.)); vec.push(Point::new(300., 40.)); vec.push(Point::new(301., 10.)); let linestring = LineString(vec); let mut compare = Vec::new(); compare.push(Point::new(10., 60.)); compare.push(Point::new(126., 31.)); compare.push(Point::new(280., 19.)); compare.push(Point::new(117., 48.)); compare.push(Point::new(300., 40.)); compare.push(Point::new(301., 10.)); let ls_compare = LineString(compare); let simplified = linestring.simplifyvw_preserve(&668.6); assert_eq!(simplified, ls_compare)
Implementors
impl<T> SimplifyVWPreserve<T> for LineString<T> where
T: Float + SpadeFloat,impl<T> SimplifyVWPreserve<T> for MultiLineString<T> where
T: Float + SpadeFloat,impl<T> SimplifyVWPreserve<T> for Polygon<T> where
T: Float + SpadeFloat,impl<T> SimplifyVWPreserve<T> for MultiPolygon<T> where
T: Float + SpadeFloat,