这是一个有趣的练习:
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 log n) algorithm is possible. n is the number of vertices or edges, as it is a polygon, number of edges roughly equals to number of vertices.
这是我的想法:
首先将 q 与 P 中的所有顶点(假设有 N 个顶点)连接起来。将有 N 行，或 N-1 对行。
最后的射击线必须在这些对之间。所以我们必须找到包含最多边数的对。
我不认为这个解决方案是 O(n log n)。
有什么想法吗？
最佳答案
嗯，先把点坐标转换成以P为中心的极坐标系。
- 不失一般性，让我们选择顺时针方向作为角度坐标的特殊方向。
- 现在让我们沿着多边形的所有边依次进行圆形行走，并注意这些边的起点和终点，在此处行走以相对于 P 的顺时针方向进行。
- 我们称这种边的终点为“屁股”，起点为“头”。这一切都应该在 O(n) 中完成。现在我们必须对这些头和屁股进行排序，因此使用快速排序可能是
O(nlog(n))。我们按照它们的角度 (φ) 坐标从最小的 φ 向上排序，确保在 φ 坐标相等的情况下，头部被认为小于枪托(这对于遵守问题的最后一条规则很重要)。 - >
完成后，我们将从最小的 φ 开始遍历它们，每当遇到屁股时递增运行总和，每当遇到头部时递减，注意全局最大值，这将是 φ 坐标上的间隔。这也应该在 O(n) 中完成，因此整体复杂度为
O(nlog(n))。
现在你能告诉我你为什么问这种问题吗？
关于algorithm - 找到尽可能多次与多边形相交的射线，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10474287/