id summary reporter owner description type status priority milestone component version resolution keywords cc
852 The use of tolerance in function point_in_ring is not robust. nicklas pramsey "I have taken a closer look at function point_in_ring because of my task in #846.
There is two independent problems.
the row numbers references the file lwgeom_functions_analytic.c
1) on line 1133 we find this
{{{
/* a point on the boundary of a ring is not contained. */
if (fabs(side) < 1e-12)
{
}}}
the problem here is that the calculated values ""side"" is not only related to the distance between the point and the segment but also to the length of the segment. That results in that the first example here returns false and the second true even if the point is on the exact same distance from the polygon in both cases.
{{{
select st_intersects('POINT(0.5 0.5000000000001)'::geometry, 'POLYGON((0 0, 10 10, 1 0, 0 0))'::geometry);
select st_intersects('POINT(0.5 0.500000000001)'::geometry, 'POLYGON((0 0, 1 1, 1 0, 0 0))'::geometry);
}}}
2) the second problem is the construct to first check on which side of the segment the point is with a tolerance and then deciding if the point is within the endpoints without a tolerance. The second test will make the tolerance worthless if the segment is vertical or horizontal. That is actually the reason why the bug #845 showed.
there is also a third problem with this tolerance but that doesn't cause anything wrong I think after twisting it around many times. But the use of tolerance in the macros in the begining of lilwgeom.h that looks like this
{{{
#define FP_TOLERANCE 1e-12
#define FP_LT(A, B) (((A) + FP_TOLERANCE) < (B))
#define FP_LTEQ(A, B) (((A) - FP_TOLERANCE) <= (B))
#define FP_CONTAINS_BOTTOM(A, X, B) (FP_LTEQ(A, X) && FP_LT(X, B))
}}}
makes no difference in the result in any case. It causes only a small shift in the whole calculation. If it would have made any difference I am quite sure it would also have been one or many cases where the tolerance would have caused wrong answer. But now I think it is only confusing.
The last issue I would like to just remove the tolerance part, but I suspect it is there for some reason. Does anyone remember? the regression tests passes on my computer if I remove it.
The two first problems is worse. I guess we need some sort of tolerance to be sure to catch the boundary-cases. But this is not the right way, I think I have found. Both because it gives an unpredictable tolerance as shown in 1) and second because there is no tolerance at all in vertical and horizontal segments.
I attach an image showing the point and polygon from #845 to illustrate. The distance betwen the point and the left boundary is about 3e-7 m.
/Nicklas" defect closed blocker PostGIS 2.0.0 postgis 1.5.X fixed