StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Okay, I've been pondering this for a while, and I have formulated a <a href="http://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer">backtracking </a> algorithm that I believe will work. The idea is that you will attempt to build a polygon in a counter-clockwise fashion. And we will set up the problem such that the first polygon we find will be the smallest. That way, we don't have to find all of them.</p> <p><strong>Algorithm:</strong></p> <ol> <li>Sort the line segments in order of how close they are to the target point. <ul> <li>Henceforth whenever you need to loop over the lines, loop over them in this sorted order</li> <li>Treat the line segments as infinite lines when calculating their distance from the target point. <img src="https://i.stack.imgur.com/K2KoR.png" alt="point/line distance"></li> </ul></li> <li>Perform Step 3 with the closest line segment, using the <strong>2nd</strong> intersection point along the line in the "counter-clockwise" direction <ul> <li>Take "counter-clockwise" to mean the direction that puts the target point on the left side of the line.</li> <li>NOTE: the <strong>1st</strong> intersection point is hopefully the place where we will end up once we've worked our way around the target point</li> </ul></li> <li><p>On the newly-found line...</p> <p>A. Loop over all of the other lines that are not already part of the shape you are building, finding their intersection points with this line<br /> B. Sort the intersection points counter-clockwise with respect to the target point.<br /> <img src="https://i.stack.imgur.com/bLhSC.png" alt="counter-clockwise sorting"></p></li> <li><p>Find the next intersection point counter-clockwise on the current line. If this is the first point we're checking on this line, then the "next" point is the one after the intersection point that brought us to this line.</p> <p>A. If there is no such point (this might mean that we've already checked all of the points on the current line), then the current candidate solution is infeasible...</p> <ul> <li><strong>Backtrack</strong> to the previous line and repeat <strong>Step 4</strong> with the next point on that line.</li> <li>If there is no previous line (i.e., you're on the line where you started the shape), <strong>Backtrack</strong> and do <strong>Step 2</strong> with the next-closest line, starting a new shape.</li> </ul> <p>B. If the line that forms the intersection point does not have the target point on it's left side (counter-clockwise), then the polygon it would form does not enclose the target point. <strong>Repeat Step 4</strong> for the current line with its next point.<br /> C. If the line that forms the intersection point is the line you started with, then we have found the solution<br /> D. If none of the above is true, do <strong>Step 3</strong> for the line that formed the intersection point.</p></li> </ol> <p><strong>Optimizations:</strong></p> <ol> <li>If there are fewer than 3 lines, there is no solution. Don't do any work.</li> <li>You may want to cache the intersection points when you find them so that you don't have to recalculate them <ul> <li>If you choose to do this, I recommend using a 2D array</li> </ul></li> <li>I recommend throwing out lines when you know that they aren't part of the solution. <ul> <li>Example: if you already tried the line closest to the target point, but it didn't lead to a solution, it doesn't make sense to include that line when finding intersection points on other lines.</li> </ul></li> </ol> <p><strong>Remarks:</strong><br /></p> <ul> <li>This algorithm will be easiest to implement recursively.</li> <li>You will have to decide what to do if the target point is <strong>on</strong> one of the lines</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload