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

[Nyall Dawson]

On Fri, 26 Jun 2020 at 01:57, Martin Davis <mtnclimb at gmail.com> wrote:
>
> 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?

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

> It would be faster to simply scan all the edges of the polygon and find the ones which intersect the line segment.

Thanks -- this is what I was suspecting, and somewhat fearful of! I
was hoping to avoid as much downstream logic as possible...

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

GEOSPreparedIntersects_r will handle that nicely!

Nyall

>
> 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
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel