这是一个有趣的练习：
设 P 是一个简单但不一定是凸多边形，q 是不一定在 P 中的任意点。
设计一种有效的算法来找到一条源自 q 且与 P 的最大边数相交的线段。
换句话说，如果站在q点，你应该把枪瞄准什么方向，这样子弹才能穿过最多数量的墙壁？
穿过 P 顶点的子弹仅获得一堵墙的功劳。
O(n log n) 算法是可能的。 n是顶点或边的数量，因为它是多边形，边的数量大致等于顶点的数量。
这是我的想法：
首先将 q 与 P 中的所有顶点（假设有 N 个顶点）连接起来。将有 N 条线，或 N-1 对线。
最终的射击线必须位于这两对之间。所以我们必须找到包含最多边数的对。
我认为这个解决方案不是 O(n log n)。
有任何想法吗？
好吧，首先将点坐标转换为以 P 为中心的极坐标系。
- 不失一般性，我们选择顺时针方向作为相对于角坐标的特殊方向。
- 现在，让我们沿着多边形的所有边依次进行循环行走，并注意这些边的起点和终点，即相对于 P 沿顺时针方向行走。
- 我们将这种边缘的终点称为“屁股”，将起点称为“头部”。这一切都应该在 O(n) 内完成。现在我们必须对这些头和屁股进行排序，所以使用快速排序可能是
O(nlog(n))。我们按照角度 (φ) 坐标从最小的 φ 向上对它们进行排序，确保在 φ 坐标相等的情况下，头部被认为小于屁股（这对于遵守问题的最后一个规则很重要）。
- 完成后，我们将从最小的 φ 开始遍历它们，每当遇到屁股时递增运行总和，每当遇到头部时递减，注意全局最大值，这将是 φ 坐标上的一个区间。这也应该在 O(n) 内完成，因此总体复杂度为
O(nlog(n)).
现在你能告诉我你为什么问这样的问题吗？
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
