[geos-devel] CoverageUnion

[Martin Davis]

On Tue, Apr 18, 2023 at 5:24 PM Daniel Baston <dbaston at gmail.com> wrote:

> I noticed that the OverlayNG coverage union returns an empty polygon if
> the inputs do not form a coverage, whereas the older algorithm produces an
> error. I think it would be a good idea to apply an area post-check to the
> NG version so that we retain the error.
>

Seems reasonable.


> I have also noticed cases (TIGER county boundaries) where the NG algorithm
> takes about 2x as long as the old algorithm but performs better than the
> old algorithm if the inputs are pre-sorted (as they are in the old
> algorithm). Maybe the same sorting should be added to the NG version.
>

Any theories about why sorting improves the performance?

Perhaps it's because of the BoundaryChainNoder, which adds segments to an
std::unordered_set<Segment, Segment::HashCode>.  Segments are removed from
the set when duplicates occur.  If the segments inserted have spatial
coherency, that would tend to reduce the dynamic size of the unorderedset,
which perhaps improves performance?

I also note that using the OverlayNG logic for CoverageUnion is a bit of
overkill, since the topology of the unioned coverage is much simpler than a
general topological situation.  At some point it would be good to see if a
dedicated implementation for building the union coverage topology would be
faster.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20230418/903610cf/attachment.htm>