盒子内任意两点间的切线范围

Question

盒子内任意两点间的切线范围

algorithmcomputational-geometry

3

假设我有一个装满了点的盒子。我需要能够计算通过所有可能的点对的所有线条的最小和最大角度。我可以通过枚举每个点与其他所有点的方式在O(n^2)时间内完成它。但是是否有更快的算法？

- Yola

对于所有可能的不同点A和B的向量AB，您是否正确地在范围*[0; 2 pi]内取极角？特别是，除非只有一个点，否则得到的范围总是至少为pi*。 - stgatilov

1

@stgatilov 我需要计算与x轴的角度，我认为范围是[0:pi)。 - Yola

很抱歉，我的解决方案使用范围*[-pi/2; pi/2]。换句话说，它找到了k的范围，k是k x + b*中的线系数。 - stgatilov

@stgatilov，我们能不能将整个东西旋转-pi/2，然后再应用你的方法？不管怎样，你的方法非常好！ - Yola

1

是的，你说得对。我们只需要检查 (y, x) 和 (y, -x) 的排序顺序即可 =) - stgatilov

2个回答

2

对点进行排序(或使用哈希映射)以找出是否存在任何水平线。

然后在双重平面上解决此问题。您只需要找到最左和最右的交点。使用二分搜索查找一对水平坐标，使得所有交点都在它们之间。(您可以通过从这些坐标继续进行二分搜索来快速找到近似结果)。

然后按照它们在双重平面上的切线对行进行排序。对于在此排序顺序中相邻的线对，找到最靠近水平坐标的交点。这不能保证在原始平面上有些线条几乎水平的最差情况下具有好复杂度。但在大多数情况下，时间复杂度将由排序确定：O(N log N) + O(二分搜索复杂度)。

- Evgeny Kluev

我认为你可以使用O（N log N + K）扫描线算法来找到平面上线段的交点。由于您只需要最左边的点，因此您只需要按（-k，b）字典顺序对线进行排序，然后检查相邻线的交点。在最坏情况下，它将花费O（N log N）。 - stgatilov

@stgatilov 我应该如何找到所有的交点？它们有n^2个。我可以使用Bentley-Ottmann算法来处理线段，但不适用于直线。 - Yola

@stgatilov：我无法理解如何使用扫描线算法获得 O(N log N) 的最坏情况。你能详细说明一下吗？ - Evgeny Kluev

1

好的，我们只需要 N 条线的最左交点。我们将使用扫描线算法来解决它。首先将扫描线放在 x = -无穷大 上。显然，所有的线按照以字典序排序的*(-k, b)*的顺序与竖直线相交。回想一下扫描线算法计算每两条相邻线的交点并将事件放入堆中。当我们通过交点(即事件发生)移动我们的扫描线时，线的顺序会改变(它们通常存储在平衡树中)。 - stgatilov

然而，我们只需要最左边的交点，因此停在第一个事件上就足够了。我们既不需要堆也不需要二叉树。只需计算相邻线段之间的所有交点，并选择最先发生的那个。它就是最左边的交点。 - stgatilov

感谢您提出双平面的想法。 - Yola

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- stgatilov · Accepted Answer

采用 Evgeny Kluev 提出的双平面概念，结合我的关于查找最左交点的建议，我将尝试给出一个等效的直接解决方案，无需任何双重空间。

解决方案很简单：按字典顺序对您的点进行排序 (x, y)。现在，在排序顺序中每两个相邻点之间画一条线。可以证明这些线中最小的角度是其中之一。要获得最大角度，您需要按字典顺序通过 (x, -y) 进行排序，并且仅检查相邻的点对。

让我们用最小角度的思想证明一下。考虑产生可能的最小角度的两个点 A 和 B。在这样的点中，我们可以选择差异最小的 x 坐标的一对。

1. 假设它们有相同的 y。如果它们之间没有其他点，则它们是相邻的。如果它们之间有任何点，则显然其中至少一个与我们的顺序中的 A 相邻，并且所有这些点均产生相同的角度。

2. 假设存在一点 P，其 x 坐标在 A 和 B 之间，即 Ax < Px < Bx。如果 P 在 AB 上，则 AP 具有相同的角度但 x 坐标的差异更小，从而产生矛盾。当 P 不在 AB 上时，则 AP 或 PB 中的任何一个将给您更小的角度，这也产生矛盾。

3. 现在，我们有两个相邻的垂直线上的点 A 和 B。这些线之间没有其他点。如果 A 和 B 是它们所在垂直线上唯一的点，则对于排序顺序中的 AB 对来说显然是相邻的，因此原命题成立。如果这些线上有许多点，显然最小角度可以通过在左侧垂直线上取最高点（必须是 A）和在右侧垂直线上取最低点（必须是 B）来实现。由于我们按 y 来排序等 x 的点，这两个点也是相邻的。