Quelle est la meilleure façon de transformer un vecteur 2D dans la direction de la boussole à 8 directions la plus proche?

Si vous avez un vecteur 2D exprimé en x et y, quelle est la bonne façon de le transformer dans la direction de la boussole la plus proche?

par exemple

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

Le moyen le plus simple est probablement d'obtenir l'angle du vecteur en utilisant atan2(), comme Tetrad le suggère dans les commentaires, puis de le mettre à l'échelle et de l'arrondir, par exemple (pseudocode):

// 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];

La octant = round( 8 * angle / (2*PI) + 8 ) % 8ligne pourrait avoir besoin d'explications. Dans à peu près toutes les langues que je connais, la atan2()fonction renvoie l'angle en radians. Le diviser par 2 π le convertit des radians en fractions d'un cercle complet, et le multiplier par 8 le convertit ensuite en huitièmes de cercle, que nous arrondissons ensuite à l'entier le plus proche. Enfin, nous le réduisons modulo 8 pour prendre en charge le bouclage, afin que les deux 0 et 8 soient correctement mappés vers l'est.

La raison de la + 8, que j'ai ignorée ci-dessus, est que dans certaines langues atan2()peut retourner des résultats négatifs (c'est-à-dire de - π à + π plutôt que de 0 à 2 π ) et l'opérateur modulo ( %) peut être défini pour renvoyer des valeurs négatives pour arguments négatifs (ou son comportement pour les arguments négatifs peut être indéfini). L'ajout 8(c'est-à-dire un tour complet) à l'entrée avant la réduction garantit que les arguments sont toujours positifs, sans affecter le résultat d'une autre manière.

Si votre langue ne fournit pas une fonction arrondie au plus proche, vous pouvez utiliser une conversion d'entier tronqué à la place et ajouter simplement 0,5 à l'argument, comme ceci:

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

Notez que, dans certaines langues, la conversion flottante en entier par défaut arrondit les entrées négatives vers le haut plutôt que vers le bas, ce qui est une autre raison pour s'assurer que l'entrée est toujours positive.

Bien sûr, vous pouvez remplacer toutes les occurrences de 8sur cette ligne par un autre nombre (par exemple 4 ou 16, ou même 6 ou 12 si vous êtes sur une carte hexadécimale) pour diviser le cercle dans autant de directions. Ajustez simplement l'énumération / le tableau en conséquence.

Vous avez 8 options (ou 16 ou plus si vous voulez une précision encore plus fine).

Utilisez atan2(y,x)pour obtenir l'angle de votre vecteur.

atan2() fonctionne de la manière suivante:

Donc x = 1, y = 0 donnera 0, et il est discontinu à x = -1, y = 0, contenant à la fois π et -π.

Maintenant, nous avons juste besoin de mapper la sortie de atan2()pour correspondre à celle de la boussole que nous avons ci-dessus.

Le plus simple à mettre en œuvre est probablement une vérification incrémentielle des angles. Voici un pseudo-code qui peut être facilement modifié pour une précision accrue:

//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]

Maintenant, pour ajouter plus de précision, ajoutez simplement les valeurs à l'énumération de la direction.

L'algorithme fonctionne en vérifiant les valeurs croissantes autour de la boussole pour voir si notre angle se situe quelque part entre l'endroit où nous avons vérifié pour la dernière fois et la nouvelle position. C'est pourquoi nous commençons à -PI + incrément / 2. Nous voulons compenser nos contrôles pour inclure un espace égal autour de chaque direction. Quelque chose comme ça:

West est divisé en deux car les valeurs de retour de atan2()at West sont discontinues.

Chaque fois que vous traitez avec des vecteurs, envisagez des opérations vectorielles fondamentales au lieu de convertir en angles dans un cadre particulier.

Étant donné un vecteur de requête vet un ensemble de vecteurs unitaires s, le vecteur le plus aligné est le vecteur s_iqui maximisedot(v,s_i) . Cela est dû au fait que le produit scalaire donné des longueurs fixes pour les paramètres a un maximum pour les vecteurs avec la même direction et un minimum pour les vecteurs avec des directions opposées, changeant en douceur entre les deux.

Cela se généralise trivialement en plus de deux dimensions, est extensible avec des directions arbitraires et ne souffre pas de problèmes spécifiques à l'image comme des gradients infinis.

En termes d'implémentation, cela reviendrait à associer à partir d'un vecteur dans chaque direction cardinale un identifiant (énum, ​​chaîne, tout ce dont vous avez besoin) représentant cette direction. Vous feriez ensuite une boucle sur votre ensemble de directions, en trouvant celle avec le produit scalaire le plus élevé.

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];
    }    
}

Une façon qui n'a pas été mentionnée ici est de traiter les vecteurs comme des nombres complexes. Ils ne nécessitent pas de trigonométrie et peuvent être assez intuitifs pour ajouter, multiplier ou arrondir les rotations, d'autant plus que vos en-têtes sont déjà représentés sous forme de paires de nombres.

Dans le cas où vous ne les connaissez pas, les directions sont exprimées sous la forme a + b (i) avec a étant la composante réelle et b (i) est l'imaginaire. Si vous imaginez le plan cartésien avec X réel et Y imaginaire, 1 serait à l'est (à droite), je serais au nord.

Voici la partie clé: Les 8 directions cardinales sont représentées exclusivement avec les nombres 1, -1 ou 0 pour leurs composantes réelles et imaginaires. Donc, tout ce que vous avez à faire est de réduire vos coordonnées X, Y comme un rapport et d'arrondir les deux au nombre entier le plus proche pour obtenir la direction.

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

Pour la conversion de la diagonale en tête vers la plus proche, réduisez X et Y proportionnellement pour que la plus grande valeur soit exactement 1 ou -1. Ensemble

// 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));
}

Arrondir les deux composantes de ce qui était à l'origine (10, -2) vous donne 1 + 0 (i) ou 1. La direction la plus proche est donc l'est.

Ce qui précède ne nécessite pas réellement l'utilisation d'une structure numérique complexe, mais en les considérant comme tels, il est plus rapide de trouver les 8 directions cardinales. Vous pouvez effectuer des calculs vectoriels de la manière habituelle si vous souhaitez obtenir l'en-tête net de deux ou plusieurs vecteurs. (En tant que nombres complexes, vous n'ajoutez pas, mais multipliez pour le résultat)

cela semble fonctionner:

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 + signe (x)) * (1-signe (y ^ 2)) - (2 + signe (x)) * signe (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)

Lorsque vous voulez une chaîne:

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)

Cela vous donne des constantes en utilisant des champs 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

Une légère amélioration des performances serait de < -checks dans la branche else des >-checks correspondants , mais je me suis abstenu de le faire car cela nuit à la lisibilité.