找到一条射线，使其与多边形相交的次数尽可能多。

Question

这是一个有趣的练习：

假设P是一个简单但不一定是凸多边形，q是一个任意点，不一定在P中。

设计一个有效的算法，从q出发找到一条线段，使其与尽可能多的P的边相交。

换句话说，在站在点q处时，应该向哪个方向瞄准枪才能穿过最多的墙壁？

通过P的顶点的子弹只得到一个点的信用。

可以使用O(n log n)算法。n是顶点或边的数量，因为它是一个多边形，因此边的数量大致等于顶点的数量。

我的想法是：

首先将q与P中所有的顶点连接起来（假设有N个顶点）。这将得到N条直线或N-1组直线。

最终的射击线必须在这些线对之间。因此，我们必须找到包含最多边的线对。

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

有什么想法吗？

- Jackson Tale

---

哇，我一点都不知道。出于好奇，这里的n是什么？边的数量吗？ - Jeremy

我相信这个问题是相关的：https://dev59.com/T2855IYBdhLWcg3wQx9L 你可以将P中的每个线段表示为一个光线从q必须落在之间的弧度值对。 - Sam Dufel

@Jeremy 我编辑了。是的，n 可以是边或顶点的数量，在多边形中大致相同。 - Jackson Tale

Answer 1

首先，将点的坐标转换为以P为中心的极坐标系。

不妨选择顺时针方向作为角度坐标的特殊方向。

现在，我们按顺序沿多边形的所有边进行循环遍历，并注意这些边的起点和终点，在顺时针方向下与P相比，步行会带我们到达哪个点。

让我们称此类边的结束点为“butt”，开始点为“head”。这一切都应该在O(n)内完成。现在，我们需要按照它们的角度（φ）坐标从最小的φ开始对这些头和butt进行排序，并确保在φ坐标相等的情况下，头被认为比butt更小（这非常重要以遵守问题的最后一个规则）。使用快速排序可以做到O(nlog(n))。

完成后，我们将从最小的φ开始遍历，每当遇到butt时增加运行总和，每当遇到head时减少运行总和，同时注意全局最大值，这将是φ坐标上的一个区间。这也应该在O(n)内完成，因此总体复杂度为O(nlog(n))。

现在，你能告诉我为什么要问这种问题吗？

- Boris Stitnicky

---

谢谢您回答这个问题。您能否编辑您的答案，使其看起来更好看些？ - Jackson Tale

这是《算法设计手册》中的一项练习。 - Jackson Tale

有人能详细解释一下这个解决方案吗，特别是第三和第四点@BorisStitnicky？ - KingJames

@KingJames，随着时间的推移，我意识到措辞可能需要改进。但我不会这样做。如果你愿意，你可以编辑答案，但我认为现在它已经足以激发正确方向上的思考，特别是考虑到这基本上是一项家庭作业任务。 - Boris Stitnicky

我有一个问题。你知道如何正确地进行顺时针或逆时针行走吗？如果P位于多边形内部，似乎存在歧义。多边形的最后一条边将与φ = 0方向相交，但区间头部的φ值将小于尾部的φ值。 - Michael Katkov

我发现叉积是解决这个问题的好方法。 - Michael Katkov

Answer 2

我使用了Boris Stitnicky的算法，并用Java编写了我的解决方案。但我选择逆时针方向，并使用叉积来检查区间的起点和终点。您可以在这里找到它：https://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java

- Michael Katkov