Reversed result in GEOSClipByRect

[Algunenano]

When passing the following invalid geometry to GEOSClipByRect, the result of the clipping is reversed (you get the part of the box that doesn't intersects with the geometry).

template<> template<> void object::test<14>
()
{
    const char* wkt = "POLYGON((680 2050,682 2050,683 2054,686 2059,690 2061,694 2062,697 2065,699 2071,700 2080,701 2081,702 2081,703 2082,702 2083,701 2084,701 2085,699 2086,700 2086,699 2086,698 2085,699 2085,695 2083,689 2083,687 2083,685 2085,679 2083,677 2081,677 2078,673 2069,668 2062,667 2062,666 2062,665 2060,667 2058,667 2056,665 2055,666 2055,666 2054,667 2053,666 2052,667 2050,668 2050,670 2054,672 2052,673 2053,674 2052,676 2050,679 2050,680 2050))";
    geom1_ = GEOSGeomFromWKT(wkt);
    geom2_ = GEOSClipByRect(geom1_, -8, -8, 2056, 2056);
    isEqual(geom2_, "POLYGON((665 2055,667 2056,684.2 2056,683 2054,682 2050,680 2050,679 2050,676 2050,674 2052,673 2053,672 2052,670 2054,668 2050,667 2050,666 2052,667 2053,666 2054,666 2055,665 2055))");
}

This is affecting Postgis, both in ST_ClipByBox2d and ST_AsMVTGeom (although it has a hack to try to detect this and drop the geometry completely).

[Algunenano]

Visualized. Red = expected result. Orange = current result

[Algunenano]

Related PR with just the broken test case: ​https://github.com/libgeos/geos/pull/152

[strk]

I think by definition invalid inputs result in invalid outputs

[mdavis]

Given that this geometry is only slightly invalid (a single collapsed line segment), and given the relatively simplicity of clipping to a rectangle, it seems like it might be technically feasible to make clipping more tolerant of some invalid inputs. This might require an entirely new algorithm, though.

The other option for now is to ensure the input geometry is valid. In this case that can be done via a simple linear scan of the polygon ring, to detect and remove the collapsed segment. Perhaps that can be provided as a utility function. Or perhaps MakeValid could be enhanced with hints to optimize what kinds of cleaning approaches are used.

[Algunenano]

I think by definition invalid inputs result in invalid outputs

Fair enough, but then ST_AsMvtGeom shouldn't be using it. To be honest, I'm already on the verge of removing the geos path and leave wagyu as the only option for clipping and validation for MVT polygons.

Given that this geometry is only slightly invalid (a single collapsed line segment), and given the relatively simplicity of clipping to a rectangle, it seems like it might be technically feasible to make clipping more tolerant of some invalid inputs. This might require an entirely new algorithm, though.

What surprised me the most is that it gives this invalid input although the invalid spike is outside the clipping rectangle (which is the only ring). I haven't checked the algorithm that Geos uses yet.

As a reference, here is the current quick clip mechanism in wagyu: ​https://github.com/postgis/postgis/blob/svn-trunk/deps/wagyu/include/mapbox/geometry/wagyu/quick_clip.hpp#L67

[mdavis]

That wagyu quick clip algorithm will certainly be fast. But it will produce highly invalid geometry from a GEOS geometry model perspective. That may not matter for tile rendering, of course.

But then it's doing something different than GEOSClipByRect, which is intended to produce valid geometry. This is a harder task, so slower and more demanding of the input.

If MVT Tile generation can get away with a less restrictive geometry model and hence faster/simpler algorithms, that's great. But perhaps those algorithms should not be in GEOS, or at least they should be in a separate package.

[mdavis]

Is the wagyu quick_clip all that is needed for clipping MVT polygons? If so, that's easy to port. If not, then it's not the real comparison.

[Algunenano]

Is the wagyu quick_clip all that is needed for clipping MVT polygons? If so, that's easy to port. If not, then it's not the real comparison.

Yes and no, wagyu guarantees that the output will always be valid (it does a pass later for force validation with int coordinates). In exchange it might drop small triangles of a multipolygon, which you can't get away with in MVTs as it's normal for things to pop up/out and you zoom in/out.

It doesn't make much sense to port that clipping algorithm without the whole paraphernalia (quick validation with int coordinates). I found and even harder issue around mvts today [1] where making a polygon valid changed some of its coordinates to floats (against the mvt spec), then snapping them to ints turned it invalid (against the mvt spec), and so on.

Based on this, I think I'll keep dropping geometries when this happens and push to make wagyu the default for 3.0.

Thanks a lot for the comments @mdavis.

1 - ​https://trac.osgeo.org/postgis/ticket/4348

[mdavis]

Replying to Algunenano:

It doesn't make much sense to port that clipping algorithm without the whole paraphernalia (quick validation with int coordinates).

Ok, so any replacement/improvement to GEOS-based MVT clipping has to produce valid integer geoms.

I found and even harder issue around mvts today [1] where making a polygon valid changed some of its coordinates to floats (against the mvt spec), then snapping them to ints turned it invalid (against the mvt spec), and so on.

Not totally surprising. MakeValid operates at full precision, and can introduce new vertices. And because it is using full precision, the output will not necessarily be valid when snapped to lower precision.

The JTS (and probably GEOS) operations can actually specify a precision model, which might solve this problem. It would have to be exposed by MakeValid, however. And MakeValid is doing a LOT of complex processing, so not sure that's even feasible. Also, for the kind of invalidity produced by brute-force clipping to a rectangle (as in quick_clip), MakeValid is probably overkill. It might be possible to just node the clipped linework (using int precision), and then polygonize. I will try and experiment with this. If that works, it would provide a fairly simple GEOS-based rectangle clipper for MVT use.