Самый быстрый способ сортировки векторов по углу без фактического вычисления этого угла

Ответ 1

Я начал играть с этим и понял, что спецификация является неполной. atan2 имеет разрыв, так как при изменении dx и dy существует точка, в которой atan2 будет прыгать между -pi и + pi. На приведенном ниже графике показаны две формулы, предложенные @MvG, и на самом деле они оба имеют разрывы в другом месте по сравнению с atan2. (NB: я добавил 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), что приводит к ответу 0 на разрыве между возвратом -2 и +2. И тот же трюк будет работать с оригинальной методологией @MvG, можно было бы вернуть знак (dx) (p-1).

Обновление В следующем комментарии @MvG предлагает однострочную реализацию C, а именно

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

@MvG говорит, что он работает хорошо, и это выглядит хорошо для меня: -).

Ответ 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 мы уже имеем монотонную область угла t210 > . Для 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

Ответ 3

Я вроде как тригонометрия, поэтому я знаю, что лучший способ сопоставить угол с некоторыми значениями, которые мы обычно имеем, - это касательная. Конечно, если мы хотим конечное число, чтобы не иметь стычки в сравнении {sign (x), y/x}, он становится немного более запутанным.

Но существует функция, которая отображает [1, + inf [на [1,0] [известную как обратную, что позволит нам иметь конечный диапазон, на который мы будем налагать углы. Обратным к касательной является хорошо известный котангенс, поэтому x/y (да, это так просто).

Небольшая иллюстрация, показывающая значения касательной и кокасательной на единичном круге:

Вы видите, что значения совпадают, когда | x | = | y |, и вы также видите, что если мы будем окрашивать части, которые выдают значение между [-1,1] в обоих кругах, нам удастся покрасить полный круг. Чтобы такое отображение значений было непрерывным и монотонным, мы можем сделать два таких:

• используйте противоположность котангенса, чтобы иметь такое же монотонность, как тангенс
• добавьте 2 в -cotan, чтобы значения совпадали, где tan = 1
• добавьте 4 к одной половине круга (скажем, под диагональю x = -y), чтобы иметь значения, соответствующие одному из разрывов.

Это дает следующую кусочную функцию, которая является непрерывной и монотонной функцией углов с единственным разрывом (который является минимумом):

double pseudoangle(double dx, double dy) 
{
    // 1 for above, 0 for below the diagonal/anti-diagonal
    int diag = dx > dy; 
    int adiag = dx > -dy;

    double r = !adiag ? 4 : 0;

    if (dy == 0)
        return r;

    if (diag ^ adiag)
        r += 2 - dx / dy; 
    else
        r += dy / dx; 

    return r;
}

Обратите внимание, что это очень близко к углы Фаулера с теми же свойствами. Формально pseudoangle(dx,dy) + 1 % 8 == Fowler(dx,dy)

Чтобы говорить о производительности, он гораздо менее разветвлен, чем код Фаулера (и, как правило, менее сложный imo). Скомпилированный с помощью -O3 в gcc 6.1.1, вышеприведенная функция генерирует код сборки с 4 ветвями, где два из них относятся к dy == 0 (один проверяет, являются ли оба операнда "неупорядоченными", таким образом, если dy был NaN, а другая проверяет, равны ли они).

Я бы сказал, что эта версия более точна, чем другие, поскольку она использует только операции сохранения мантиссы, пока не переместит результат в правый интервал. Это должно быть особенно заметно при | x | & Л; < | У | или | y | → | x |, то операция | x | + | y ​​| теряет определенную точность.

Как вы можете видеть на графике, отношение угла-псевдоангеля также хорошо близко к линейному.

Посмотрев, откуда происходят ветки, мы можем сделать следующие замечания:

• Мой код не полагается на abs и copysign, что делает его более самодостаточным. Однако воспроизведение знаковых битов по значениям с плавающей запятой на самом деле довольно тривиально, так как оно просто переворачивает отдельный бит (без ветки!), Поэтому это скорее недостаток.

• Кроме того, другие предлагаемые здесь решения не проверяют, следует ли abs(dx) + abs(dy) == 0 делиться им, но эта версия завершится неудачно, если только один компонент (dy) равен 0 - так, что выбрасывает ветку (или 2 в моем случае).

Если мы выберем примерно один и тот же результат (вплоть до ошибок округления), но без ветвей, мы можем злоупотреблять copsign и писать:

double pseudoangle(double dx, double dy) 
{
    double s = dx + dy; 
    double d = dx - dy; 
    double r = 2 * (1.0 - copysign(1.0, s)); 
    double xor_sign = copysign(1.0, d) * copysign(1.0, s); 

    r += (1.0 - xor_sign);
    r += (s - xor_sign * d) / (d + xor_sign * s);

    return r;
}

Большие ошибки могут произойти, чем с предыдущей реализацией, из-за отмены в d или s, если dx и dy близки по абсолютной величине. Нет проверки на деление на ноль, чтобы быть сопоставимым с другими представленными реализациями, и потому что это происходит только тогда, когда и dx, и dy равны 0.

Ответ 4

nice.. вот переменная, которая возвращает -Pi, Pi, как и многие функции arctan2.

edit note: изменил мой псевдокод на правильный python.. изменен порядок arg для совместимости с математическим модулем pythons atan2(). Edit2 беспокоит больше кода, чтобы поймать случай dx = 0.

def pseudoangle( dy , dx ):
  """ returns approximation to math.atan2(dy,dx)*2/pi"""
  if dx == 0 :
      s = cmp(dy,0)
  else::
      s = cmp(dx*dy,0)  # cmp == "sign" in many other languages.
  if s == 0 : return 0 # doesnt hurt performance much.but can omit if 0,0 never happens
  p = dy/(dx+s*dy)
  if dx < 0: return p-2*s
  return  p

В этом виде максимальная погрешность составляет всего ~ 0,07 радиан для всех углов. (конечно, не оставляйте Pi/2, если вы не заботитесь о величине.)

Теперь для плохих новостей - в моей системе с использованием python math.atan2 примерно на 25% быстрее Очевидно, что замена простого интерпретируемого кода не превзойдет скомпилированный intrisic.

Ответ 5

Просто используйте функцию кросс-продукта. Направление, по которому вы вращаете один сегмент относительно другого, даст либо положительное, либо отрицательное число. Нет триггерных функций и без деления. Быстро и просто. Просто Google это.