<div dir="ltr"><div dir="ltr">On Fri, Jun 26, 2020 at 2:25 AM Nyall Dawson <<a href="mailto:nyall.dawson@gmail.com">nyall.dawson@gmail.com</a>> wrote:<br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Fri, 26 Jun 2020 at 11:54, Martin Davis <<a href="mailto:mtnclimb@gmail.com" target="_blank">mtnclimb@gmail.com</a>> wrote:<br>
><br>
><br>
><br>
> On Thu, Jun 25, 2020 at 6:02 PM Andrew Bell <<a href="mailto:andrew.bell.ia@gmail.com" target="_blank">andrew.bell.ia@gmail.com</a>> wrote:<br>
>><br>
>> 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?<br>
><br>
><br>
> I'm curious about this as well.<br>
<br>
I probably should have started with that!<br>
<br>
I'm trying to write an algorithm which calculates polygon fetch lines<br>
(longest possible straight line inside a polygon). The general<br>
approach is to create rays which connect each pair of vertices, clip<br>
these to the polygon, and then find the longest one. It's horribly<br>
inefficient for complex polygons, and I've only been able to find very<br>
small optimisations to allow skipping the clip operation for some<br>
pairs (e.g. calculate the length of the ray which is inside the<br>
polygon's bounding box, if it's shorter than the current maximum<br>
length candidate then discard the pair immediately, ditto with the<br>
oriented minimum bounding box and convex hull).<br></blockquote><div><br></div><div>1) This is not really the same problem as the one you posed.</div><div>2) There are definitely optimizations to be made.  You certainly don't need to test every pair.</div><div>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.</div><div>4) Can the poly contain holes? If so, the problem seems harder.</div><div><br></div><div>Still scratching my head wondering why you'd want this number, but my imagination is sometimes weak.</div><div><br></div></div>-- <br><div dir="ltr" class="gmail_signature">Andrew Bell<br><a href="mailto:andrew.bell.ia@gmail.com" target="_blank">andrew.bell.ia@gmail.com</a></div></div>