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

问题描述

许多算法(例如 Graham scan)要求点或向量按其角度排序(也许从其他角度来看，即使用差异向量).这个顺序本质上是循环的，这个循环被打破来计算线性值通常没有那么重要.但是真正的角度值也没有多大关系，只要保持循环顺序即可.因此，对每个点都调用 atan2 可能是一种浪费.有什么更快的方法可以像 atan2 那样计算在角度上严格单调的值?此类函数显然已被某些人称为伪角".

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.

推荐答案

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

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

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

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).

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

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 说它运行良好，对我来说看起来不错:-).

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

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