在任意单位向量数组中，找到具有最大角度的两个向量的最有效方法是什么？

Question

所以我正在尝试制作一个像模拟人生那样的墙系统。虽然它是 3D，但可以简化为 2D（想想鸟瞰图）。墙由两点定义：起点和终点，墙本身有方向，可以简化为单位向量。墙壁也由直角棱镜制成，这些棱镜中的每一个都从一个点开始并在另一个点结束。所以，考虑到这一点，有时墙壁必须加长，否则墙壁的凸角会出现一个小缝隙

如果其中一个点在墙之间共享。任意数量的墙都可以放置在一个位置上，所以记住所有这些，一个网格点的数据可以包含这样的东西（使用Lua），每个table代表一个vector2，使用table 为了便于可视化，这段代码实际上不会起作用：

local gridPoint = {
  {x = 1, y = 0},
  {x = 0.7071, y = 0.7071},
  {x = 0, y = 1},
  {x = 0.7071, y = -0.7071},
}

这是点的外观图，其中交叉点是网格点，墙壁是从交叉点延伸的矢量，假设每个矢量的长度为 1（请原谅我糟糕的绘画技巧).由于点积大于 180 度时会翻转，因此最大角度总是 <=180。

所以现在，要获得任意两点之间的角度，我们可以 math.deg(math.acos(v1:dot(v2))) 来获得这两点之间的角度（以度为单位），其中 v1 是矢量 1，v2是向量2，dot是returnsv1和v2.

点积的函数

到目前为止，一切都很好。问题是我必须创建两个循环，遍历可能的点积的每一个组合，我不确定这是找到最大角度的最佳方法，这是 #gridPoint^2 可能的组合，在较低的情况下很好数字，但是这个可能的组合数量随着每面新墙呈指数增长。

有更简单的方法吗？

Answer 1

这道题相当于求最远点对，所有点都在单位圆上

排序点-将具有正y（角度0..Pi）的点分离到第一个列表中，并将具有负y的点分离到第二个列表中，对它们进行排序更简单按 X-coordinate，然后加入第一个列表并反转第二个列表。这个阶段需要 O(nlogn) 时间

然后执行最远点的搜索 - 固定第一个点索引（A[i]），遍历列表直到平方距离A[i]-A[j+1]小于平方距离A[i]-A[j]。所以我们找到了A[i]的最远点A[j]。现在递增 i 并搜索它的最远点 - 从 j.
开始重复直到 j 超过 n.

这个阶段是线性的，因为我们只向前移动 i 和 j。从本质上讲，这是一种 旋转卡尺 的方法，因此您可以在其他地方获得一些实现。

Out of an array of arbitrary unit vectors, what is the most efficient method of finding the two vectors that have the largest angle?