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

[Nyall Dawson]

On Thu, 2 Jul 2020 at 01:12, Martin Davis <mtnclimb at gmail.com> wrote:
>
> On Tue, Jun 30, 2020 at 10:42 PM Nyall Dawson <nyall.dawson at gmail.com> 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
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel