[geos-devel] Possible speed improvement for overlay operations

Martin Davis mtnclimb at gmail.com
Sat Dec 1 14:06:02 PST 2018

I've also had some thoughts about being able to "prepare" geometries for
overlay.  At least for intersection and difference - it's less clear that
there is much of a use case for union and symdifference.

At the theoretical level certainly the self-noding could be cached, and
probably a reduction to a set of edges (Monotone Chains) as well.

This will require fairly major surgery to the codebase, however.   Ideally
the relate code can be split out (and hopefully reworked entirely), to
reduce the complexity.  There's also snap-rounding lurking in the

On Sat, Dec 1, 2018 at 8:15 AM Paul van der Linden <
paul.doskabouter at gmail.com> wrote:

> Ok, you're right. This was just a random example I used to see if I can
> spot some improvements and get a bit of a feel about the algorithms used.
> Ultimately I'm trying to figure out if the overlay-ops (especially
> intersection and union) can be reworked to use prepared geometries, but
> will make sure any tests I do involve real-world polygons
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181201/8e9bd312/attachment.html>

More information about the geos-devel mailing list