<div dir="ltr">Hey,<div>sorry this mail thread has been split :-/</div><div><br></div><div>As I said I don't have knowledge nor intention to modify in depth PostGIS general tolerance policy.</div><div>Numeric precision in computing is a very serious research field, and PostGIS can't hope to have all the latest cool stuff from it.</div>
<div><br></div><div>However I strongly share your feeling that when working with real geographical imprecise data (almost the case) we need user-specified tolerance. I think we can somehow handle this if base functions (like ST_Intersects) are working properly.</div>
<div><br></div><div>There even is a wiki page about tolerance, it appears to be a recurrent issue.</div><div><br></div><div>As a matter of fact I tried to add tolerance to "RobustDeterminant::signOfDet2x2" , but I understood it was pointless because the problem of point being on line is chaotic.</div>
<div>So there is no way to solve this simply replacing "=" by "difference<a_tolerance". (I tried it in geo sand with plain plpgsql).</div><div><br></div><div>As I said in other mail, maybe we could work around by transforming the "is on line" to "is left/right"?</div>
<div><br></div><div>Cheers,</div><div><br>Rémi-C</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/11/8 Martin Davis <span dir="ltr"><<a href="mailto:mtnclimb@telus.net" target="_blank">mtnclimb@telus.net</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
Another aspect to consider is that the "pixel size" in DP is not a
fixed value. It gets smaller closer to the origin.<br>
<br>
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?<br>
<br>
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.<br>
<br>
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.<div><div class="h5"><br>
<br>
<div>On 11/6/2013 4:41 AM, Rémi Cura wrote:<br>
</div>
</div></div><blockquote type="cite"><div><div class="h5">
<div dir="ltr">Hey Sandro =) ,
<div>thanks for the answer and the suggestion ( switching to
geos-devel) </div>
<div><b>(Hey geos list, please see the message history in
reverse order)</b><br>
<br>
I'm not looking for infinite precision, just *coherent* double
precision.
<div>
<br>
<div>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).</div>
<div><br>
</div>
<div>This issue is not about geometry being approximated
(rounded), but about st_intersects miss-computing with
this rounded geom. </div>
<div><br>
</div>
<div>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.</div>
<div>I'm not sure about this, and i don't know either what
kind of change could solve this problem.</div>
<div><br>
</div>
<div>Maybe the computing of "robust determinant" needs to be
relaxed a bit to output 0 in close cases.</div>
<div><br>
</div>
<div><br>
</div>
<div>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.</div>
<div>
<br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>Cheers,</div>
<div>Rémi-C </div>
<div><br>
</div>
</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">2013/11/6 Sandro Santilli <span dir="ltr"><<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a>></span><br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div>On Wed, Nov 06, 2013 at 11:15:12AM +0100,
Rémi Cura wrote:<br>
<br>
> This is without speaking of custom precision model,
ie working with the<br>
> postgis 'infinite' precision (double precision, 15
to 17 digits)<br>
<br>
</div>
Double precision is not 'infinite'.<br>
Maybe CGAL would give you a closer approximation, but GEOS
doesn't support<br>
the CGAL-like arbitrary precision.<br>
<br>
You might want to subscribe to geos-devel and start a
thread there if<br>
you intend to work on that side of the architecture.<br>
<br>
--strk;<br>
<div>
<div>_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">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></div>
</div>
</blockquote>
<div><br>
</div>
<div dir="ltr" style="font-family:arial,sans-serif;font-size:12.800000190734863px">
Hey Nicklas,
<div>thanks for your answer.<br>
<br>
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 !</div>
<div><br>
</div>
<div>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 !).</div>
<div><br>
</div>
<div>Here is a simple illustration : <a href="http://hpics.li/c3485b5" target="_blank">http://hpics.li/c3485b5</a> 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)</div>
<div><a href="http://hpics.li/f30aeb7" target="_blank">http://hpics.li/f30aeb7</a> 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).<br>
</div>
<div><br>
</div>
<div>This is without speaking of custom precision model,
ie working with the postgis 'infinite' precision (double
precision, 15 to 17 digits)</div>
<div><br>
</div>
<div>I tried several workaround (like several random walk
along the line to find a point that st_intersects like, </div>
<div>and also reverse engineer to find which points are
seen on the line by st_intersects (related to prime
factorization of slope it appears) ). </div>
<div><br>
</div>
<div>The issue is there is a flaw in ST_Intersects and in
bad cases there is no workaround.</div>
<div><br>
</div>
<div>Could you elaborate about 'native' functions please?</div>
<div><br>
</div>
<div>Cheers,</div>
<div><br>
Rémi-C</div>
<div><br>
</div>
</div>
<div class="gmail_extra" style="font-family:arial,sans-serif;font-size:12.800000190734863px">
<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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div>
<div>
<div>
<div>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.</div>
<div><br>
</div>
<div>I do not get the idea do far. Is it a
tolerance you are implementing? </div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>Best regards</div>
<div>Nicklad</div>
<div><br>
</div>
<div>
<div style="font-size:9.600000381469727px;color:rgb(87,87,87)">
Skickat från min Samsung Mobil</div>
</div>
<br>
<br>
<br>
-------- Originalmeddelande --------<br>
Från: Rémi Cura <<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>> <br>
Datum: 06-11-2013 8:59 (GMT+01:00) <br>
Till: PostGIS Development Discussion <<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a>> <br>
Rubrik: [postgis-devel] SNapPointToLine : GEOS :
where is the code for st_intersects between line
and point? <br>
<div><br>
<br>
<div dir="ltr">Hey,
<div>I've been working on a
ST_SnapPointToLine for the past week,</div>
<div>by reverse engineering when points are
considered to be on line by st_intersect.</div>
<div><br>
</div>
<div>The (classic) problem is purely a
numerical issue, and I suspect a problem
in design of st_intersects.</div>
<div><br>
</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>I know where the API is, but I'm
looking for the exact part that decide if
a point and a line intersects.</div>
<div><br>
</div>
<div>Cheers,</div>
<div><br>
</div>
<div>Rémi-C</div>
</div>
</div>
</div>
<br>
</div>
</div>
_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">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></blockquote>
</div>
</div>
<div> </div>
</div>
<br>
</div>
</div>
<br>
<fieldset></fieldset>
<br>
</div></div><pre>_______________________________________________
geos-devel mailing list
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a>
<a href="http://lists.osgeo.org/mailman/listinfo/geos-devel" target="_blank">http://lists.osgeo.org/mailman/listinfo/geos-devel</a></pre>
<br>
<fieldset></fieldset>
<br>
<p color="#000000" align="left">No virus
found in this message.<br>
Checked by AVG - <a href="http://www.avg.com" target="_blank">www.avg.com</a><br>
Version: 2013.0.3426 / Virus Database: 3222/6813 - Release Date:
11/06/13</p>
</blockquote>
<br>
</div>
<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></blockquote></div><br></div>