[geos-devel] [postgis-devel] SNapPointToLine : GEOS : where is the code for st_intersects between line and point?

Fri Nov 8 01:09:55 PST 2013

Hey,
sorry this mail thread has been split :-/

As I said I don't have knowledge nor intention to modify in depth PostGIS
general tolerance policy.
Numeric precision in computing is a very serious research field, and
PostGIS can't hope to have all the latest cool stuff from it.

However I strongly share your feeling that when working with real
geographical imprecise data (almost the case) we need user-specified
tolerance. I think we can somehow handle this if  base functions (like
ST_Intersects) are working properly.

There even is a wiki page about tolerance, it appears to be a recurrent
issue.

As a matter of fact I tried to add tolerance to
"RobustDeterminant::signOfDet2x2" , but I understood it was pointless
because the problem of point being on line is chaotic.
So there is no way to solve this simply replacing "=" by
"difference<a_tolerance". (I tried it in geo sand with plain plpgsql).

As I said in other mail, maybe we could work around by transforming the "is
on line" to "is left/right"?

Cheers,

Rémi-C

2013/11/8 Martin Davis <mtnclimb at telus.net>

>  Another aspect to consider is that the "pixel size" in DP is not a fixed
> value.  It gets smaller closer to the origin.
>
> So how would you deal with this fact?  Use the pixel size of the largest
> coordinate of the line segment? Of the geometry?  Would this introduce
> inconsistencies across geometries?
>
> My gut feel about this is that if this kind of "coherent behaviour" is
> desired then the API client (user) should be required to specify the
> tolerance they care about.  This is how Oracle Spatial works (more or
> less).  This has a wider advantage in that it is then possible to guarantee
> that geometries constructed according to the tolerance model are guaranteed
> to be consistent in that model.
>
> I *think* that it would be of only medium difficulty to add a tolerance to
> the predicate computation.  For overlay operations this is harder, since it
> would require snap-rounding to be used.  There would probably be
> performance impacts in both, however.
>
>
> On 11/6/2013 4:41 AM, Rémi Cura wrote:
>
> Hey Sandro =) ,
> thanks for the answer and the suggestion ( switching to geos-devel)
> *(Hey geos list, please see the message history in reverse order)*
>
> I'm not looking for infinite precision, just *coherent* double precision.
>
> Using double precision to represent a line/point gives you a
> representation like pixels in images, where size of pixel in x is min
> precision in (that is a round to 15 to17 digits) (same in y). This is not
> an issue (for me).
>
>  This issue is not about geometry being approximated (rounded), but about
> st_intersects miss-computing with this rounded geom.
>
>  Currently st_intersects computing for a point and a line is false, more
> exactly the computing seems to be more precise than the geometry, thus
> giving false answer.
> I'm not sure about this, and i don't know either what kind of change could
> solve this problem.
>
>  Maybe the computing of "robust determinant" needs to be relaxed a bit to
> output 0 in close cases.
>
>
>  I can give you example of points being exactly on the double precision
> grid (ie 17 digits in each coordinate),  exactly on the theoretical line
> (up to 10^-30), and yet rejected by st_intersects.
>
>
>
>  Cheers,
> Rémi-C
>
>
>
> 2013/11/6 Sandro Santilli <strk at keybit.net>
>
>> On Wed, Nov 06, 2013 at 11:15:12AM +0100, Rémi Cura wrote:
>>
>> > This is without speaking of custom precision model, ie working with the
>> > postgis 'infinite' precision (double precision, 15 to 17 digits)
>>
>>  Double precision is not 'infinite'.
>> Maybe CGAL would give you a closer approximation, but GEOS doesn't support
>> the CGAL-like arbitrary precision.
>>
>> You might want to subscribe to geos-devel and start a thread there if
>> you intend to work on that side of the architecture.
>>
>> --strk;
>>  _______________________________________________
>> postgis-devel mailing list
>> postgis-devel at lists.osgeo.org
>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel
>>
>
>  Hey Nicklas,
> thanks for your answer.
>
> I'm simply trying to solve a problem in current ST_Intersects behavior
> regarding a point and a line. IN most of the case, a point on a line(to
> double limit precision) is not on the line for st_intersects !
>
>  it works as intended in very very few cases (ie, all the points that
> intersects a line is a very sparse set and is not a line at all !).
>
>  Here is a simple illustration : http://hpics.li/c3485b5 represents a
> line with max zoom : it is all the point that follow the line equation and
> are rounded to the(16 or 17 digits)
> http://hpics.li/f30aeb7 now the big points represents the point that are
> on the line for ST_Intersect, in a favorable case (bad case could mean no
> points at all).
>
>  This is without speaking of custom precision model, ie working with the
> postgis 'infinite' precision (double precision, 15 to 17 digits)
>
>  I tried several workaround (like several random walk along the line to
> find a point that st_intersects like,
> and also reverse engineer to find which points are seen on the line by
> st_intersects (related to prime factorization of slope it appears) ).
>
>  The issue is there is a flaw in ST_Intersects and in bad cases there is
> no workaround.
>
>  Could you elaborate about 'native' functions please?
>
>  Cheers,
>
> Rémi-C
>
>
>
> 2013/11/6 Nicklas Avén <nicklas.aven at jordogskog.no>
>
>>   I think postgis has native functions for st_intersects when at least
>> one of the geometries is a point. And there is two paths in the code. One
>> that prepares the "not point" geometry if it is to be used multiple times
>> and one that doesn't.
>>
>>  I do not get the idea do far. Is it a tolerance you are implementing?
>>
>>
>>
>>  Best regards
>> Nicklad
>>
>>   Skickat från min Samsung Mobil
>>
>>
>>
>> -------- Originalmeddelande --------
>> Från: Rémi Cura <remi.cura at gmail.com>
>> Datum: 06-11-2013 8:59 (GMT+01:00)
>> Till: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
>> Rubrik: [postgis-devel] SNapPointToLine : GEOS : where is the code for
>> st_intersects between line and point?
>>
>>
>> Hey,
>> I've been working on a ST_SnapPointToLine for the past week,
>> by reverse engineering when points are considered to be on line by
>> st_intersect.
>>
>>  The (classic) problem is purely a numerical issue, and I suspect a
>> problem in design of st_intersects.
>>
>>
>>  So far my solution doesn't work for all line, can someone please point
>> me in the right direction in GEOS so I can see if something can be improved
>> regarding precision.
>>
>>  I know where the API is, but I'm looking for the exact part that decide
>> if a point and a line intersects.
>>
>>  Cheers,
>>
>>  Rémi-C
>>
>>  _______________________________________________
>> postgis-devel mailing list
>> postgis-devel at lists.osgeo.org
>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel
>
>
>
>
>
> _______________________________________________
> geos-devel mailing listgeos-devel at lists.osgeo.orghttp://lists.osgeo.org/mailman/listinfo/geos-devel
>
>
>
> No virus found in this message.
> Checked by AVG - www.avg.com
> Version: 2013.0.3426 / Virus Database: 3222/6813 - Release Date: 11/06/13
>
>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20131108/a8f5c178/attachment.html>