Trait geo::algorithm::simplify_vw::SimplifyVwPreserve

source · 
pub trait SimplifyVwPreserve<T, Epsilon = T> {
    // Required method
    fn simplify_vw_preserve(&self, epsilon: &T) -> Self
       where T: CoordFloat + RTreeNum;
}
Expand description

Simplifies a geometry, attempting to preserve its topology by removing self-intersections

A larger epsilon means being more aggressive about removing points with less concern for maintaining the existing shape. Specifically, when you consider whether to remove a point, you can draw a triangle consisting of the candidate point and the points before and after it. If the area of this triangle is less than epsilon, we will remove the point.

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

Required Methods§

source

fn simplify_vw_preserve(&self, epsilon: &T) -> Self
where T: CoordFloat + RTreeNum,

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.

§Notes
  • It is possible for the simplification algorithm to displace a Polygon’s interior ring outside its shell.
  • The algorithm does not guarantee a valid output geometry, especially on smaller geometries.
  • If removal of a point causes a self-intersection, but the geometry only has n + 1 points remaining (3 for a LineString, 5 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.
  • The tolerance used to remove a point is epsilon, in keeping with GEOS. JTS uses epsilon ^ 2
§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.simplify_vw_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);

Object Safety§

This trait is not object safe.

Implementors§