在O(n log n)时间内计算线条排列的边界框。

Question

我想计算一组直线的边界框（没有平行线）。该边界框应包含所有直线交点。

我进行了一些研究，发现计算边界框应该可以在O（n log n）时间内完成。不幸的是，我无法找到这个说法的来源。

我尝试想出一个算法，以O（n log n）的时间解决此问题，但目前还没有成功。我尝试使用对偶性来计算信封，但不幸的是，信封并不总是包含最低和最高交点。

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

- Bixilein

---

线段还是无限直线？ - MBo

“no parallel lines”（有点像）意味着无限，除非它是指“没有一条线与其中一个平面轴平行”的Sloppish。 - greybeard

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 坐标相邻即可。

- PelicanFive

---

具有最低斜率的线表示与最低x坐标相交的交点 - 很好。您能否请说明为什么只需要考虑“x轴上的双重邻居”（“斜率上的原始邻居”）？ - greybeard

我不确定你的意思... 你想让我解释一下，为什么我只查看按x坐标排序的列表中相邻的点而不是每两个点的所有组合吗？ - PelicanFive

@greybeard 考虑两条线A和B，其中斜率(A) < 斜率(B)，并且它们相交于点p。第三条线X，其斜率(A) < 斜率(X) < 斜率(B)，将在点p的右侧和左侧各有两个交点，或者新的交点将等于p。在这两种情况下，我们都可以忽略p。 - Lucius

你如何确保双重形式下的最低斜率线是由两个相邻点形成的？为什么不可能由P [i]，P [i + 2]等形成最低斜率线？ - X.Arthur

@X.Arthur 假设我们有两点A、B之间的斜坡AB。现在尝试在它们之间放置另一个点X，并检查AX和XB的斜率。你会发现，AX和XB中的一个总是比AB更陡峭，而另一个则比AB更平缓（除非X恰好在AB上）。您可以轻松地尝试所有情况，将X放在A和B之上，将X放在AB之上但低于较高的点等。由于没有办法放置X使得AB保持最陡峭的斜坡，因此我们可以得出结论，最陡峭的斜坡总是在相邻两点之间。 - PelicanFive

Answer 2

我不同意PelicanFive的说法，因为你仍然需要检查所有不同的线段对以找到最低斜率的线段。

我的处理方法是（以最左边和最右边的交点为例）使用一条从极远处的左侧和极远处的右侧垂直线向交点扫描。

在非常遥远的距离，这条垂直线将按顺序与所有这些线相交，从上到下记录此顺序。

请注意，如果此垂直线通过某个交点，则顺序将更改。

在决策树模型中，找到第一个交点的步骤数为O(log n)，每次检查将花费O(n)。

因此，总运行时间为O(n log n)。

对于最上面和最下面的顶点也是如此。

- X.Arthur