On Fri, 26 Jun 2020 at 01:57, Martin Davis <mtncl...@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.daw...@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@lists.osgeo.org >> https://lists.osgeo.org/mailman/listinfo/geos-devel > > _______________________________________________ > geos-devel mailing list > geos-devel@lists.osgeo.org > https://lists.osgeo.org/mailman/listinfo/geos-devel _______________________________________________ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
