找到与多边形相交的光线尽可能多次

Question

这是一个有趣的练习:

设P是一个简单但不一定是凸的多边形,q是任意一点,不一定是P.

设计一种有效的算法来找到源自q的线段,该线段与P的最大边数相交.

换句话说,如果站在q点,你应该朝着什么方向瞄准枪,这样子弹将穿过最大数量的墙壁？

穿过P顶点的子弹只能获得一面墙的信誉.

O(n log n)算法是可能的.n是顶点或边的数量,因为它是多边形,边数大致等于顶点数.

这是我的想法:

首先在P中连接q与所有顶点(假设有N个顶点).将有N行或N-1对行.

最终的射击线必须在这些对之间.所以我们必须找到包含最多边数的对.

我不认为这个解决方案是O(n log n).

有任何想法吗？

Answer 1

好吧,首先将点坐标转换为以P为中心的极坐标系.

• 不失一般性,让我们选择相对于角度坐标的顺时针方向.
• 现在让我们沿着多边形的所有边缘顺序进行圆形步行,让我们注意那些边缘的起点和终点,其中步行带我们相对于P顺时针方向.
• 让我们将这种边的终点称为'对接',将起点称为'头'.这一切都应该在O(n)中完成.现在我们必须对这些头部和头部进行排序,因此可能会使用quicksort O(nlog(n)).我们按照从最小φ向上的角度(φ)坐标对它们进行排序,确保在φ坐标相等的情况下,头部被认为小于对接(这对于符合问题的最后规则很重要).
• 一旦完成,我们将从最小的φ开始走它们,每当我们遇到一个屁股时递增运行总和,并且每当我们遇到一个头时递减,注意到全局最大值,这将是φ坐标上的间隔.这也应该在O(n)中完成,因此整体复杂性是O(nlog(n)).

现在你能告诉我你为什么问这类问题？