[postgis-devel] [PostGIS] #852: The use of tolerance in function point_in_ring is not robust.

[PostGIS]

#852: The use of tolerance in function point_in_ring is not robust.
---------------------+------------------------------------------------------
 Reporter:  nicklas  |       Owner:  pramsey      
     Type:  defect   |      Status:  new          
 Priority:  medium   |   Milestone:  PostGIS 2.0.0
Component:  postgis  |     Version:  1.5.X        
 Keywords:           |  
---------------------+------------------------------------------------------
Description changed by nicklas:

Old description:

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

New description:

 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

--

-- 
Ticket URL: <http://trac.osgeo.org/postgis/ticket/852#comment:1>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.