<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Apr 14, 2019 at 11:41 PM 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">On Thu, Apr 11, 2019 at 01:06:51PM -0700, Martin Davis wrote:<br>
> Sandro, have you had any further thoughts on fixing the performance<br>
> regression caused by <a href="https://trac.osgeo.org/geos/ticket/837" rel="noreferrer" target="_blank">https://trac.osgeo.org/geos/ticket/837</a> ?<br>
<br>
There are a few TODO comments left in code, which do look aimed at<br>
improving performance. WARNING: there's some "environment" written<br>
instead of "envelope" (confused mind).<br>
<br><br></blockquote><div>Yes, I saw those, and they make sense as being a safe optimization.  Not sure they will deliver much of a performance boost - but need to code the iterative approach up to be sure. </div><div><br></div><div>I do have a slightly changed patch which runs all current test cases correctly, and provides similar performance to the original implementation.  The only catch is that I think it is theoretically not 100% safe, since it still leaves a small opening for having geometry perturbed by the union causing overlaps and thus invalid output.  This should be very rare though.  I will push a PR soon with this fix.  Perhaps it's possible to give it a more thorough stress test and if it passes switch to using it.</div><div><br></div><div>Ultimately I think the ideal approach is going to be abandoning CascadedUnion and switch to a full union algorithm (which will essentially be the same as running buffer(0).  This should have very good performance.  </div><div><br></div><div>It's also possible that there is a further optimization possible for situations with many disjoint polygons (as in both of the provided regression cases). This would depend on being able to carry out an interesects test faster than a full union computation, which seems possible (something similar is already recommended as an optimization for intersection).   </div></div></div>