[GEOS] #841: Regression in prepared polygons contains

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[GEOS] #841: Regression in prepared polygons contains

geos-2
#841: Regression in prepared polygons contains
------------------------+-------------------------------
 Reporter:  sgillies    |      Owner:  geos-devel@…
     Type:  defect      |     Status:  new
 Priority:  major       |  Milestone:  3.6.3
Component:  Default     |    Version:  3.6.2
 Severity:  Unassigned  |   Keywords:  prepared contains
------------------------+-------------------------------
 Shapely users have found a regression in the contains predicate of a
 prepared polygon: https://github.com/Toblerity/Shapely/issues/519

 With GEOS 3.4.2 we see the following:


 {{{
 >>> from shapely.geometry import Point, Polygon
 >>> import shapely.prepared
 >>> point = Point(0.95, 0.05)
 >>> geom = Polygon([(0, 0), (1, 0), (0, 1), (0, 0)])
 >>> shapely.geos.geos_version
 (3, 4, 2)
 >>> shapely.prepared.prep(geom).contains(point)
 True
 >>> geom.contains(point)
 True
 }}}

 With GEOS version 3.5.1 and newer we observe

 {{{
 >>> shapely.prepared.prep(geom).contains(point)
 False
 >>> geom.contains(point)
 True
 }}}

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/841>
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] #841: Regression in prepared polygons contains

geos-2
#841: Regression in prepared polygons contains
-------------------------------+---------------------------
 Reporter:  sgillies           |       Owner:  geos-devel@…
     Type:  defect             |      Status:  new
 Priority:  major              |   Milestone:  3.6.3
Component:  Default            |     Version:  3.6.2
 Severity:  Unassigned         |  Resolution:
 Keywords:  prepared contains  |
-------------------------------+---------------------------

Comment (by mdavis):

 I can't comment on why there is a regression in GEOS, but I will note
 something "interesting" about this case.  Mathematically, the value of
 contains for this case should be FALSE.  This is because of the
 consequence of the OGC contains semantics that "Polygons do not contain
 their boundary".  That said, in JTS (all versions) the value of contains
 is TRUE (for both PreparedGeometry and Geometry)!  This is because of
 numerical precision issues.  While mathematically the point (0.95, 0.05)
 lies exactly on the line (1,0)-(0,1), slight discrepancies in the
 floating-point representation result in a non-zero determinant being
 computed in the CGAlgorithms.orientationIndex test, which in turn results
 in the point being computed as NOT on the line segment.

 Unfortunately for JTS, even the new extended-precision arithmetic approach
 still computes a non-zero determinant, due to the mathematical 0.05 being
 represented as 0.050000000000000002775557561562891 (and similarly for
 0.95).  Not sure at the moment how this can be resolved, or even whether
 it should be.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/841#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] #841: Regression in prepared polygons contains

geos-2
In reply to this post by geos-2
#841: Regression in prepared polygons contains
-------------------------------+---------------------------
 Reporter:  sgillies           |       Owner:  geos-devel@…
     Type:  defect             |      Status:  new
 Priority:  major              |   Milestone:  3.6.3
Component:  Default            |     Version:  3.6.2
 Severity:  Unassigned         |  Resolution:
 Keywords:  prepared contains  |
-------------------------------+---------------------------

Comment (by dbaston):

 If I recall (not 100% sure0 there may have been a problem pre-3.5.1 where
 the "prepared" implementation of "contains" was never actually called.
 That could explain why the prepared/standard results were in agreement,
 and are no longer.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/841#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] #841: Regression in prepared polygons contains

geos-2
In reply to this post by geos-2
#841: Regression in prepared polygons contains
-------------------------------+---------------------------
 Reporter:  sgillies           |       Owner:  geos-devel@…
     Type:  defect             |      Status:  closed
 Priority:  major              |   Milestone:  3.6.3
Component:  Default            |     Version:  3.6.2
 Severity:  Unassigned         |  Resolution:  wontfix
 Keywords:  prepared contains  |
-------------------------------+---------------------------
Changes (by sgillies):

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


Comment:

 Thanks for the responses! I think I've opened this one by mistake and will
 close it.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/841#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] #841: Regression in prepared polygons contains

geos-2
In reply to this post by geos-2
#841: Regression in prepared polygons contains
-------------------------------+---------------------------
 Reporter:  sgillies           |       Owner:  geos-devel@…
     Type:  defect             |      Status:  closed
 Priority:  major              |   Milestone:  3.6.3
Component:  Default            |     Version:  3.6.2
 Severity:  Unassigned         |  Resolution:  wontfix
 Keywords:  prepared contains  |
-------------------------------+---------------------------

Comment (by mdavis):

 Seems like Prepared and Geometry contains should always be in agreement,
 no?  So this seems like something that should be looked into.  In JTS they
 are in agreement (even though the result is not ideal/correct, as per my
 comment above).

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/841#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