通过角度对矢量进行排序的最快方法,而无需实际计算该角度

Question

许多算法(例如格雷厄姆扫描)要求点或矢量按其角度排序(可能从其他点看,即使用差矢量).这个顺序本质上是循环的,并且在这个循环被破坏以计算线性值的情况下通常无关紧要.但是,只要维持循环次序,真实角度值也无关紧要.因此,atan2为每一点做一个电话可能是浪费.有什么更快的方法来计算一个在角度上严格单调的值,方法atan2是什么？这些功能显然被一些人称为"伪角".

Answer 1

我开始玩这个并意识到规范有点不完整. atan2有一个不连续性,因为当dx和dy变化时,有一个点atan2会在-pi和+ pi之间跳跃.下图显示了@MvG建议的两个公式,实际上它们在不同的地方都有不连续性atan2.(注意:我在第一个公式中添加了3,在替代方案中添加了4个,以便线条在图表上不重叠).如果我添加atan2到该图形,那么它将是直线y = x.所以在我看来,可能有各种答案,取决于人们想要将不连续性放在哪里.如果一个人真的想要复制atan2,答案(在这种类型中)将是

# Input:  dx, dy: coordinates of a (difference) vector.
# Output: a number from the range [-2 .. 2] which is monotonic
#         in the angle this vector makes against the x axis.
#         and with the same discontinuity as atan2
def pseudoangle(dx, dy):
    p = dx/(abs(dx)+abs(dy)) # -1 .. 1 increasing with x
    if dy < 0: return p - 1  # -2 .. 0 increasing with x
    else:      return 1 - p  #  0 .. 2 decreasing with x

这意味着如果您使用的语言具有符号函数,则可以通过返回符号(dy)(1-p)来避免分支,这会在返回-2和之间的不连续处设置0的答案. +2.同样的技巧适用于@ MvG的原始方法,可以返回符号(dx)(p-1).

更新在下面的评论中,@ MVG建议对此进行单行C实现,即

pseudoangle = copysign(1. - dx/(fabs(dx)+fabs(dy)),dy)

@MvG说效果很好,对我来说看起来不错:-).

Answer 2

我知道一个可能的这样的功能,我将在这里描述.

# Input:  dx, dy: coordinates of a (difference) vector.
# Output: a number from the range [-1 .. 3] (or [0 .. 4] with the comment enabled)
#         which is monotonic in the angle this vector makes against the x axis.
def pseudoangle(dx, dy):
    ax = abs(dx)
    ay = abs(dy)
    p = dy/(ax+ay)
    if dx < 0: p = 2 - p
    # elif dy < 0: p = 4 + p
    return p

那么为什么这样呢？需要注意的一点是,缩放所有输入长度不会影响输出.所以矢量的长度(dx, dy)是无关紧要的,只有它的方向很重要.专注于第一象限,我们暂时可以假设dx == 1.然后dy/(1+dy)从零单调增长dy == 0到一无限dy(即为dx == 0).现在还必须处理其他象限.如果dy是否定的,那么初始也是如此p.因此,对于正面,dx我们已经-1 <= p <= 1在角度范围内具有范围单调.因为dx < 0我们更改了标志并添加了两个.这给出了一个范围1 <= p <= 3的dx < 0,和一系列的-1 <= p <= 3整体上.如果负数是由于某种原因不理想,该elif注释行可以包括在内,这将在第四象限,从转变-1…0到3…4.

我不知道上面的函数是否具有已建立的名称,以及谁可能首先发布它.我很久以前就已经把它从一个项目复制到另一个项目了.然而,我发现发生在网络上的这一点,所以我会考虑这个剪断公众足够的重复使用.

有一种方法可以获得范围[0 ... 4](对于实际角度[0 ...2π])而不引入进一步的区分:

# Input:  dx, dy: coordinates of a (difference) vector.
# Output: a number from the range [0 .. 4] which is monotonic
#         in the angle this vector makes against the x axis.
def pseudoangle(dx, dy):
    p = dx/(abs(dx)+abs(dy)) # -1 .. 1 increasing with x
    if dy < 0: return 3 + p  #  2 .. 4 increasing with x
    else:      return 1 - p  #  0 .. 2 decreasing with x