[geos-devel] Progress on #837 - TopologyException in UnaryUnion

[Martin Davis]

On Sun, Apr 14, 2019 at 11:41 PM Sandro Santilli <strk at kbt.io> wrote:

> On Thu, Apr 11, 2019 at 01:06:51PM -0700, Martin Davis wrote:
> > Sandro, have you had any further thoughts on fixing the performance
> > regression caused by https://trac.osgeo.org/geos/ticket/837 ?
>
> There are a few TODO comments left in code, which do look aimed at
> improving performance. WARNING: there's some "environment" written
> instead of "envelope" (confused mind).
>
>
> 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.

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.

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.

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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20190415/a9a29828/attachment.html>