<div dir="ltr">That's an interesting problem.<div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jun 24, 2020 at 11:55 PM Nyall Dawson <<a href="mailto:nyall.dawson@gmail.com">nyall.dawson@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi list!<br>
<br>
I've a situation where I've got ~millions of lines (each consisting of<br>
a single segment only) which I need to intersect against a complex<br>
polygon.<br>
<br>
Trying the naive way of multiple calls to GEOSIntersection_r gives<br>
predictably horrendous performance. Is there a better way I can<br>
approach this situation using the GEOS c api?<br>
<br>
Thanks,<br>
Nyall<br>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a></blockquote></div>