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

[Martin Davis]

That's an interesting problem.

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?

It would be faster to simply scan all the edges of the polygon and find the
ones which intersect the line segment. Then you would have to determine the
inside/outside relationship of the portions of the line segment to see
which ones to keep.  This could potentially be done with a Point-In-Polygon
check on the midpoint of each edge.  I'm not sure if the C API exposes an
indexed version of that.

The pending OverlayNG will improve things somewhat, since it can optimize
cases where the envelope of the line is significantly smaller than the
envelope of the polygon.

But there's room for further improvement.  Reusing the index of the polygon
edges would be improve performance.  And given the simplicity of the single
line segment, there might be a way to further reduce the number of edges of
the polygon in a general way.

On Wed, Jun 24, 2020 at 11:55 PM Nyall Dawson <nyall.dawson at gmail.com>
wrote:

> Hi list!
>
> I've a situation where I've got ~millions of lines (each consisting of
> a single segment only) which I need to intersect against a complex
> polygon.
>
> Trying the naive way of multiple calls to GEOSIntersection_r gives
> predictably horrendous performance. Is there a better way I can
> approach this situation using the GEOS c api?
>
> Thanks,
> Nyall
> _______________________________________________
> 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/20200625/71c7ac9c/attachment.html>