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

[Martin Davis]

On Wed, Apr 17, 2019 at 4:38 AM Sandro Santilli <strk at kbt.io> wrote:

>
>
> I don't think it should be ever accepted for a GEOS algorithm to
> possibly return invalid outputs. That's a big cornerstone we're
> building on. And was the main reason for me to look for a fix
> (callers assume GEOS always returns valid ouput!).
>

Agreed.  Any other way madness lies.

>
> An exception to this rule (always returning valid output) should
> always be carefully documented (one case was ClipByBox2d, which
> was recently also argued about if I recall correctly).
>

Agreed, it might be ok to bend the rule in the following cases:
(a) there is not (yet) an implementation or algorithm that can guarantee
valid output, but the function is still useful
(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)

>
> Can't we just always tell how much the perturbation was, by looking
> at the bounding box of the unioned geometries ? I thought that's what
> my change was doing but maybe it was just in planning and never went
> ahead doing it (your "iterative" approach?)
>

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.

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.

(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?)

But... I think there is a slim possibility that:
(a) The envelope does not change
(b) The union moves a line segment slightly (due to snapping or simply by
having a new node introduced)
(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

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).

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