BUG #14971: point outside polygon is reported inside polygon

From: postgresql(at)eric(dot)brechemier(dot)name
To: pgsql-bugs(at)postgresql(dot)org
Cc: postgresql(at)eric(dot)brechemier(dot)name
Subject: BUG #14971: point outside polygon is reported inside polygon
Date: 2017-12-13 17:28:06
Message-ID: 20171213172806.20142.73638@wrigleys.postgresql.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-bugs

The following bug has been logged on the website:

Bug reference: 14971
Logged by: Eric Bréchemier
Email address: postgresql(at)eric(dot)brechemier(dot)name
PostgreSQL version: 9.5.0
Operating system: macos
Description:

Using GPS positions with 5 decimals, which corresponds to an accuracy of
approximately 1 meter, we noticed that the operators '<@' and '@>' which
check whether a polygon contains a given point sometimes give an incorrect
result.

Here is a minimum example which shows the issue:

select '((30E-5,-15E-5),(60E-5,90E-5),(-30E-5,150E-5))'::polygon @>
point(0,0);

This query returns TRUE instead of FALSE.

The same query, scaled to integer values correctly returns FALSE:

select '((30,-15),(60,90),(-30,150))'::polygon @> point(0,0);

I simulated the algorithm used in the implementation step by step in a
spreadsheet, and found that the discrepancy occurs in the computation of
FPzero(z) called by lseg_crossing() called by point_inside() called by
poly_contain_pt().

With the floating point values, z becomes smaller than the EPSILON of
1.0E-6, which is not the case with integer values.

Changing EPSILON to a lower value solves the issue. It appears that the
current value of EPSILON was chosen with single precision floating point
values in mind rather than the double precision values stored in points and
polygons.

Browse pgsql-bugs by date

  From Date Subject
Next Message Tom Lane 2017-12-13 17:36:41 Re: Build error on Windows 10 of version 9.5.10 using Visual Studio 2015
Previous Message Kenneth Reister 2017-12-13 16:51:28 Build error on Windows 10 of version 9.5.10 using Visual Studio 2015