Qual é a melhor maneira de transformar um vetor 2D na direção da bússola de 8 direções mais próxima?

Se você tem um vetor 2D expresso em xey, qual é a melhor maneira de transformá-lo na direção da bússola mais próxima?

por exemplo

x:+1,  y:+1 => NE
x:0,   y:+3 => N
x:+10, y:-2 => E   // closest compass direction

A maneira mais simples é provavelmente obter o ângulo do vetor usando atan2(), como sugere o Tetrad nos comentários, e depois escalá-lo e arredondá-lo, por exemplo (pseudocódigo):

// enumerated counterclockwise, starting from east = 0:
enum compassDir {
    E = 0, NE = 1,
    N = 2, NW = 3,
    W = 4, SW = 5,
    S = 6, SE = 7
};

// for string conversion, if you can't just do e.g. dir.toString():
const string[8] headings = { "E", "NE", "N", "NW", "W", "SW", "S", "SE" };

// actual conversion code:
float angle = atan2( vector.y, vector.x );
int octant = round( 8 * angle / (2*PI) + 8 ) % 8;

compassDir dir = (compassDir) octant;  // typecast to enum: 0 -> E etc.
string dirStr = headings[octant];

A octant = round( 8 * angle / (2*PI) + 8 ) % 8linha pode precisar de alguma explicação. Em praticamente todas as línguas que conheço, a atan2()função retorna o ângulo em radianos. Dividir por 2 π converte-o de radianos em frações de um círculo completo e, multiplicando por 8, converte-o em oitavos de um círculo, que arredondamos para o número inteiro mais próximo. Por fim, reduzimos o módulo 8 para cuidar do contorno, de modo que 0 e 8 sejam mapeados corretamente para o leste.

A razão para o + 8que ignorei acima é que em alguns idiomas atan2()pode retornar resultados negativos (por exemplo, de - π a + π em vez de 0 a 2 π ) e o operador módulo ( %) pode ser definido para retornar valores negativos para argumentos negativos (ou seu comportamento para argumentos negativos pode ser indefinido). Adicionando8 (ou seja, uma volta completa) à entrada antes da redução garante que os argumentos sejam sempre positivos, sem afetar o resultado de nenhuma outra maneira.

Se o seu idioma não fornecer uma função conveniente de arredondar para o mais próximo, você poderá usar uma conversão de truncamento de números inteiros e apenas adicionar 0,5 ao argumento, desta forma:

int octant = int( 8 * angle / (2*PI) + 8.5 ) % 8;  // int() rounds down

Observe que, em alguns idiomas, a conversão padrão de float para número inteiro arredonda as entradas negativas para cima em direção a zero, e não para baixo, o que é outro motivo para garantir que a entrada seja sempre positiva.

Obviamente, você pode substituir todas as ocorrências 8dessa linha por algum outro número (por exemplo, 4 ou 16, ou mesmo 6 ou 12, se você estiver em um mapa hexadecimal) para dividir o círculo em várias direções. Apenas ajuste a enumeração / matriz de acordo.

Você tem 8 opções (ou 16 ou mais, se desejar uma precisão ainda mais fina).

Use atan2(y,x)para obter o ângulo do seu vetor.

atan2() funciona da seguinte maneira:

Então x = 1, y = 0 resultará em 0 e é descontínuo em x = -1, y = 0, contendo π e -π.

Agora, apenas precisamos mapear a saída atan2()para corresponder à da bússola que temos acima.

Provavelmente o mais simples de implementar é uma verificação incremental dos ângulos. Aqui estão alguns pseudo códigos que podem ser modificados facilmente para aumentar a precisão:

//start direction from the lowest value, in this case it's west with -π
enum direction {
west,
south,
east,
north
}

increment = (2PI)/direction.count
angle = atan2(y,x);
testangle = -PI + increment/2
index = 0

while angle > testangle
    index++
    if(index > direction.count - 1)
        return direction[0] //roll over
    testangle += increment


return direction[index]

Agora, para adicionar mais precisão, basta adicionar os valores à enumeração da direção.

O algoritmo funciona verificando valores crescentes ao redor da bússola para ver se nosso ângulo está em algum lugar entre a última verificação e a nova posição. É por isso que começamos com -PI + increment / 2. Queremos compensar nossas verificações para incluir espaço igual em cada direção. Algo assim:

West é dividido em dois por causa dos valores de retorno de atan2()West serem descontínuos.

Sempre que estiver lidando com vetores, considere operações fundamentais de vetores em vez de converter em ângulos em algum quadro específico.

Dado um vetor de consulta ve um conjunto de vetores de unidade s, o vetor mais alinhado é o vetor s_ique maximiza dot(v,s_i). Isso se deve ao fato de que o produto escalar dado comprimentos fixos para os parâmetros tem um máximo para vetores com a mesma direção e um mínimo para vetores com direções opostas, mudando suavemente entre eles.

Isso generaliza trivialmente em mais dimensões que duas, é extensível com direções arbitrárias e não sofre problemas específicos de quadros, como gradientes infinitos.

