use RingClipper for polygon clip in RectangeIntersection

[kalenikaliaksandr]

There is a bug in ST_ClipByBox2D.

select st_astext(st_clipbybox2d('POLYGON((10 0, 10 60, 50 20, 90 60, 90 0, 10 0))'::geometry, 'POLYGON((30 20, 30 40, 70 40, 70 20, 30 20))'::geometry));
┌────────────────────────────────────┐
│             st_astext              │
├────────────────────────────────────┤
│ POLYGON((30 40,50 20,70 40,30 40)) │
└────────────────────────────────────┘
(1 row)

In this example input geometry has coincident segments along the sides of clip rectangle. It is noted that output might be self-intersecting geometry but for this case produced polygon contains part of rectangle that doesn't has overlap with input geometry. The bug is located in the code that tries to build polygon from clipped lines and clip rectangle.

In this PR I replaced part of RectangleIntersection class responsible for polygon clip with RingClipper which still might produce invalid geometry but doesn't suffer from mentioned bug in current implementation.

[dr-jts]

OverlayNG has an optimization for intersection, which should provide very good performance for intersection with rectangles. Any idea if ST_ClipByBox2D is still faster?

[pramsey]

I think we might need to actually benchmark this out, since if NG is just faster for rectangles, the best thing to do us remove all the old rectangle code and delegate to NG.

[dr-jts]

I think we might need to actually benchmark this out, since if NG is just faster for rectangles, the best thing to do us remove all the old rectangle code and delegate to NG.

Absolutely. I can take this on.

[kalenikaliaksandr]

I tested from PostGIS using following query select count(*) from (select ST_Subdivide(geom, 30) from large_country_boundary) q;
using PostGIS built from master that uses OverlayNG to clip polygon in ST_Subdivide: 1651,973 ms
using modified PostGIS that uses GEOSClipByRect to clip polygon in ST_Subdivide: 168,398 ms

GEOSClipByRect is significantly faster but subdivision contains invalid polygons so maybe it's worth using NG for clip despite worse performance.

[dr-jts]

GEOSClipByRect is significantly faster but subdivision contains invalid polygons so maybe it's worth using NG for clip despite worse performance.

Makes sense to me. The output from ST_Subdivide should be valid, since it is often used for further querying.

[kalenikaliaksandr]

Makes sense to me. The output from ST_Subdivide should be valid, since it is often used for further querying.

ST_Subdivide doesn't use GEOSClipByRect with current implementation, it uses OverlayNG. I made ST_Subdivide to use GEOSClipByRect for my benchmark.

if ST_ClipByBox2D is still faster?

Yes, GEOSClipByRect is still faster than OverlayNG. At least for my test input. But sometimes it produces invalid geometries. Actually it's noted in PostGIS documentation that invalid geometries might be produced https://postgis.net/docs/ST_ClipByBox2D.html.

[pramsey]

This either needs to be a more thorough-going fix to the RectangleIntersection that does not produce new and exciting invalidities while getting rid of other ones, or to be abandoned on the principle of "the devil you know".

[pramsey]

These are pretty big changes in behaviour...

[pramsey]

Lots of holes-over-shells cases come out of this change.

[pramsey]

This is way worse than before... the result is a hole exactly on the shell. Which is, yes, empty, but far less legibly than what came before. Is the juice worth the squeeze here?

[kalenikaliaksandr]

@pramsey thank you for review.

This is way worse than before... the result is a hole exactly on the shell. Which is, yes, empty, but far less legibly than what came before. Is the juice worth the squeeze here?

right, with these changes there are plenty of cases when geometry becomes invalid after clip whereas with current implementation it's fine but all these geometries are possible to fix with ST_MakeValid while the example I provided in description is unrepairable because polygon is constructed from wrong part of rectangle.

That is what happens when subdivision is done using current ST_ClipByBox2D:

So I would prefer to have more cases where invalid geometries are produces but these geometries are repairable over function that almost always ok but sometimes outputs completely broken geometry.

For me it looks like making ST_ClipByBox2D use OverlayNG like @dr-jts suggested is the best option here.

[pramsey]

Yes, it seems validity is the highest order concern. Although aren't we already using OverlayNG in subdivide?

[kalenikaliaksandr]

Yes, OverlayNG is already used in subdivide. I made it to use ST_ClipByBox2D for my testing purposes, it does plenty of clip operations which makes it easier to find these kind of issue.

[pramsey]

This seems to have aged out. There is perhaps a use case for rectangle (or convex?) clipping if it can be made reliable, but I don't know that this is it?