<div dir="ltr"><div><div>Hey list, Sandro, Paul. <br>Up ?<br></div><br><br></div><div>Short summary :<b> Allowing to split a line by a point </b>!<br></div><div>proposed change :<br>IN /postgis/liblwgeom/lwgeom_geos_split.c:190:<br>
</div><div>change <br>"if ( dist > 0) /* TODO: accept a tolerance ? */"<br></div><div>by <br><div><div>//@TOTEST @CHECK change by Remi-C : adding a small tolerance</div><div><span style="white-space:pre-wrap"> </span>vstol = ptarray_length_2d(lwline_in->points) / 1e14; //note : 1e12 would be better<br>
</div><div><span style="white-space:pre-wrap"> </span>if ( dist > vstol ) /* TODO: accept a tolerance ? */<br><br></div><div>This modification would allow to split line by points in most cases (see test sql files in previous mail).<br>
<br></div><div>This modification allows to take care of a known numeric issue.<br><br></div><div>Cheers,<br><br>Rémi-C<br></div><div><br><br></div>
</div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013-12-02 11:50 GMT+01:00 Rémi Cura <span dir="ltr"><<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>Hey Paul ,<br>thanks for the insight !<br><br>I've thought about this, and this is true that this may be a parameter.<br>
<br>We have a given number of digits (15 to 17), and some are spent on coordinates (I'd say 10 at most), so some remain to do precise computation.<br>
The problem is that the error we can allow (the epsilon) should depend on this. For example, if I use 10 digits, only 5 remains, and the error should be 5 digits.<br>But if use 5 digits for coordinates, I could be much more precise and allow 10 digits to error.<br>
Maybe the (advanced) user could change this.<br><br>Here is what I propose, and what I'll enforce for my work (the analogy is just for example):<br>any point/line/poly should be precise up to 10 digits (2 points could be separated by 1000 km + 1 mm ).<br>
Any function working on geom should give good answer on 10 digits geom.<br><br>More than this, geometry are equal except during computing (so we can use full digits during computing ).<br><br>Remaining digits should be used to epsilon and like so as to give best possible answers.<br>
<br><br></div>Please find the required test : <br></div>the sql querry should return (true,true)<br></div><div style="margin-left:40px">1.) the first true means that on 100 000 random line and random point on line, all line have been split in 2.<br>
2.) the second true means that for this random lines, none was split by a point farther than epsilon from line.<br></div></div><div><div><div><div>All testing are done on point/line having at most 10 digits coordinates<br>
<br></div><div>Please note that for 1.) I didn't check than splitting occured at the right place, because I'm not testing split computing but chen it computes.<br></div><div><br>This is base code where you can chose number of digits in coordinates, epsilon, number of tests to have<br>
</div><div>The random is seeded so test can be reproduced.<br></div><div>This could be reused to test more thoroughly other functions, and could be improved (lines are always segments, orientation not random).<br><br></div>
<div>I also have a function which for a given line A and point P, gives the closest point to P on A with a given number of digits. A bit like a ST_SNapToGrid, but for point on line (in concept).<br></div><div><br>Cheers,<br>
Rémi-C<div><br></div>
</div></div></div></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">2013/11/30 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>On Fri, Nov 29, 2013 at 09:26:07AM -0800, Paul Ramsey wrote:<br>
> Just to be a loose cannon in general: we have hard-wired tolerances<br>
> all over the code base, just grep for EPSILON and see what pops out.<br>
> We've hardly been ascetics about abusing tolerances where it suits our<br>
> purposes. The proposal for a "split that 'works'" fits in with our<br>
> general historical approach to tolerances that make things "work".<br>
<br>
</div>Yeah, and I'll confess: I've injected some of that myself too,<br>
recently. See r10973 ...<br>
<br>
What can I say Remi, give me a testcase and let's add to the mud :)<br>
<br>
--strk(I wanna be Anarchy);<br>
<div><div><br>
><br>
> P.<br>
><br>
> On Fri, Nov 29, 2013 at 5:18 AM, Sandro Santilli <<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a>> wrote:<br>
> > On Fri, Nov 29, 2013 at 10:48:54AM +0100, Rémi Cura wrote:<br>
> >> ST_Split(line,point) is currently broken.<br>
> >> This is quite a neutral statement, because given a random point on a random<br>
> >> line, split won't do anything (p_correct_answer<1/10k )!<br>
> >><br>
> >> The only work around I can think about are<br>
> >> _ snap the line to the point : it implies moving the line, which is not an<br>
> >> option if you do it several times with different points, and is more<br>
> >> abstractly a very bad idea<br>
> ><br>
> > This is what you'd be doing anyway by implementing a tolerance.<br>
> > That is, the line would be moved anyway.<br>
> ><br>
> >> _ change the point to a very small line in the perpendicular direction of<br>
> >> the line we want to split, then use split(line,line). Again not a very good<br>
> >> option because you would possibiliy split the line in more than one point<br>
> >> (and anyway split(line,line) has also precision issues).<br>
> ><br>
> > Still this is a legit options.<br>
> ><br>
> >> I understand PostGIS is a big project and we have to be conservative,<br>
> >> that is "we don't break a fine function with changes bringing unknown<br>
> >> consequences for unproven benefits",<br>
> >> but this function is broken, and we could change it to a function working<br>
> >> most of the time !<br>
> ><br>
> > Yes, we could change it by accepting a tolerance value.<br>
> > What's wrong with that ?<br>
> ><br>
> >> *Pros of this change :*<br>
> >><br>
> >> _a line will be split by a point correctly (p_error < 10^6)<br>
> >> _no heavy changes in code or methods<br>
> >><br>
> >> *Cons of this change :*<br>
> >><br>
> >> _the line would be split by any points close enough (lengthofline/10^12).<br>
> >> (that is all points less than 10 micro meters away from a line 1000 km long<br>
> >> !).<br>
> ><br>
> > PostGIS doesn't deal with unit, so you don't know if those are<br>
> > micro meters or micro peta meters.<br>
> > You might be splitting a milli meter line by a point...<br>
> ><br>
> > All I'm saying is I'd like precision/tolerance to be _EXPLICIT_.<br>
> > Particularely important when you're about to run a _set_ of operations<br>
> > and you want them to be _consistent_ as per precision.<br>
> ><br>
> >> *I would also like adding ST_Split(geom,geom,tolerance).*<br>
> >> In fact it could be an easy wrapper around ST_Split(geom,geom) if this<br>
> >> function was working. (something like: if the point is DWithin, split the<br>
> >> closest part of the line)<br>
> ><br>
> > Please go ahead. Such a function would be accepted.<br>
> ><br>
> > NOTE: TopoGeo_addPoint does take a tolerane, and does use ST_Split after<br>
> > snapping the line to a DWithin point to implement it.<br>
> > Haing it available natively in C would speed that up.<br>
> ><br>
> > --strk;<br>
> ><br>
> > () ASCII ribbon campaign - against html e-mail<br>
> > /\ <a href="http://www.asciiribbon.org" target="_blank">http://www.asciiribbon.org</a> - against proprietary attachments<br>
> > _______________________________________________<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><br>
> _______________________________________________<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><br>
<br>
</div></div>--<br>
<div><div><br>
() ASCII ribbon campaign - against html e-mail<br>
/\ <a href="http://www.asciiribbon.org" target="_blank">http://www.asciiribbon.org</a> - against proprietary attachments<br>
_______________________________________________<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><br>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>