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

[Andrew Bell]

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.
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
andrew.bell.ia at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20200626/9dd2ca66/attachment.html>