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

[Nyall Dawson]

On Fri, 26 Jun 2020 at 23:35, Andrew Bell <andrew.bell.ia at gmail.com> wrote:
>
> On Fri, Jun 26, 2020 at 2:25 AM Nyall Dawson <nyall.dawson at gmail.com> wrote:
>>
>> On Fri, 26 Jun 2020 at 11:54, Martin Davis <mtnclimb at gmail.com> wrote:
>> >
>> >
>> >
>> > On Thu, Jun 25, 2020 at 6:02 PM Andrew Bell <andrew.bell.ia at gmail.com> 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
> andrew.bell.ia at gmail.com
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel