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