Jaki jest najlepszy sposób na przekształcenie wektora 2D w najbliższy 8-kierunkowy kierunek kompasu?

Jeśli masz wektor 2D wyrażony jako xiy, co jest dobrym sposobem na przekształcenie go w najbliższy kierunek kompasu?

na przykład

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

Najprostszym sposobem jest prawdopodobnie uzyskanie kąta wektora za pomocą atan2(), jak sugeruje Tetrad w komentarzach, a następnie skalowanie i zaokrąglanie go, np. (Pseudokod):

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

octant = round( 8 * angle / (2*PI) + 8 ) % 8Linia może wymagać pewnego wyjaśnienia. W całkiem dużo wszystkich języków, które znam, które mają to, funkcja zwraca kąt w radianach. Dzielenie go przez 2 π przekształca go z radianów na ułamki pełnego koła, a pomnożenie przez 8 następnie przekształca go w ósemki koła, które następnie zaokrąglamy do najbliższej liczby całkowitej. Na koniec zmniejszamy go modulo 8, aby zająć się zawijaniem, tak aby zarówno 0, jak i 8 były poprawnie odwzorowane na wschód.atan2()

Powodem tego + 8, który pominąłem powyżej, jest to, że w niektórych językach atan2()mogą zwracać wyniki ujemne (tj. Od - π do + π zamiast od 0 do 2 π ), a operator modulo ( %) może być zdefiniowany tak, aby zwracał wartości ujemne dla argumenty negatywne (lub jego zachowanie w przypadku argumentów negatywnych może być niezdefiniowane). Dodanie 8(tj. Jeden pełny obrót) do danych wejściowych przed redukcją zapewnia, że ​​argumenty są zawsze dodatnie, bez wpływu na wynik w jakikolwiek inny sposób.

Jeśli twój język nie zapewnia wygodnej funkcji zaokrąglania do najbliższego, możesz zamiast tego użyć skracającej konwersji liczb całkowitych i po prostu dodać 0,5 do argumentu, tak jak to:

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

Zauważ, że w niektórych językach domyślna konwersja liczb zmiennoprzecinkowych zaokrągla ujemne wartości wejściowe w górę do zera zamiast w dół, co jest kolejnym powodem, dla którego należy upewnić się, że dane wejściowe są zawsze dodatnie.

Oczywiście możesz zastąpić wszystkie wystąpienia 8tej linii inną liczbą (np. 4 lub 16, a nawet 6 lub 12, jeśli jesteś na mapie heksadecymalnej), aby podzielić okrąg na tyle kierunków. Po prostu dostosuj odpowiednio wyliczanie / tablicę.

Masz 8 opcji (lub 16 lub więcej, jeśli chcesz jeszcze dokładniejszej).

Użyj, atan2(y,x)aby uzyskać kąt dla wektora.

atan2() działa w następujący sposób:

Zatem x = 1, y = 0 spowoduje 0, i jest nieciągły przy x = -1, y = 0, zawierający zarówno π, jak i π.

Teraz musimy tylko zmapować wyjście tak, atan2()aby pasowało do kompasu, który mamy powyżej.

Prawdopodobnie najłatwiejszym do wdrożenia jest stopniowe sprawdzanie kątów. Oto pseudo kod, który można łatwo modyfikować w celu zwiększenia precyzji:

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

Teraz, aby dodać większą precyzję, po prostu dodaj wartości do wyliczenia kierunku.

Algorytm działa poprzez sprawdzanie rosnących wartości wokół kompasu, aby sprawdzić, czy nasz kąt leży gdzieś pomiędzy miejscem, w którym ostatnio sprawdzaliśmy, a nową pozycją. Dlatego zaczynamy od -PI + przyrost / 2. Chcemy przesunąć nasze kontrole, aby objąć równą przestrzeń wokół każdego kierunku. Coś takiego:

Zachód jest podzielony na dwie części, ponieważ wartości zwracane atan2()na Zachodzie są nieciągłe.

Ilekroć masz do czynienia z wektorami, rozważ podstawowe operacje wektorowe zamiast konwersji na kąty w określonej ramce.

Biorąc pod uwagę wektor zapytania vi zestaw wektorów jednostkowych s, najbardziej wyrównanym wektorem jest wektor, s_iktóry się maksymalizuje dot(v,s_i). Wynika to z tego, że iloczyn skalarny o ustalonych długościach dla parametrów ma maksimum dla wektorów o tym samym kierunku i minimum dla wektorów o przeciwnych kierunkach, płynnie zmieniających się między nimi.

Uogólnia to ogólnie na więcej niż dwa wymiary, jest rozszerzalne z dowolnymi kierunkami i nie ma problemów specyficznych dla ramki, takich jak nieskończone gradienty.

Pod względem implementacji sprowadzałoby się to do skojarzenia z wektora w każdym kardynalnym kierunku z identyfikatorem (wyliczenie, ciąg, cokolwiek potrzebujesz) reprezentującego ten kierunek. Następnie zapętlisz swój zestaw wskazówek, znajdując ten z najwyższym iloczynem kropkowym.

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

Jednym ze sposobów, o którym nie wspomniano tutaj, jest traktowanie wektorów jako liczb zespolonych. Nie wymagają trygonometrii i mogą być dość intuicyjne w dodawaniu, mnożeniu lub zaokrąglaniu rotacji, zwłaszcza, że ​​nagłówki są już reprezentowane jako pary liczb.

W przypadku, gdy nie jesteś ich zaznajomiony, kierunki są wyrażone w postaci a + b (i), a istota jest składnikiem rzeczywistym, a b (i) jest urojoną. Jeśli wyobrażasz sobie płaszczyznę kartezjańską z X będącym rzeczywistym, a Y będącym urojonym, 1 byłby na wschodzie (po prawej), byłbym na północy.

Oto kluczowa część: 8 głównych kierunków jest reprezentowanych wyłącznie przez liczby 1, -1 lub 0 dla ich rzeczywistych i urojonych składników. Wszystko, co musisz zrobić, to zmniejszyć współrzędne X, Y jako stosunek i zaokrąglić obie do najbliższej liczby całkowitej, aby uzyskać kierunek.

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

W celu zamiany kierunku na najbliższą przekątną zmniejsz proporcjonalnie zarówno X, jak i Y, aby większa wartość wynosiła dokładnie 1 lub -1. Zestaw

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

Zaokrąglenie obu składników pierwotnie (10, -2) daje 1 + 0 (i) lub 1. Więc najbliższy kierunek to wschód.

Powyższe w rzeczywistości nie wymaga użycia złożonej struktury liczbowej, ale myślenie o nich jako takich przyspiesza znalezienie 8 głównych kierunków. Możesz zrobić matematykę wektorową w zwykły sposób, jeśli chcesz uzyskać nagłówek netto dwóch lub więcej wektorów. (Jako liczby zespolone nie dodajesz, ale mnożysz dla wyniku)

to wydaje się działać:

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

Kiedy chcesz ciąg:

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)

Daje to stałe poprzez wykorzystanie pól bitowych:

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

Nieznaczną poprawą wydajności byłoby umieszczenie <-checks w gałęzi else odpowiednich >-checks, ale powstrzymałem się od robienia tego, ponieważ szkodzi to czytelności.