algorithm - 盒子中所有点对的切线范围

Question

假设我有一个盒子，里面有很多点。我需要能够计算通过所有可能的点对的所有线的最小和最大角度。我可以在 O(n^2) 次内完成，只需将每个点与所有其他点一起枚举。但是有没有更快的算法呢？

Answer 1

采用 Evgeny Kluev 提出的双平面思想，以及我关于寻找最左边交点的评论，我将尝试给出一个没有任何对偶空间的等效直接解决方案。

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

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

1. 假设他们有相同的y。如果它们之间没有其他点，那么它们是相邻的。如果它们之间有任何点，那么很明显它们中至少有一个与我们的顺序中的 A 相邻，并且它们都产生相同的角度。

2. 假设在A和B之间存在一个点P，即Ax < Px < Bx。如果P位于AB上，则AP角度相同，x坐标差较小，矛盾。当 P 不在 AB 上时，AP 或 PB 都会给你较小的角度，这也会产生矛盾.

3. 现在我们有点 A 和 B 位于两条相邻的垂直线上。这些线之间没有其他点。如果 A 和 B 是它们垂直线上的唯一点，那么 AB 对在排序顺序和 QED 上显然是相邻的。如果这些线上有很多点，显然最小角度是取左边垂直线的最高点(必须是A)和右边垂直线的最低点(必须是B)。由于我们按 y 对相等的 x 点进行排序，因此这两个点也是相邻的。