Opened 6 months ago

Closed 6 months ago

Last modified 6 months ago

#841 closed defect (wontfix)

Regression in prepared polygons contains

Reported by: sgillies Owned by: geos-devel@…
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:

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)
>>> geom.contains(point)

With GEOS version 3.5.1 and newer we observe

>>> shapely.prepared.prep(geom).contains(point)
>>> geom.contains(point)

Change History (4)

comment:1 Changed 6 months ago 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.

comment:2 Changed 6 months ago 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.

comment:3 Changed 6 months ago by sgillies

Resolution: wontfix
Status: newclosed

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

comment:4 Changed 6 months ago 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).

Note: See TracTickets for help on using tickets.