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

[Nyall Dawson]

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).

Nyall


> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel