O(n log n) 时间内排列的边界框
Bounding Box of the Line Arrangement in O(n log n) time
我想计算线排列的边界框（没有平行线）。边界框应包含线排列的所有交点。
我做了一些研究，多次发现计算边界框应该可以在 O(n log n) 时间内完成。不幸的是，我无法找到这种说法的来源。
我试图想出一个在 O(n log n) 时间内解决这个问题的算法，但到目前为止还没有成功。我尝试使用对偶性来计算包络线，但不幸的是，包络线并不总是包含最低和最高交点。
如果有人知道在哪里可以找到这样的算法或它是如何工作的，我将不胜感激。
可以在 O(n log n) 时间内完成。我们不必检查每个路口，我们只需要找到具有 highest/lowest 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) Return 该点的 x 坐标作为左边界。 O(1)
斜率最低的线表示 x 坐标最低的交点。右边界的工作方式相同，但斜率最高。为了获得上限和下限的算法，我们可以将对偶性更改为 l:y = mx + c => l* = (-c, m) （基本上将平面旋转 90 度）以便能够通过查看斜率来确定最低和最高交点。
我们不必为了找到最陡的斜率而查看所有线的交点，根据 x 坐标查看彼此相邻的线就足够了。
我不同意 PelicanFive 所说的，因为您仍然需要检查所有不同的线对以找到最低斜率线。
我的处理方法是（以最左边和最右边的交点为例）用一条从左边很远，右边很远的垂线扫向交点
在很远的距离，这条竖线会和所有这些线相交，从上到下按顺序，记录下这个顺序。
注意，如果这条垂直线经过某个交点，顺序会改变。
在决策树模型中，找到第一个交点顶点的步骤数为 O(log n)，每次检查将花费 O(n)。
因此，总运行时间为 O(n log n)。
最上面和最下面的顶点是一样的。
我想计算线排列的边界框（没有平行线）。边界框应包含线排列的所有交点。
我做了一些研究，多次发现计算边界框应该可以在 O(n log n) 时间内完成。不幸的是，我无法找到这种说法的来源。
我试图想出一个在 O(n log n) 时间内解决这个问题的算法，但到目前为止还没有成功。我尝试使用对偶性来计算包络线，但不幸的是，包络线并不总是包含最低和最高交点。
如果有人知道在哪里可以找到这样的算法或它是如何工作的，我将不胜感激。
可以在 O(n log n) 时间内完成。我们不必检查每个路口，我们只需要找到具有 highest/lowest 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) Return 该点的 x 坐标作为左边界。 O(1)
斜率最低的线表示 x 坐标最低的交点。右边界的工作方式相同，但斜率最高。为了获得上限和下限的算法，我们可以将对偶性更改为 l:y = mx + c => l* = (-c, m) （基本上将平面旋转 90 度）以便能够通过查看斜率来确定最低和最高交点。
我们不必为了找到最陡的斜率而查看所有线的交点，根据 x 坐标查看彼此相邻的线就足够了。
我不同意 PelicanFive 所说的，因为您仍然需要检查所有不同的线对以找到最低斜率线。
我的处理方法是（以最左边和最右边的交点为例）用一条从左边很远，右边很远的垂线扫向交点
在很远的距离，这条竖线会和所有这些线相交，从上到下按顺序，记录下这个顺序。
注意，如果这条垂直线经过某个交点，顺序会改变。
在决策树模型中，找到第一个交点顶点的步骤数为 O(log n)，每次检查将花费 O(n)。
因此，总运行时间为 O(n log n)。
最上面和最下面的顶点是一样的。