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
An epsilon less than or equal to zero will return an unaltered version of the geometry
Required Methods§
sourcefn simplify_vw_preserve(&self, epsilon: &T) -> Selfwhere
T: CoordFloat + RTreeNum,
fn simplify_vw_preserve(&self, epsilon: &T) -> Selfwhere 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 aLineString
, 5 for aPolygon
), 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 usesepsilon ^ 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);