[GEOS] #959: Reversed result in GEOSClipByRect

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

[GEOS] #959: Reversed result in GEOSClipByRect

geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+--------------------------
 Reporter:  Algunenano   |      Owner:  geos-devel@…
     Type:  defect       |     Status:  new
 Priority:  major        |  Milestone:  3.5.2
Component:  Default      |    Version:  3.5.0
 Severity:  Significant  |   Keywords:
-------------------------+--------------------------
 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).

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:
 Keywords:               |
-------------------------+---------------------------
Changes (by Algunenano):

 * Attachment "clip.png" added.

 Visualized. Red = expected result. Orange = current result

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by Algunenano):

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

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:1>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by strk):

 I think by definition invalid inputs result in invalid outputs

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:2>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:3>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:4>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:5>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:
 Keywords:               |
-------------------------+---------------------------

Comment (by 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.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:6>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  closed
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:  invalid
 Keywords:               |
-------------------------+---------------------------
Changes (by Algunenano):

 * status:  new => closed
 * resolution:   => invalid


Comment:

 > 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

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:7>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #959: Reversed result in GEOSClipByRect

geos-2
In reply to this post by geos-2
#959: Reversed result in GEOSClipByRect
-------------------------+---------------------------
 Reporter:  Algunenano   |       Owner:  geos-devel@…
     Type:  defect       |      Status:  closed
 Priority:  major        |   Milestone:  3.5.2
Component:  Default      |     Version:  3.5.0
 Severity:  Significant  |  Resolution:  invalid
 Keywords:               |
-------------------------+---------------------------

Comment (by mdavis):

 Replying to [comment:7 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.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/959#comment:8>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel