TADM2E 4.27

Problem

4-27. Let P be a simple, but not necessarily convex, polygon, and q an arbitrary point not necessarily in P. Design an efficient algorithm to find a line segment originating from q that intersects the maximum number of edges of P. In other words, if standing at point q, in what direction should you aim a gun so the bullet will go through the largest number of walls? A bullet through a vertex of P gets credit for only one wall. An O(n lg n) algorithm is possible.

Solution

Since a bullet through a vertex doesn't count as 2 walls, let's describe the polygon P in terms of pairs of points like [$ (x_1, y_1), (x_2, y_2) $). That is, the first point will count as a wall, but the second will not.

Next, let's convert all of the points in P to polar notation. We don't actually need to store the radius, however, just the angle $ \theta $. Also, the polar notation is relative to q's location, $ (q_x, q_y) $, so for every point p in P we have $ \theta_p = atan((p_y - q_y) / (p_x - q_x)) $. These calculations are done on every point, so a computational complexity of $ \Theta(n) $.

Keep a list of the line segments, with points stored as pairs of angles relative to q, and sort them by the minimum of the two angles. It is okay to switch which angle comes first in a pair, but the pairs must move together when they are sorted. It is also important to preserve knowledge of which point was the source (closed interval) and which was the destination (open interval), so we don't count one vertex twice. This sorting costs O(n lg n), and it is the dominant factor in this algorithm.

Finally, iterate through the sorted list of minimum elements, incrementing a counter whenever the start of a line segment is encountered, and decrementing the counter whenever a line segment ends.