<div dir="ltr">Hey ,<div>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)</div><div><div><br>
</div><div>@Sandro : I agree it should be robust.<br>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).</div>
<div><br></div><div>@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 !</div>
<div>Example : `<span class="" style="white-space:pre"> </span>SELECT 1234567890.1234566::double precision*10.0 = 1234567890.1234567::double precision*10.0` yield TRUE, while it returns false without x10.</div><div>With current PostGIS, we can design an example with 2 lines being parallel, but sharing an infinite number of points (<a href="http://hpics.li/58f194d">http://hpics.li/58f194d</a> , where square with 2 colors are shared)! </div>
<div>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.</div><div><br></div><div>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). </div>
<div>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!</div><div>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.</div>
<div>If predicates are guarantees to be true, each one can then add a custom tolerance on top of it in plpgsql if needed.</div><div><br></div><div><br></div><div>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". </div>
<div><br></div><div>Yet the question "is on line" is not robust (as proven by current ST_Intersects behavior).<br></div><div>Maybe we could rewrite the question "is on line" using "left or right?", taking  advantage of the known inherent double precision limit?</div>
<div>for example : <a href="http://hpics.li/ccf7b74">http://hpics.li/ccf7b74</a> </div><div>(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).<br>
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.</div><div><br></div><div>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.</div>
<div><br></div><div>Cheers,</div><div>Rémi C</div><div><br></div><div>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 !</div>
<div>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?.)</div><div><br></div><div><br></div><div><br></div></div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/11/7 Paul Ramsey <span dir="ltr"><<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I can certainly see the practical utility of a global tolerance value,<br>
since it would allow some more symmetric results, like<br>
<br>
PtC = LineA.Intersection(LineB)<br>
LineA.Intersects(PtC) == true<br>
LineB.Intersects(PtC) == true<br>
<br>
An expected euclidian result that occurs in almost no cases in our code.<br>
<br>
Of course a tolerance introduces different inconsistencies. Within a<br>
tolerance it's possible for<br>
<br>
LineA.Intersects(PtC) == true<br>
LineB.Intersects(PtC) == true<br>
Even when A is parallel to B and A != B.<br>
<br>
Not something which can happen in a true euclidian space, but<br>
something that can happen in our tolerance space.<br>
<br>
However, it's a concept that needs to reside at the very bottom of a<br>
geometry library, I don't see how we introduce it without irreparably<br>
shaking everything we've already built above.<br>
<span class="HOEnZb"><font color="#888888"><br>
P.<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
On Thu, Nov 7, 2013 at 8:44 AM, Sandro Santilli <<a href="mailto:strk@keybit.net">strk@keybit.net</a>> wrote:<br>
> On Thu, Nov 07, 2013 at 02:36:26PM +0100, Rémi Cura wrote:<br>
>> Hey,<br>
>> after some testing it appears that simply evaluating the = with precision<br>
>> in mind won't suffice.<br>
>><br>
>> The core of the problem is that the determinant algorithm geos uses seems<br>
>> to be designed to robustly say left or right of a line, but not robustly on<br>
>> the line.<br>
>><br>
>> So an idea may be to offset the line to the left and the right with the<br>
>> precision limit distance, and use the robust determinant to test if the<br>
>> point is right of the left and left of the right (between).<br>
>><br>
>> Can I have some answers on this please? Is it doable, ?<br>
><br>
> Sorry Remi, I think everything is possible, but it needs careful<br>
> thinking about consequence of changes. If the design it to be robust,<br>
> ading a toleranc would defeat the design, which isn't a sane thing<br>
> to do. Rather you might want another class to do things the way<br>
> you want them to be done.<br>
><br>
> It's still not clear to me what the goal is, nor if the provision<br>
> of "Fixed Precision Model" helps already at reaching that goal.<br>
><br>
> Are you trying to find a point that's guaranteed to be found on a<br>
> line by robust intersection finder ? My take is that it is<br>
> impossible unless the point you pick is a pre-existing vertex of<br>
> that line, and so the only way to do it is by also modifying the<br>
> line you want to snap to (ie: snap line to closest-point-on-line).<br>
><br>
> --strk;<br>
> _______________________________________________<br>
> geos-devel mailing list<br>
> <a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a><br>
> <a href="http://lists.osgeo.org/mailman/listinfo/geos-devel" target="_blank">http://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org">geos-devel@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/geos-devel" target="_blank">http://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
</div></div></blockquote></div><br></div>