Bix*_*ein 5 algorithm geometry line bounding-box
我想计算线排列的边界框（没有平行线）。边界框应包含线条布置的所有交点。
我进行了一些研究，发现几次计算边界框应该可以在O（n log n）时间内完成。不幸的是，我找不到此要求的来源。
我试图提出一种算法，可以在O（n log n）的时间内解决此问题，但到目前为止还无法完成。我尝试使用对偶性来计算包络线，但不幸的是，包络线并不总是包含最低和最高的交集。
如果有人知道在哪里可以找到这样的算法或其工作原理，我将不胜感激。
小智 5
可以在O（n log n）时间内完成。我们不必检查每个交叉点，只需要找到x和y坐标最高/最低的交叉点即可。
这是我想出的。我认为我们正在同一堂课中，这几乎完全是我要提交的内容，因此，如果要使用此解决方案，请不要只是复制粘贴它。
左界算法：
1）根据点线对偶性l：y = mx + c => l * =（m，-c）将线变成点。上）
2）通过x坐标对其进行排序。O（n log n）
3）将前两点的线保存为斜率最低的线。O（1）
4）经过点，如果两条点P [i]和P [i + 1]的线的斜率比以前保存的最低斜率低，则将该线另存为具有最低斜率的线。上）
5）再次使用对偶，将直线定为一点。O（1）
6）返回该点的x坐标作为左边界。O（1）
斜率最低的线表示x坐标最低的交点。右边界的工作原理相同，但斜率最高。为了获得上下限的算法，我们可以将对偶性更改为l：y = mx + c => l * =（-c，m）（基本上将平面旋转90度）以便能够确定通过查看坡度，可以找到最低和最高的交点。
我们不必查看线的所有交点即可找到最陡的斜率，根据x坐标查看彼此相邻的线就足够了。