<div dir="ltr">Hey Nicklas,<div><br></div><div>I agree tolerance is even more complicated than precision. This is a completely different matter as when defining tolerance you go into fuzzy logic.</div><div><br></div><div>Here I'm just talking about all computing being "true" for the double precision world.</div>
<div><br></div><div>Finding a point on a line with double precision is not a problem, you can just do computing with better precision and round. </div><div>The problem is this point would be on the line (for a double world), but not on the line for st_intersects.</div>
<div><br></div><div>I found experimentally that using st_intersect, you have point spacing following the prime decomposition of the slope , which is very bad news in most of case.</div><div><br></div><div>The issue seems to be in robust_determinant computing, at a point, for a point M being on line P1 P2, </div>
<div>you must have</div><div>(x2-x1)*(ym-y1) =  (y2-y1)*(xm-x1)</div><div>by translating you can make x1=y1=0 with x2t and y2t being the x2 y2 translated.</div><div>x2t*ym  =  y2t * xm</div><div>Now the "equal" should be evaluated with precision in mind : </div>
<div>Ina typical case of a small slope : (slope = 0.001), we could take precision(x2t=1000m)= 10^(-15+4), precision(y2t=1m)= 10^(-15+1);</div><div><br></div><div>In this case the "=" should be evaluated with a 10^(-11) precision (is it sufficient? too much??)</div>
<div><br></div><div>Cheers,</div><div>Rémi-C</div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/11/6 Nicklas Avén <span dir="ltr"><<a href="mailto:nicklas.aven@jordogskog.no" target="_blank">nicklas.aven@jordogskog.no</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hallo<br>
<br>
Sorry, I was wrong. It was only the point in polygon test that is done<br>
in the PostGIS code, see file postgis/lwgeom_geos.c row 2602<br>
<br>
I thought I remembered that also point vs linestring was handled in the<br>
postgis code.<br>
<br>
I think it was last time we discussed this problem that I created the<br>
tolerance discussion wiki-page. But it is not very easy to handle<br>
correct.<br>
<br>
Maybe the point should be projected to the line and see if the projected<br>
point is equal to the unprojected point and then declare it<br>
intersecting. But I doubt that is very robust when comparing projected<br>
points from different machines on different platforms. We have seen<br>
differences in the last decimal before.<br>
<br>
<br>
Your idea, if I understand it right to find a point that actually is on<br>
the line and is representable with double precission coorinates can<br>
result in points far away from where it is supposed to be.<br>
<br>
I think that in most cases with not horizontal or vertical lines you<br>
will just get the vertex points and nothing else.<br>
<br>
Representable values on not horizontal or vertical lines is actually<br>
quite rare.<br>
<br>
Best Regards<br>
<span class="HOEnZb"><font color="#888888"><br>
Nicklas Avén<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
<br>
On Wed, 2013-11-06 at 11:15 +0100, Rémi Cura wrote:<br>
> Hey Nicklas,<br>
> thanks for your answer.<br>
><br>
> I'm simply trying to solve a problem in current ST_Intersects behavior<br>
> regarding a point and a line. IN most of the case, a point on a<br>
> line(to double limit precision) is not on the line for st_intersects !<br>
><br>
><br>
> it works as intended in very very few cases (ie, all the points that<br>
> intersects a line is a very sparse set and is not a line at all !).<br>
><br>
><br>
> Here is a simple illustration : <a href="http://hpics.li/c3485b5" target="_blank">http://hpics.li/c3485b5</a> represents a<br>
> line with max zoom : it is all the point that follow the line equation<br>
> and are rounded to the(16 or 17 digits)<br>
> <a href="http://hpics.li/f30aeb7" target="_blank">http://hpics.li/f30aeb7</a> now the big points represents the point that<br>
> are on the line for ST_Intersect, in a favorable case (bad case could<br>
> mean no points at all).<br>
><br>
><br>
><br>
> This is without speaking of custom precision model, ie working with<br>
> the postgis 'infinite' precision (double precision, 15 to 17 digits)<br>
><br>
><br>
> I tried several workaround (like several random walk along the line to<br>
> find a point that st_intersects like,<br>
> and also reverse engineer to find which points are seen on the line by<br>
> st_intersects (related to prime factorization of slope it appears) ).<br>
><br>
><br>
> The issue is there is a flaw in ST_Intersects and in bad cases there<br>
> is no workaround.<br>
><br>
><br>
> Could you elaborate about 'native' functions please?<br>
><br>
><br>
> Cheers,<br>
><br>
> Rémi-C<br>
><br>
><br>
><br>
><br>
> 2013/11/6 Nicklas Avén <<a href="mailto:nicklas.aven@jordogskog.no">nicklas.aven@jordogskog.no</a>><br>
>         I think postgis has native functions for st_intersects when at<br>
>         least one of the geometries is a point. And there is two paths<br>
>         in the code. One that prepares the "not point" geometry if it<br>
>         is to be used multiple times and one that doesn't.<br>
><br>
><br>
>         I do not get the idea do far. Is it a tolerance you are<br>
>         implementing?<br>
><br>
><br>
><br>
><br>
><br>
><br>
>         Best regards<br>
>         Nicklad<br>
><br>
><br>
>         Skickat från min Samsung Mobil<br>
><br>
><br>
><br>
>         -------- Originalmeddelande --------<br>
>         Från: Rémi Cura <<a href="mailto:remi.cura@gmail.com">remi.cura@gmail.com</a>><br>
>         Datum: 06-11-2013 8:59 (GMT+01:00)<br>
>         Till: PostGIS Development Discussion<br>
>         <<a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a>><br>
>         Rubrik: [postgis-devel] SNapPointToLine : GEOS : where is the<br>
>         code for st_intersects between line and point?<br>
><br>
><br>
>         Hey,<br>
>         I've been working on a ST_SnapPointToLine for the past week,<br>
>         by reverse engineering when points are considered to be on<br>
>         line by st_intersect.<br>
><br>
><br>
>         The (classic) problem is purely a numerical issue, and I<br>
>         suspect a problem in design of st_intersects.<br>
><br>
><br>
><br>
><br>
>         So far my solution doesn't work for all line, can someone<br>
>         please point me in the right direction in GEOS so I can see if<br>
>         something can be improved regarding precision.<br>
><br>
><br>
>         I know where the API is, but I'm looking for the exact part<br>
>         that decide if a point and a line intersects.<br>
><br>
><br>
>         Cheers,<br>
><br>
><br>
>         Rémi-C<br>
><br>
>         _______________________________________________<br>
>         postgis-devel mailing list<br>
>         <a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br>
>         <a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-devel</a><br>
><br>
><br>
<br>
<br>
</div></div></blockquote></div><br></div>