millions of lines intersection against single polygon

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

millions of lines intersection against single polygon

Nyall Dawson
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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Martin Davis-3
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!

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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

andrew.bell.ia@gmail.com
In reply to this post by Nyall Dawson

On Thu, Jun 25, 2020 at 2:55 AM 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?

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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Nyall Dawson
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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Martin Davis-3


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?

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

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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

andrew.bell.ia@gmail.com
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:
>
> 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

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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Martin Davis-3


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. 

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Nyall Dawson
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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

andrew.bell.ia@gmail.com
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.
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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Nyall Dawson
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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Martin Davis-3
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.

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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Nyall Dawson
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
Reply | Threaded
Open this post in threaded view
|

Re: millions of lines intersection against single polygon

Martin Davis-3


On Wed, Jul 1, 2020 at 3:14 PM Nyall Dawson <[hidden email]> wrote:

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

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