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 [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
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 <[hidden email]> wrote: Hi list! _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
In reply to this post by Nyall Dawson
On Thu, Jun 25, 2020 at 2:55 AM Nyall Dawson <[hidden email]> wrote: Hi list! There's an algorithm in PDAL that does this for point-in-polygon, but all the guts are there to do segment intersections. You're welcome to take it and modify to your liking: https://github.com/PDAL/PDAL/tree/master/filters/private/pnp How much better it would from a more brute-force approach depends a lot on the data. Andrew Bell [hidden email] _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
In reply to this post by Martin Davis-3
On Fri, 26 Jun 2020 at 01:57, Martin Davis <[hidden email]> 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 <[hidden email]> 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 >> [hidden email] >> https://lists.osgeo.org/mailman/listinfo/geos-devel > > _______________________________________________ > geos-devel mailing list > [hidden email] > https://lists.osgeo.org/mailman/listinfo/geos-devel geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Thu, Jun 25, 2020 at 3:47 PM Nyall Dawson <[hidden email]> 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? 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. _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
In reply to this post by Nyall Dawson
On Thu, Jun 25, 2020 at 6:47 PM Nyall Dawson <[hidden email]> wrote: On Fri, 26 Jun 2020 at 01:57, Martin Davis <[hidden email]> wrote: What is the real-life use-case for this? Are the lines that you're projecting related to one another in some way? Related to the polygon in any way? Andrew Bell [hidden email] _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Thu, Jun 25, 2020 at 6:02 PM Andrew Bell <[hidden email]> wrote:
I'm curious about this as well. _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Fri, 26 Jun 2020 at 11:54, Martin Davis <[hidden email]> wrote:
> > > > On Thu, Jun 25, 2020 at 6:02 PM Andrew Bell <[hidden email]> wrote: >> >> What is the real-life use-case for this? Are the lines that you're projecting related to one another in some way? Related to the polygon in any way? > > > I'm curious about this as well. I probably should have started with that! I'm trying to write an algorithm which calculates polygon fetch lines (longest possible straight line inside a polygon). The general approach is to create rays which connect each pair of vertices, clip these to the polygon, and then find the longest one. It's horribly inefficient for complex polygons, and I've only been able to find very small optimisations to allow skipping the clip operation for some pairs (e.g. calculate the length of the ray which is inside the polygon's bounding box, if it's shorter than the current maximum length candidate then discard the pair immediately, ditto with the oriented minimum bounding box and convex hull). Nyall > _______________________________________________ > geos-devel mailing list > [hidden email] > https://lists.osgeo.org/mailman/listinfo/geos-devel _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Fri, Jun 26, 2020 at 2:25 AM Nyall Dawson <[hidden email]> wrote: On Fri, 26 Jun 2020 at 11:54, Martin Davis <[hidden email]> wrote: 1) This is not really the same problem as the one you posed. 2) There are definitely optimizations to be made. You certainly don't need to test every pair. 3) This may well be a solved problem. A literature. search is probably in order. Sadly, line-of-sight comes up when people want to shoot things at other people, though the problem may be a little different since the shooter usually knows where the shootee is located. 4) Can the poly contain holes? If so, the problem seems harder. Still scratching my head wondering why you'd want this number, but my imagination is sometimes weak. Andrew Bell [hidden email] _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Fri, 26 Jun 2020 at 23:35, Andrew Bell <[hidden email]> wrote:
> > On Fri, Jun 26, 2020 at 2:25 AM Nyall Dawson <[hidden email]> wrote: >> >> On Fri, 26 Jun 2020 at 11:54, Martin Davis <[hidden email]> wrote: >> > >> > >> > >> > On Thu, Jun 25, 2020 at 6:02 PM Andrew Bell <[hidden email]> wrote: >> >> >> >> What is the real-life use-case for this? Are the lines that you're projecting related to one another in some way? Related to the polygon in any way? >> > >> > >> > I'm curious about this as well. >> >> I probably should have started with that! >> >> I'm trying to write an algorithm which calculates polygon fetch lines >> (longest possible straight line inside a polygon). The general >> approach is to create rays which connect each pair of vertices, clip >> these to the polygon, and then find the longest one. It's horribly >> inefficient for complex polygons, and I've only been able to find very >> small optimisations to allow skipping the clip operation for some >> pairs (e.g. calculate the length of the ray which is inside the >> polygon's bounding box, if it's shorter than the current maximum >> length candidate then discard the pair immediately, ditto with the >> oriented minimum bounding box and convex hull). > > > 1) This is not really the same problem as the one you posed. Well, it boils down to the same issue -- clipping thousands/millions of lines against a single polygon, in order to measure the length of each inside the polygon. > 2) There are definitely optimizations to be made. You certainly don't need to test every pair. > 3) This may well be a solved problem. A literature. search is probably in order. Sadly, line-of-sight comes up when people want to shoot things at other people, though the problem may be a little different since the shooter usually knows where the shootee is located. > 4) Can the poly contain holes? If so, the problem seems harder. Holes are actually the problem -- I've only found optimised approaches for polygons without holes in my literature scan. And yes, the polygon can contain holes. > Still scratching my head wondering why you'd want this number, but my imagination is sometimes weak. It's inspired by this question: https://gis.stackexchange.com/questions/365901/finding-longest-straight-line-within-polygon-in-qgis The routine is used for calculations like "what's the optimal placement for a airplane runway" in this polygon. Nyall > > -- > Andrew Bell > [hidden email] > _______________________________________________ > geos-devel mailing list > [hidden email] > https://lists.osgeo.org/mailman/listinfo/geos-devel _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Tue, Jun 30, 2020 at 10:42 PM Nyall Dawson <[hidden email]> wrote: It's inspired by this question: Well that's pretty cool! The diagrams from QGIS are very nice. They don't seem to mention performance - I assume it's not very fast using their approach. I'm continuing to think about the best way to optimize intersecting a line with an arbitrary polygon (fully general, so can contain holes). Am zeroing in on a solution, but don't have it running yet. It will be interesting to see how much faster it is. _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Thu, 2 Jul 2020 at 01:12, Martin Davis <[hidden email]> wrote:
> > On Tue, Jun 30, 2020 at 10:42 PM Nyall Dawson <[hidden email]> wrote: >> >> It's inspired by this question: >> https://gis.stackexchange.com/questions/365901/finding-longest-straight-line-within-polygon-in-qgis >> The routine is used for calculations like "what's the optimal >> placement for a airplane runway" in this polygon. > > > Well that's pretty cool! The diagrams from QGIS are very nice. They don't seem to mention performance - I assume it's not very fast using their approach. Yeah, it's definitely not going to be fast! The approach used in the answer isn't actually correct either -- you can see in the illustrations that there's longer possible lines. That's due to the use of the "densified" vertices approach, where it's better (and faster) to use the original polygon + ring vertices only instead. But the general approach is fundamentally similar. > I'm continuing to think about the best way to optimize intersecting a line with an arbitrary polygon (fully general, so can contain holes). Am zeroing in on a solution, but don't have it running yet. It will be interesting to see how much faster it is. Do you think this algorithm is a candidate for inclusion in JTS/GEOS itself? Nyall > _______________________________________________ > geos-devel mailing list > [hidden email] > https://lists.osgeo.org/mailman/listinfo/geos-devel _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
On Wed, Jul 1, 2020 at 3:14 PM Nyall Dawson <[hidden email]> wrote:
Yes, that's my plan, assuming there is a significant improvement in performance over the more general OverlayNG algorithm (which I fully expect to be the case). _______________________________________________ geos-devel mailing list [hidden email] https://lists.osgeo.org/mailman/listinfo/geos-devel |
Free forum by Nabble | Edit this page |