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

[Rémi Cura]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20131106/49ab664f/attachment.html>