[geos-devel] [postgis-devel] SNapPointToLine : GEOS : where is the code for st_intersects between line and point?
Martin Davis
mtnclimb at telus.net
Thu Nov 7 21:51:01 PST 2013
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 <mailto: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 <mailto: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
> <mailto: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 <mailto:remi.cura at gmail.com>>
> Datum: 06-11-2013 8:59 (GMT+01:00)
> Till: PostGIS Development Discussion
> <postgis-devel at lists.osgeo.org
> <mailto: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 <mailto:postgis-devel at lists.osgeo.org>
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel
>
>
>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>
>
> No virus found in this message.
> Checked by AVG - www.avg.com <http://www.avg.com>
> Version: 2013.0.3426 / Virus Database: 3222/6813 - Release Date: 11/06/13
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20131107/d50c074d/attachment.html>
More information about the geos-devel
mailing list