我想计算一组直线的边界框(没有平行线)。该边界框应包含所有直线交点。
我进行了一些研究,发现计算边界框应该可以在O(n log n)时间内完成。不幸的是,我无法找到这个说法的来源。
我尝试想出一个算法,以O(n log n)的时间解决此问题,但目前还没有成功。我尝试使用对偶性来计算信封,但不幸的是,信封并不总是包含最低和最高交点。
如果有人知道在哪里找到这样的算法或者它是如何工作的,我将不胜感激。
我进行了一些研究,发现计算边界框应该可以在O(n log n)时间内完成。不幸的是,我无法找到这个说法的来源。
我尝试想出一个算法,以O(n log n)的时间解决此问题,但目前还没有成功。我尝试使用对偶性来计算信封,但不幸的是,信封并不总是包含最低和最高交点。
如果有人知道在哪里找到这样的算法或者它是如何工作的,我将不胜感激。