[geos-devel] millions of lines intersection against single polygon

[Martin Davis]

On Thu, Jun 25, 2020 at 3:47 PM Nyall Dawson <nyall.dawson at gmail.com> wrote:

> > Are the line segments in fully general position relative to the polygon?
> I.e. they range from just touching it to fully crossing it, and may
> intersect the boundary multiple times?
>
> They are actually "rays", possibly extending to infinity. But for the
> simplicity I've restricted them to fall inside the polygon's bounding
> box, since I only care about portion of the line within the polygon.
> So they:
> 1. Will always intersect at least twice with the polygon exterior
> 2. May possibly coincide exactly with one or more exterior/interior
> segments
>
> I've been thinking about this a bit more, and realized that lines being
coincident with polygon segments makes this a bit harder.  What's needed is
a simple "graph" structure along the line, which can determine which
portions of the line are inside, outside or coincident.  Then the overlay
result can be extracted from that.  There probably also needs to be a
little bit of snapping done, in case intersections lie very close together
(in which case they might reverse position along the line, causing
mislabelled topology).

Also, rather than a linear scan of the polygon edges a spatial index can be
used on the polygon (which can be reused).

All this suggests the possiblity of a new "OverlayPolygonLine" algorithm.
Even given the above, it will be quite a bit simpler than full overlay, and
should be a lot faster too.  I am planning to prototype this in JTS to see
how it works out.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20200625/7ad07b6d/attachment.html>