Regression in prepared polygons contains

[sgillies]

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

[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.

[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.

[sgillies]

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

[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).