Using Simplification algorithm on a polygon can result in an invalid polygon

[frewsxcv]

#135 (comment)

Maybe the algorithm should sometimes return an Option<T> since it can sometimes fail.

[amandasaurus]

Polygon::new can result in an invalid polygon. 😉 This is back to the validity thing again.

Personally I think that the simplification algorithm should return the geometry type, rather than an Option. Allow the caller to call the future .is_valid() function on it.

• PostGIS's ST_Simplify can return invalid polygons.
• In PostGIS there are some ways to make some invalid geometries valid again (e.g. ST_MakeValid or the ST_Buffer(geom, 0) trick). rust-geo might have that later, in which case an invalid polygon from simplification could be "fixed" later. If we returned an Option, then you would never have the chance to return an invalid polygon.
• Some software can work with invalid polygons. I think mapnik is able to draw some invalid polygons.

[urschrei]

I've been looking at R-tree implementations in Rust again since this came up, and I'm making good progress with Spade's R* implementation, now that I've managed to implement the PointN trait for Point. I've been working on implementing the technique from here (See WIP here).

If / when that lands, I'm still in favour of returning an Option or Result from anything that can produce invalid geometries. Returning one of these doesn't preclude you from trying to fix the geometry yourself, it just gives you the choice between using an unwrap and taking your chances, or implementing your own fix. We should probably still benchmark a validity check, but unless it's hugely expensive, I think we should be erring on the side of flexible safety.

[frewsxcv]

Currently, I'm in favor of returning Option/Result types for methods/constructors that can return invalid geometries. At least for validation, right now, I'm envisioning something along the lines of:

impl<T: Float> LineString<T> {
  fn from_vec(v: Vec<T>) -> Result<LineString> { .. }

  /// << insert big disclaimer here >>
  fn from_vec_unchecked(v: Vec<T>) -> LineString { .. }
}

[frewsxcv]

Here's a simple case (epsilon = 1.0) simplifying a Polygon exterior ring that results in a ring with only two points:

Before:

LineString([Coord { x: 42.59023437500002, y: 15.303417968749995 }, Coord { x: 42.558691406250006, y: 15.281201171874995 }, Coord { x: 42.54902343750001, y: 15.320068359375 }, Coord { x: 42.56972656250002, y: 15.407324218749991 }, Coord { x: 42.60234375000002, y: 15.432519531249994 }, Coord { x: 42.62451171875, y: 15.36796875 }, Coord { x: 42.610449218750006, y: 15.332275390625 }, Coord { x: 42.59023437500002, y: 15.303417968749995 }])

After:

LineString([Coord { x: 42.59023437500002, y: 15.303417968749995 }, Coord { x: 42.59023437500002, y: 15.303417968749995 }])

[frewsxcv]

In the case of polygon rings, could we just break once the LineString ring is 3 coordinates?

[urschrei]

I think so (that's what we do in visvalingam_preserve – actually it's 4 coordinates there, but no matter) but is there a perf hit for checking the length on every loop?

[frewsxcv]

Here's my fix attempt: #943