algorithm - O(n log n) 时间内排列的边界框

Question

我想计算线排列的边界框(没有平行线)。边界框应包含线排列的所有交点。

我做了一些研究，多次发现计算边界框应该可以在 O(n log n) 时间内完成。不幸的是，我无法找到这种说法的来源。

我试图想出一个算法来在 O(n log n) 时间内解决这个问题，但到目前为止还没有成功。我尝试使用对偶性来计算包络线，但不幸的是，包络线并不总是包含最低和最高交点。

如果有人知道在哪里可以找到这样的算法或它是如何工作的，我将不胜感激。

Answer 1

可以在 O(n log n) 时间内完成。我们不必检查每个路口，我们只需要找到具有最高/最低 x 和 y 坐标的路口。

这是我想出的。我想我们在同一个类上，这几乎就是我要交的内容，所以如果你想使用这个解决方案，请不要只是复制粘贴它。

左边界算法:

1) 根据点线对偶性将线变成点 l:y = mx + c => l* = (m, -c)。 O(n)

2) 按 x 坐标排序。 O(n log n)

3) 将前两点的线保存为斜率最低的线。 O(1)

4) 遍历点，如果由两点 P[i] 和 P[i+1] 组成的线的斜率低于先前保存的最低斜率，则将该线保存为具有最低斜率的线。 O(n)

5) 把线变成一个点，再次使用对偶性。 O(1)

6) 返回该点的 x 坐标作为左边界。 O(1)

斜率最低的线表示 x 坐标最低的交点。右边界的工作方式相同，但斜率最高。为了获得上限和下限的算法，我们可以将对偶性更改为 l:y = mx + c => l* = (-c, m) (基本上将平面旋转 90 度)以便能够确定也可以通过观察斜坡来确定最低和最高的交叉点。

我们不必为了找到最陡坡度而查看所有线的交点，根据 x 坐标查看彼此相邻的线就足够了。