最快的方法是按角度对矢量进行排序，而无需实际计算该角度 [英] Fastest way to sort vectors by angle without actually computing that angle

问题描述

许多算法（例如 Graham扫描）要求点或向量按其角度排序（也许从其他角度看，即使用差异向量）。这个顺序本质上是循环的，在这个循环被打破以计算线性值的地方通常并不重要。但是，只要保持循环顺序，实际角度值也不重要。因此，为每个点调用 atan2 可能会造成浪费。有什么更快的方法来计算角度中严格单调的值， atan2 的方式是什么？这些功能显然被一些人称为伪角。

我开始玩弄这个，并意识到规范是种类不完整。 atan2 有一个不连续性，因为由于dx和dy不同，所以 atan2 会在-pi和+ PI。下图显示了@MvG建议的两个公式，事实上它们在不同的地方与 atan2 相比具有不连续性。 （注意：我在第一个公式中添加了3，在替代项中添加了4，以使图中的行不重叠）。如果我将 atan2 添加到该图中，那么它将是直线y = x。因此，在我看来，可能会有各种答案，取决于人们想在哪里放置不连续点。如果一个人真的想要复制 atan2 ，答案（在这个流派中）就是 $ b $

 ＃输入：dx，dy：（差异）向量的坐标。 
＃输出：该向量对x轴的角度为单调
＃的范围[-2 .. 2]中的数字。 
＃和与atan2 
 def defangle（dx，dy）相同的不连续性：
p = dx /（abs（dx）+ abs（dy））＃-1 .. 1增加x 
如果dy < 0：返回p  -  1＃-2 .. 0随着x 
增加而增加b else：返回1  -  p＃0 .. 2随着x 
减少 

这意味着如果您使用的语言具有符号函数，则可以通过返回符号（dy）（1-p）来避免分支，在-2和+2之间的不连续处回答0。同样的技巧可以用于@ MvG的原创方法，可以返回符号（dx）（p-1）。

更新在下面的评论中，@MvG建议对此进行一行C实现，即

  pseudoangle = copysign（1。 -  dx /（晶圆厂（dx）+晶圆厂（dy）），dy）
  

@MvG表示它运作良好，它看起来不错： - ）。

Many algorithms (e.g. Graham scan) require points or vectors to be sorted by their angle (perhaps as seen from some other point, i.e. using difference vectors). This order is inherently cyclic, and where this cycle is broken to compute linear values often doesn't matter that much. But the real angle value doesn't matter much either, as long as cyclic order is maintained. So doing an atan2 call for every point might be wasteful. What faster methods are there to compute a value which is strictly monotonic in the angle, the way atan2 is? Such functions apparently have been called "pseudoangle" by some.

解决方案

I started to play around with this and realised that the spec is kind of incomplete. atan2 has a discontinuity, because as dx and dy are varied, there's a point where atan2 will jump between -pi and +pi. The graph below shows the two formulas suggested by @MvG, and in fact they both have the discontinuity in a different place compared to atan2. (NB: I added 3 to the first formula and 4 to the alternative so that the lines don't overlap on the graph). If I added atan2 to that graph then it would be the straight line y=x. So it seems to me that there could be various answers, depending on where one wants to put the discontinuity. If one really wants to replicate atan2, the answer (in this genre) would be

# 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

This means that if the language that you're using has a sign function, you could avoid branching by returning sign(dy)(1-p), which has the effect of putting an answer of 0 at the discontinuity between returning -2 and +2. And the same trick would work with @MvG's original methodology, one could return sign(dx)(p-1).

Update In a comment below, @MvG suggests a one-line C implementation of this, namely

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

@MvG says it works well, and it looks good to me :-).

这篇关于最快的方法是按角度对矢量进行排序，而无需实际计算该角度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！