Em termos de implementação, isso se resumiria à associação de um vetor em cada direção cardinal a um identificador (enum, string, o que você precisar) representando essa direção. Em seguida, você percorreria seu conjunto de instruções, encontrando a que apresentasse o produto de ponto mais alto.

map<float2,Direction> candidates;
candidates[float2(1,0)] = E; candidates[float2(0,1)] = N; // etc.

for each (float2 dir in candidates)
{
    float goodness = dot(dir, v);
    if (goodness > bestResult)
    {
        bestResult = goodness;
        bestDir = candidates[dir];
    }    
}

Uma maneira que não foi mencionada aqui é tratar os vetores como números complexos. Eles não exigem trigonometria e podem ser bastante intuitivos para adicionar, multiplicar ou arredondar rotações, especialmente porque você já tem seus cabeçalhos representados como pares de números.

Caso você não esteja familiarizado com elas, as direções são expressas na forma de a + b (i), sendo um componente real eb (i) é o imaginário. Se você imaginar o plano cartesiano com o X sendo real e Y sendo imaginário, 1 seria leste (à direita), eu seria norte.

Aqui está a parte principal: As 8 direções cardinais são representadas exclusivamente com os números 1, -1 ou 0 para seus componentes reais e imaginários. Então, tudo o que você precisa fazer é reduzir as coordenadas X, Y como uma proporção e arredondar as duas para o número inteiro mais próximo para obter a direção.

NW (-1 + i)       N (i)        NE (1 + i)
W  (-1)          Origin        E  (1)
SW (-1 - i)      S (-i)        SE (1 - i)

Para a conversão de diagonal para a posição mais próxima, reduza X e Y proporcionalmente para que o valor maior seja exatamente 1 ou -1. Conjunto

// Some pseudocode

enum xDir { West = -1, Center = 0, East = 1 }
enum yDir { South = -1, Center = 0, North = 1 }

xDir GetXdirection(Vector2 heading)
{
    return round(heading.x / Max(heading.x, heading.y));
}

yDir GetYdirection(Vector2 heading)
{
    return round(heading.y / Max(heading.x, heading.y));
}

Arredondar os dois componentes do que era originalmente (10, -2) fornece 1 + 0 (i) ou 1. Portanto, a direção mais próxima é leste.

O que foi dito acima não exige o uso de uma estrutura numérica complexa, mas pensar nelas como tal torna mais rápido encontrar as oito direções principais. Você pode fazer a matemática vetorial da maneira usual se quiser obter o cabeçalho líquido de dois ou mais vetores. (Como números complexos, você não adiciona, mas multiplica para o resultado)

isso parece funcionar:

public class So49290 {
    int piece(int x,int y) {
        double angle=Math.atan2(y,x);
        if(angle<0) angle+=2*Math.PI;
        int piece=(int)Math.round(n*angle/(2*Math.PI));
        if(piece==n)
            piece=0;
        return piece;
    }
    void run(int x,int y) {
        System.out.println("("+x+","+y+") is "+s[piece(x,y)]);
    }
    public static void main(String[] args) {
        So49290 so=new So49290();
        so.run(1,0);
        so.run(1,1);
        so.run(0,1);
        so.run(-1,1);
        so.run(-1,0);
        so.run(-1,-1);
        so.run(0,-1);
        so.run(1,-1);
    }
    int n=8;
    static final String[] s=new String[] {"e","ne","n","nw","w","sw","s","se"};
}

E = 0, NE = 1, N = 2, NW = 3, W = 4, SW = 5, S = 6, SE = 7

f (x, y) = mod ((4-2 * (1 + sinal (x)) * (1 sinal (y ^ 2)) - (2 + sinal (x)) * sinal (y)

    -(1+sign(abs(sign(x*y)*atan((abs(x)-abs(y))/(abs(x)+abs(y))))

    -pi()/(8+10^-15)))/2*sign((x^2-y^2)*(x*y))),8)

Quando você quer uma string:

h_axis = ""
v_axis = ""

if (x > 0) h_axis = "E"    
if (x < 0) h_axis = "W"    
if (y > 0) v_axis = "S"    
if (y < 0) v_axis = "N"

return v_axis.append_string(h_axis)

Isso fornece constantes utilizando campos de bits:

// main direction constants
DIR_E = 0x1
DIR_W = 0x2
DIR_S = 0x4
DIR_N = 0x8
// mixed direction constants
DIR_NW = DIR_N | DIR_W    
DIR_SW = DIR_S | DIR_W
DIR_NE = DIR_N | DIR_E
DIR_SE = DIR_S | DIR_E

// calculating the direction
dir = 0x0

if (x > 0) dir |= DIR_E 
if (x < 0) dir |= DIR_W    
if (y > 0) dir |= DIR_S    
if (y < 0) dir |= DIR_N

return dir

Uma ligeira melhoria de desempenho seria colocar os <-checks no ramo else dos >-checks correspondentes , mas me abstive de fazer isso porque isso prejudica a legibilidade.