找到可见的线

Question

最近面试，面试官问我“line visibility”。

问题是这样的-有x轴和y轴，假设一个人（P）站在（0，∞）。现在在这个平面上画了一些线，注意这些是线而不是线段。我们必须找到 P 可见的所有线。他说你可以假设线以对象的形式给出，并且有一个函数 returns 两条线的交点。同样为了简单起见，我们假设没有平行线。

现在我确定可以看到最左端和最右端（具有最大和最小斜率）的 2 条线，但是如何找到线段位于极端线之间的线？我相信下一个后续问题是 - 解决方案的时间复杂度是多少以及如何优化它？

Answer 1

在极对偶性下相当于计算一组点的上凸包，具体来说，每条线y = m x + b对应点(m, b)。上层船体有大量算法选择； Graham 扫描非常简单并且运行及时O(n log n)。