这可以用 O(n) 中的线扫描算法解决吗？

Question

在这个问题中，我们给定平面中的 n 个水平线段，在 O(n) 时间内找到一条与所有线段相交并具有最大可能斜率的线，或者确定没有这样的线。

我想通过不等式求解并获得所有可能的线方程来找到所有可能的线，然后找到斜率最大的线，但是我找不到解决方案与我们在计算几何学中学到的任何东西有关谁能给我一个暗示或提及计算几何中任何可能有帮助的相关主题

Answer 1

正如评论所暗示的线扫描算法比速度慢，O(n)所以答案是否定的，但是简单的O(n)方法仍然是可能的，例如如下所示：

1. 找到你的交叉线的BBOX

   所以您正在搜索x0,y0,x1,y1穿过所有线（水色矩形）内部的“内接”矩形的坐标。这可以在O(n)

   

   因此搜索所有行并得到：

   y0 = min(y)
   y1 = max(y)
   x0 = max(left_x)
   x1 = min(righ_x)
   

   其中每条线的left_x<right_x两个坐标。x

2. 构建你的生产线

   万一x0>x1没有这样的线路是可能的。

   对于最小斜率，只需使用 BBOX 的对角线之一：

   Line(x0,y0,x1,y1)
   Line(x0,y1,x1,y0)
   

   

   这取决于你的坐标系（点甚至可能颠倒）......

   最大的斜率是垂直线，因此您可以使用任何x内部<x0,x1>间隔，例如

   Line(x0,y0,x0,y1)