Apa cara terbaik untuk mengubah vektor 2D ke arah kompas 8 arah terdekat?

Jika Anda memiliki vektor 2D yang dinyatakan sebagai x dan y, apa cara yang baik untuk mengubahnya menjadi arah kompas terdekat?

misalnya

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

Cara paling sederhana mungkin untuk mendapatkan sudut vektor menggunakan atan2(), seperti yang Tetrad sarankan dalam komentar, dan kemudian skala dan bulatkan itu, misalnya (kodesemu):

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

The octant = round( 8 * angle / (2*PI) + 8 ) % 8garis mungkin perlu beberapa penjelasan. Dalam hampir semua bahasa yang saya tahu bahwa memilikinya, yang atan2()fungsi mengembalikan sudut dalam radian. Membaginya dengan 2 π mengubahnya dari radian menjadi pecahan dari lingkaran penuh, dan mengalikannya dengan 8 lalu mengubahnya menjadi seperdelapan lingkaran, yang kemudian kita bulatkan ke bilangan bulat terdekat. Akhirnya, kita menguranginya modulo 8 untuk menangani wrap-around, sehingga baik 0 dan 8 dipetakan dengan benar ke timur.

Alasan untuk + 8, yang saya lewati di atas, adalah bahwa dalam beberapa bahasa atan2()dapat mengembalikan hasil negatif (yaitu dari - π ke + π daripada dari 0 ke 2 π ) dan operator modulo ( %) dapat didefinisikan untuk mengembalikan nilai negatif untuk argumen negatif (atau perilakunya untuk argumen negatif mungkin tidak terdefinisi). Menambahkan 8(yaitu satu putaran penuh) ke input sebelum reduksi memastikan bahwa argumen selalu positif, tanpa mempengaruhi hasilnya dengan cara lain.

Jika bahasa Anda tidak memberikan fungsi bulat-ke-terdekat yang nyaman, Anda dapat menggunakan konversi integer terpotong sebagai gantinya dan hanya menambahkan 0,5 pada argumen, seperti ini:

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

Perhatikan bahwa, dalam beberapa bahasa, konversi float-to-integer default memasukkan input negatif ke arah nol daripada ke bawah, yang merupakan alasan lain untuk memastikan bahwa input selalu positif.

Tentu saja, Anda dapat mengganti semua kemunculan 8pada baris itu dengan nomor lain (mis. 4 atau 16, atau bahkan 6 atau 12 jika Anda berada di peta hex) untuk membagi lingkaran ke dalam banyak arah. Cukup sesuaikan enum / array yang sesuai.

Anda memiliki 8 opsi (atau 16 atau lebih jika Anda menginginkan presisi yang lebih baik).

Gunakan atan2(y,x)untuk mendapatkan sudut vektor Anda.

atan2() bekerja dengan cara berikut:

Jadi x = 1, y = 0 akan menghasilkan 0, dan itu terputus-putus pada x = -1, y = 0, yang mengandung π dan -π.

Sekarang kita hanya perlu memetakan output atan2()untuk mencocokkan dengan kompas yang kita miliki di atas.

Kemungkinan yang paling sederhana untuk diterapkan adalah pemeriksaan sudut yang bertambah. Berikut beberapa kode semu yang mudah dimodifikasi untuk meningkatkan presisi:

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

Sekarang untuk menambahkan lebih presisi, cukup tambahkan nilai ke arah enum.

Algoritma bekerja dengan memeriksa nilai yang meningkat di sekitar kompas untuk melihat apakah sudut kita berada di suatu tempat antara tempat kita terakhir diperiksa dan posisi baru. Itu sebabnya kita mulai dari -PI + increment / 2. Kami ingin mengimbangi cek kami untuk memasukkan ruang yang sama di sekitar setiap arah. Sesuatu seperti ini:

Barat dipecah menjadi dua karena nilai-nilai kembali atan2()di Barat terputus-putus.

Setiap kali Anda berurusan dengan vektor, pertimbangkan operasi vektor dasar alih-alih mengonversi ke sudut dalam beberapa bingkai tertentu.

Diberikan vektor kueri vdan sekumpulan vektor satuan s, vektor yang paling selaras adalah vektor s_iyang memaksimalkan dot(v,s_i). Hal ini disebabkan bahwa produk titik yang diberikan panjang tetap untuk parameter memiliki maksimum untuk vektor dengan arah yang sama dan minimum untuk vektor dengan arah yang berlawanan, berubah dengan peralihan yang lancar.

Ini digeneralisasi secara sepele menjadi lebih dari dua dimensi, dapat diperluas dengan arah yang sewenang-wenang dan tidak mengalami masalah kerangka khusus seperti gradien tak terbatas.

Dari segi implementasi, ini akan bermuara pada penggabungan dari vektor di setiap arah mata angin dengan pengidentifikasi (enum, string, apa pun yang Anda butuhkan) mewakili arah itu. Anda kemudian akan mengulang set arah Anda, menemukan satu dengan produk titik tertinggi.

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

Salah satu cara yang belum disebutkan di sini adalah memperlakukan vektor sebagai bilangan kompleks. Mereka tidak memerlukan trigonometri dan bisa sangat intuitif untuk menambah, mengalikan, atau membulatkan rotasi, terutama karena Anda sudah memiliki judul yang direpresentasikan sebagai pasangan angka.

Jika Anda tidak terbiasa dengan mereka, arah ditunjukkan dalam bentuk a + b (i) dengan menjadi komponen nyata dan b (i) adalah imajiner. Jika Anda membayangkan pesawat cartesian dengan X menjadi nyata dan Y menjadi imajiner, 1 akan menjadi timur (kanan), saya akan berada di utara.

Inilah bagian kuncinya: 8 arah mata angin diwakili secara eksklusif dengan angka 1, -1 atau 0 untuk komponen nyata dan imajiner mereka. Jadi yang harus Anda lakukan adalah mengurangi koordinat X, Y sebagai rasio dan membulatkan keduanya ke bilangan bulat terdekat untuk mendapatkan arah.

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

Untuk konversi diagonal menuju ke terdekat, kurangi X dan Y secara proporsional sehingga nilai yang lebih besar tepat 1 atau -1. Set

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

Membulatkan kedua komponen dari apa yang semula (10, -2) memberi Anda 1 + 0 (i) atau 1. Jadi arah terdekat adalah timur.

Di atas sebenarnya tidak memerlukan penggunaan struktur bilangan kompleks, tetapi memikirkan mereka seperti itu membuatnya lebih cepat untuk menemukan 8 arah mata angin. Anda dapat melakukan matematika vektor dengan cara biasa jika Anda ingin mendapatkan judul bersih dari dua vektor atau lebih. (Sebagai bilangan kompleks, Anda tidak menambahkan, tetapi gandakan hasilnya)

ini sepertinya berhasil:

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

Saat Anda menginginkan 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)

Ini memberi Anda konstanta dengan menggunakan bitfield:

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

Sedikit peningkatan kinerja adalah dengan memasukkan <-check ke cabang-lain dari >-check yang sesuai , tetapi saya menahan diri untuk tidak melakukan itu karena itu merusak keterbacaan.