logo

Trait geo::algorithm::simplifyvw::SimplifyVWPreserve

source · [−]
pub trait SimplifyVWPreserve<T, Epsilon = T> {
    fn simplifyvw_preserve(&self, epsilon: &T) -> Self
    where
        T: CoordFloat + RTreeNum;
}
Expand description

Simplifies a geometry, preserving its topology by removing self-intersections

An epsilon less than or equal to zero will return an unaltered version of the geometry.

Required Methods

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.

Examples
use approx::assert_relative_eq;
use geo::SimplifyVWPreserve;
use geo::line_string;

let line_string = line_string![
    (x: 10., y: 60.),
    (x: 135., y: 68.),
    (x: 94., y: 48.),
    (x: 126., y: 31.),
    (x: 280., y: 19.),
    (x: 117., y: 48.),
    (x: 300., y: 40.),
    (x: 301., y: 10.),
];

let simplified = line_string.simplifyvw_preserve(&668.6);

let expected = line_string![
    (x: 10., y: 60.),
    (x: 126., y: 31.),
    (x: 280., y: 19.),
    (x: 117., y: 48.),
    (x: 300., y: 40.),
    (x: 301., y: 10.),
];

assert_relative_eq!(expected, simplified, epsilon = 1e-6);

Implementors