Wie lässt sich ein 2D-Vektor am besten in die nächste 8-Wege-Kompassrichtung umwandeln?

Wenn Sie einen 2D-Vektor haben, der als x und y ausgedrückt wird, wie können Sie diesen in die nächste Kompassrichtung umwandeln?

z.B

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

Am einfachsten ist es wahrscheinlich, den Winkel des Vektors mit atan2()zu berechnen, wie Tetrad in den Kommentaren angibt, und ihn dann zu skalieren und zu runden, z. B. (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];

Die octant = round( 8 * angle / (2*PI) + 8 ) % 8Zeile benötigt möglicherweise eine Erklärung. In so ziemlich allen Sprachen, die ich kenne, gibt die atan2()Funktion den Winkel im Bogenmaß zurück. Teilen Sie es durch 2 π wird es vom Bogenmaß in Bruchteile eines vollen Kreises umgewandelt und durch Multiplizieren mit 8 in Achtel eines Kreises umgewandelt, den wir dann auf die nächste ganze Zahl runden. Schließlich reduzieren wir es modulo 8, um den Wrap-Around zu erledigen, damit sowohl 0 als auch 8 korrekt nach Osten abgebildet werden.

Der Grund für das + 8, was ich oben übersprungen habe, ist, dass in einigen Sprachen atan2()negative Ergebnisse (dh von - π bis + π statt von 0 bis 2 π ) zurückgegeben werden können und der Modulo-Operator ( %) definiert werden kann, um negative Werte für zurückzugeben negative Argumente (oder sein Verhalten für negative Argumente kann undefiniert sein). Das Hinzufügen 8(dh eine volle Umdrehung) zu der Eingabe vor dem Reduzieren stellt sicher, dass die Argumente immer positiv sind, ohne das Ergebnis auf andere Weise zu beeinflussen.

Wenn Ihre Sprache keine bequeme Funktion zum Aufrunden der nächsten Zahl bietet, können Sie stattdessen eine Ganzzahlumwandlung mit Kürzung verwenden und dem Argument einfach 0,5 hinzufügen, wie folgt:

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

Beachten Sie, dass in einigen Sprachen bei der Standardkonvertierung von Float in Integer negative Eingaben eher in Richtung Null als nach unten gerundet werden. Dies ist ein weiterer Grund, um sicherzustellen, dass die Eingabe immer positiv ist.

Natürlich können Sie alle Vorkommen 8in dieser Zeile durch eine andere Zahl ersetzen (z. B. 4 oder 16 oder sogar 6 oder 12, wenn Sie sich auf einer Hex-Karte befinden), um den Kreis in so viele Richtungen zu unterteilen. Passen Sie einfach die Enumeration / das Array entsprechend an.

Sie haben 8 Optionen (oder 16 oder mehr, wenn Sie eine noch feinere Präzision wünschen).

Verwenden Sie atan2(y,x), um den Winkel für Ihren Vektor zu ermitteln.

atan2() funktioniert wie folgt:

Also ergibt x = 1, y = 0 0 und es ist diskontinuierlich bei x = -1, y = 0 und enthält sowohl π als auch -π.

Jetzt müssen wir nur noch die Ausgabe von atan2()zuordnen, um sie mit der des oben angegebenen Kompasses abzugleichen.

Die wahrscheinlich einfachste Implementierung ist eine inkrementelle Überprüfung der Winkel. Hier ist ein Pseudocode, der leicht geändert werden kann, um die Genauigkeit zu erhöhen:

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

Um die Genauigkeit zu erhöhen, fügen Sie einfach die Werte zur Richtungsaufzählung hinzu.

Der Algorithmus überprüft auf dem Kompass zunehmende Werte, um festzustellen, ob unser Winkel irgendwo zwischen dem Ort der letzten Überprüfung und der neuen Position liegt. Deshalb fangen wir bei -PI + increment / 2 an. Wir möchten unsere Schecks so ausgleichen, dass sie in jede Richtung den gleichen Abstand einschließen. Etwas wie das:

West ist zweigeteilt, da die Rückgabewerte von atan2()at West diskontinuierlich sind.

Wenn Sie sich mit Vektoren beschäftigen, sollten Sie grundlegende Vektoroperationen in Betracht ziehen, anstatt sie in Winkel in einem bestimmten Frame umzuwandeln.

Bei einem Abfragevektor vund einer Menge von Einheitsvektoren sist der am meisten ausgerichtete Vektor der Vektor s_i, der maximiert dot(v,s_i). Dies liegt daran, dass das für die Parameter festgelegte Skalarprodukt ein Maximum für Vektoren mit derselben Richtung und ein Minimum für Vektoren mit entgegengesetzten Richtungen aufweist, die sich gleichmäßig dazwischen ändern.

Dies verallgemeinert sich trivial in mehr als zwei Dimensionen, ist mit beliebigen Richtungen erweiterbar und leidet nicht an rahmenspezifischen Problemen wie unendlichen Verläufen.

In Bezug auf die Implementierung würde dies darauf hinauslaufen, ausgehend von einem Vektor in jeder Himmelsrichtung einen Bezeichner (enum, string, was auch immer Sie benötigen) zuzuordnen, der diese Richtung darstellt. Sie würden dann eine Schleife über Ihren Richtungssatz ziehen und den mit dem höchsten Skalarprodukt finden.

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

Eine Möglichkeit, die hier nicht erwähnt wurde, besteht darin, die Vektoren als komplexe Zahlen zu behandeln. Sie erfordern keine Trigonometrie und können sehr intuitiv zum Hinzufügen, Multiplizieren oder Runden von Rotationen verwendet werden, zumal Ihre Überschriften bereits als Zahlenpaare dargestellt sind.

Falls Sie mit ihnen nicht vertraut sind, werden die Richtungen in Form von a + b (i) ausgedrückt, wobei a die reale Komponente ist und b (i) die imaginäre. Wenn Sie sich die kartesische Ebene vorstellen, bei der X real und Y imaginär ist, wäre 1 östlich (rechts), ich wäre nördlich.

Hier ist der Schlüsselteil: Die 8 Himmelsrichtungen werden ausschließlich mit den Zahlen 1, -1 oder 0 für ihre realen und imaginären Komponenten dargestellt.Alles, was Sie tun müssen, ist, Ihre X-, Y-Koordinaten als Verhältnis zu reduzieren und beide auf die nächste ganze Zahl zu runden, um die Richtung zu erhalten.

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

Reduzieren Sie für die Konvertierung von Überschrift zu nächster Diagonale X und Y proportional, sodass der größere Wert genau 1 oder -1 ist. einstellen

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

Wenn Sie beide Komponenten von dem, was ursprünglich (10, -2) war, runden, erhalten Sie 1 + 0 (i) oder 1. Die nächste Richtung ist also Ost.

Das obige erfordert nicht die Verwendung einer komplexen Zahlenstruktur, aber wenn man sich diese als solche ansieht, ist es schneller, die 8 Himmelsrichtungen zu finden. Sie können Vektormathematik auf die übliche Weise ausführen, wenn Sie die Netzüberschrift von zwei oder mehr Vektoren erhalten möchten. (Als komplexe Zahlen addieren Sie nicht, sondern multiplizieren das Ergebnis.)

das scheint zu funktionieren:

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

Wenn Sie eine Zeichenfolge möchten:

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)

Dies gibt Ihnen Konstanten durch Verwendung von Bitfeldern:

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

Eine leichte Leistungsverbesserung wäre, die <-checks in den else-Zweig der entsprechenden >-checks zu setzen, aber ich habe darauf verzichtet, weil dies die Lesbarkeit beeinträchtigt.