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

[Rémi Cura]

Hey,

In fact this is not even a grid,
representing any number with a float introduces an error that is not
"simple" (like regular), because the mantissa thing.
But I told you I'm not an expert at all.


You can exactly represent a line with a regular grid if you accept some
digits lose, by walking along line with smaller step and rounding result (I
do it in plpgsql with numeric(100,50)).

However the precision of computing the determinant (ie asking if point is
left,on,right) badly decrease when moving away from extremities.
This is why the code already iteratively cut the initial line into smaller
pieces until a trusted result is found.

Yep you are right for ST_DWithin. Even with this you still need a robust
intersect test (for area building for instance).

"Are you saying you have a point and a line and you can mathematically
prove that the point is on the line while GEOS says otherwise ?"
Yep, it's all the problem ! in fact according to geos (st_intersect) lines
have *very* few points, and some line have no points except extremities !
AS I said the
spacing of the point found bi st_intersects seems to follow the
prime decomposition of the slope (or 1/slope) of the segment. Problem
occurs when slope is not a finite number.


The whole problem comes from using exact math formula with inexact
computations means. This has been somehow tackled by using a "robust"
determinant sign, unfortunately this robustness is about saying left or
right.

:-) Thanks for the typs about DEBUG, I'll try to find this , and also the
place where postgres store it's log.

Many thanks for your patience with a beginner like me ^^

Cheers,
Rémi-C





2013/11/8 Sandro Santilli <strk at keybit.net>

> On Fri, Nov 08, 2013 at 09:58:37AM +0100, Rémi Cura wrote:
>
> > With current PostGIS, we can design an example with 2 lines being
> parallel,
> > but sharing an infinite number of points (http://hpics.li/58f194d ,
> where
> > square with 2 colors are shared)!
>
> The grid in your drawing is a "fixed" precision grid.
> The floating point precision grid is different, with precision reducing
> (cells augmenting) as you move away from the origin.
>
> > I'm not asking to rewrite PostGIS to permit an user specified tolerance,
> as
> > it would be very difficult and  not even clear on theoretical ground
> (whole
> > model of DE-9IM would be false, as in Paul example).
> > I just would like not to have false geometric result because the
> *numeric*
> > computation is wrong due to intrinsic double limitation. This is a
> computer
> > problem, not a PostGIS problem!
>
> By "false geometric results" you don't mean predicates here, right ?
> I mean, predicates are supposedly correct, while _constructive_ geometries
> suffer from the impossibility to represent the solution.
>
> > If predicates are guarantees to be true, each one can then add a custom
> > tolerance on top of it in plpgsql if needed.
>
> This is like ST_DWithin proceeding, right ?
>
> > Yet the question "is on line" is not robust (as proven by current
> > ST_Intersects behavior).
>
> Are you saying you have a point and a line and you can matematically
> prove that the point is on the line while GEOS says otherwise ?
>
> Or are you saying that math isn't appropriate for your more
> ground-anchored need ?
>
> > Maybe we could rewrite the question "is on line" using "left or right?",
> > taking  advantage of the known inherent double precision limit?
> > for example : http://hpics.li/ccf7b74
> > (we construct 2 points at double_precision/2 distance on perpendicular
> > line. If the 2 points have different side OR at least one is on line, we
> > say the point is on the line).
> > I'm not sure about this though because I don't know how the perpendicular
> > construction will react in bad cases, I'll test this this in few hours.
>
> Welcome. May I suggest you write testcases as you move forward ?
>
> > I'm trying things with geos, but i don't know basic thinks, like how to
> see
> > result of a printf in geos while executing sql query.
>
> See code wrapped in DEBUG macros.
> It usually prints to stderr and you find the output in postgresql logs.
>
> --strk;
> _______________________________________________
> 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/5d44caa8/attachment.html>