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

[Rémi Cura]

Hey ,
First of all I'm not at all a specialist, and I don't have knowledge
nor intention to do something other than a workaround of one precise issue
(point/line intersection)

@Sandro : I agree it should be robust.
With the current st_intersects behavior it is possible if the slope (or its
inverse) is of finite size and not too long. I already wrote the functions,
but sadly in real world many lines are not concerned (ie not robust at
all!). Also the spacing of possible points increase with size of slope (in
digits), which is problematic. I thought about another possibility (see
after please).

@Paul : in fact we have no choice : we already use a precision model
(forced by double), only we don't really care to make it consistent.
pointA=point B is 17 digits precise, but as soon as there are
multiplication (or even worse: division!), we loose precision, without
taking care of it! Multiplication and division happens a lot in PostGIS !
Example : ` SELECT 1234567890.1234566::double precision*10.0 =
1234567890.1234567::double precision*10.0` yield TRUE, while it returns
false without x10.
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)!
Precision is not a choice except if we go CGAL like computation (Not the
point for PostGIS). But coherent precision is different from user defined
tolerance.

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!
For some function it is just okay to say it works up to a precision (like
the ST_OffSetCurve, robust up to 12 digits), but we can't do this for
predicates.
If predicates are guarantees to be true, each one can then add a custom
tolerance on top of it in plpgsql if needed.


the question "left or right of the line?" seems robust, so it guarantees
good behavior for higher order geometries (like intersects of line and
line). Same for the question "is inside of circle".

Yet the question "is on line" is not robust (as proven by current
ST_Intersects behavior).
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.

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.

Cheers,
Rémi C

NB1 : I rewrote some functions with 50 digits precision using postgres
"numeric" type for test purpose, but it is slow and not clever to rewrite
PostGIS in plpgsql !
NB2 : (Maybe an imperfect fix would be to re-declare every function to work
with not double but say long double (2 more bytes)? Yet would it guarantees
anything?.)





2013/11/7 Paul Ramsey <pramsey at cleverelephant.ca>

> I can certainly see the practical utility of a global tolerance value,
> since it would allow some more symmetric results, like
>
> PtC = LineA.Intersection(LineB)
> LineA.Intersects(PtC) == true
> LineB.Intersects(PtC) == true
>
> An expected euclidian result that occurs in almost no cases in our code.
>
> Of course a tolerance introduces different inconsistencies. Within a
> tolerance it's possible for
>
> LineA.Intersects(PtC) == true
> LineB.Intersects(PtC) == true
> Even when A is parallel to B and A != B.
>
> Not something which can happen in a true euclidian space, but
> something that can happen in our tolerance space.
>
> However, it's a concept that needs to reside at the very bottom of a
> geometry library, I don't see how we introduce it without irreparably
> shaking everything we've already built above.
>
> P.
>
>
> On Thu, Nov 7, 2013 at 8:44 AM, Sandro Santilli <strk at keybit.net> wrote:
> > On Thu, Nov 07, 2013 at 02:36:26PM +0100, Rémi Cura wrote:
> >> Hey,
> >> after some testing it appears that simply evaluating the = with
> precision
> >> in mind won't suffice.
> >>
> >> The core of the problem is that the determinant algorithm geos uses
> seems
> >> to be designed to robustly say left or right of a line, but not
> robustly on
> >> the line.
> >>
> >> So an idea may be to offset the line to the left and the right with the
> >> precision limit distance, and use the robust determinant to test if the
> >> point is right of the left and left of the right (between).
> >>
> >> Can I have some answers on this please? Is it doable, ?
> >
> > Sorry Remi, I think everything is possible, but it needs careful
> > thinking about consequence of changes. If the design it to be robust,
> > ading a toleranc would defeat the design, which isn't a sane thing
> > to do. Rather you might want another class to do things the way
> > you want them to be done.
> >
> > It's still not clear to me what the goal is, nor if the provision
> > of "Fixed Precision Model" helps already at reaching that goal.
> >
> > Are you trying to find a point that's guaranteed to be found on a
> > line by robust intersection finder ? My take is that it is
> > impossible unless the point you pick is a pre-existing vertex of
> > that line, and so the only way to do it is by also modifying the
> > line you want to snap to (ie: snap line to closest-point-on-line).
> >
> > --strk;
> > _______________________________________________
> > geos-devel mailing list
> > geos-devel at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/geos-devel
> _______________________________________________
> 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/18419186/attachment-0001.html>