盒子中所有点对的切线范围
Tangents range for all pairs of points in a box
假设我有一个盒子，里面有很多点。我需要能够计算通过所有可能的点对的所有线的最小和最大角度。我可以在 O(n^2) 次内完成，只需将每个点与所有其他点一起枚举。但是有没有更快的算法呢？
对点进行排序（或使用hash map），看看是否有水平线。
然后在双平面上解决这个问题。这里只需要找到最左边和最右边的交点即可。使用二进制搜索找到一对水平坐标，使得所有交点都在它们之间。 （您可以通过从这些坐标继续二进制搜索来快速找到近似结果）。
然后根据双平面上的切线对直线进行排序。对于按此排序顺序排列的成对相邻线，找到最接近这些水平坐标的交点。这并不能保证最坏情况下的良好复杂性（当原始平面上的一些线几乎水平时）。但在大多数情况下，时间复杂度将由排序决定：O(N log N) + O(binary_search_complexity).
采用 Evgeny Kluev 提出的双平面思想，以及我关于寻找最左边交点的评论，我将尝试给出一个没有任何对偶的等效直接解决方案 space。
解决方案很简单：按 (x, y) 字典顺序对您的点进行排序。现在按排序顺序通过每两个相邻点画一条线。可以证明最小角度是由这些线之一实现的。为了获得最大角度，您需要按字典顺序 (x, -y) 排序，并且只检查相邻的点对。
我们用最小角度的思路来证明一下。考虑两个点 A 和 B 产生最小可能的角度。在这些点中，我们可以选择 x 坐标差异最小的对。
假设他们有相同的y。如果它们之间没有其他点，那么它们是相邻的。如果它们之间有任何点，那么很明显它们中至少有一个在我们的顺序中与 A 相邻，并且它们都产生相同的角度。
假设存在一个点P，x坐标在A和之间B，即Ax < Px < Bx。如果 P 位于 AB 上，则 AP 与 的角度相同但差异较小x 坐标，因此矛盾。当 P 不在 AB 上时，则 AP 或 PB 会给你更少的角度，这也会产生矛盾。
现在我们有点 A 和 B 位于两条相邻的垂直线上。这些线之间没有其他点。如果 A 和 B 是它们垂直线上的唯一点，那么 AB 对显然相邻按排序顺序和 QED。如果这些线上有很多点，显然最小角度是取左边竖线上的最高点（必须是A）和右边竖线上的最低点（必须是 B）。由于我们按 y 对等于 x 的点进行排序，因此这两个点也是相邻的。
假设我有一个盒子，里面有很多点。我需要能够计算通过所有可能的点对的所有线的最小和最大角度。我可以在 O(n^2) 次内完成，只需将每个点与所有其他点一起枚举。但是有没有更快的算法呢？
对点进行排序（或使用hash map），看看是否有水平线。
然后在双平面上解决这个问题。这里只需要找到最左边和最右边的交点即可。使用二进制搜索找到一对水平坐标，使得所有交点都在它们之间。 （您可以通过从这些坐标继续二进制搜索来快速找到近似结果）。
然后根据双平面上的切线对直线进行排序。对于按此排序顺序排列的成对相邻线，找到最接近这些水平坐标的交点。这并不能保证最坏情况下的良好复杂性（当原始平面上的一些线几乎水平时）。但在大多数情况下，时间复杂度将由排序决定：O(N log N) + O(binary_search_complexity).
采用 Evgeny Kluev 提出的双平面思想，以及我关于寻找最左边交点的评论，我将尝试给出一个没有任何对偶的等效直接解决方案 space。
解决方案很简单：按 (x, y) 字典顺序对您的点进行排序。现在按排序顺序通过每两个相邻点画一条线。可以证明最小角度是由这些线之一实现的。为了获得最大角度，您需要按字典顺序 (x, -y) 排序，并且只检查相邻的点对。
我们用最小角度的思路来证明一下。考虑两个点 A 和 B 产生最小可能的角度。在这些点中，我们可以选择 x 坐标差异最小的对。
假设他们有相同的y。如果它们之间没有其他点，那么它们是相邻的。如果它们之间有任何点，那么很明显它们中至少有一个在我们的顺序中与 A 相邻，并且它们都产生相同的角度。
假设存在一个点P，x坐标在A和之间B，即Ax < Px < Bx。如果 P 位于 AB 上，则 AP 与 的角度相同但差异较小x 坐标，因此矛盾。当 P 不在 AB 上时，则 AP 或 PB 会给你更少的角度，这也会产生矛盾。
现在我们有点 A 和 B 位于两条相邻的垂直线上。这些线之间没有其他点。如果 A 和 B 是它们垂直线上的唯一点，那么 AB 对显然相邻按排序顺序和 QED。如果这些线上有很多点，显然最小角度是取左边竖线上的最高点（必须是A）和右边竖线上的最低点（必须是 B）。由于我们按 y 对等于 x 的点进行排序，因此这两个点也是相邻的。