<div dir="ltr"><div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Apr 17, 2019 at 4:38 AM Sandro Santilli <<a href="mailto:strk@kbt.io">strk@kbt.io</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
<br>
I don't think it should be ever accepted for a GEOS algorithm to<br>
possibly return invalid outputs. That's a big cornerstone we're<br>
building on. And was the main reason for me to look for a fix<br>
(callers assume GEOS always returns valid ouput!).<br></blockquote><div><br></div><div>Agreed.  Any other way madness lies. </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
An exception to this rule (always returning valid output) should<br>
always be carefully documented (one case was ClipByBox2d, which<br>
was recently also argued about if I recall correctly).<br></blockquote><div><br></div><div>Agreed, it might be ok to bend the rule in the following cases:</div><div>(a) there is not (yet) an implementation or algorithm that can guarantee valid output, but the function is still useful</div><div>(b) performance when providing invalid output is much better, and downstream use does not require validity.  (Although this should probably be exposed as a different function and documented as such) </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Can't we just always tell how much the perturbation was, by looking<br>
at the bounding box of the unioned geometries ? I thought that's what<br>
my change was doing but maybe it was just in planning and never went<br>
ahead doing it (your "iterative" approach?)<br></blockquote><div><br></div><div>That's the fix that I have now.  In the unionUsingEnvelopeIntersection function the envelope of the unioned geometries (in the overlap extent) is compared before and after, and any change triggers dropping back to computing the full union of both input geometries.  This handles the previous failure case. </div><div><br></div><div>Your previous fix was more conservative, and switched to the slow/safe logic if there were *any* polygons outside the overlap extent - which means it almost always was used, and thus the performance impact.  </div><div><br></div><div>(Kudos to you for finding the failing test case.  Was that just by chance, or would you be able to give the new potential fix a good workout?)</div><div><br></div><div>But... I think there is a slim possibility that:</div><div>(a) The envelope does not change</div><div>(b) The union moves a line segment slightly (due to snapping or simply by having a new node introduced)</div><div>(c) There is a geometry which lies just outside the overlap extent which is close enough to the changed segment that it is now intersected</div><div><br></div><div>It might be possible to come up with a synthetic test case to demonstrate this (perhaps using a fixed precision mode, which tends to highlight these kinds of issues).</div><div><br></div><div>One further test would be to compare all the line segments of the union which lie outside the overlap extent.  If they have not changed then there should be no risk of an intersection with the other outside polygons.  I think this should be significantly faster than doing the full union.  I'l try working that up and see what the impact is.</div></div></div></div>