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

17

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
izb
sumber
apakah Anda menginginkannya sebagai string atau enum? (ya, itu penting)
Philipp
Baik, karena akan digunakan dua arah :) Meskipun jika saya harus memilih, saya akan mengambil string.
izb
1
Apakah Anda peduli dengan kinerja juga, atau hanya tentang keringkasan?
Marcin Seredynski
2
var angle = Math.atan2 (y, x); return <Direction> Math.floor ((Math.round (angle / (2 * Math.PI / 8)) + 8 + 2)% 8); Saya menggunakan yang ini
Kikaimaru
Ringkas: ditandai dengan singkatnya ekspresi atau pernyataan: bebas dari semua elaborasi dan detail berlebihan. Hanya melempar itu ke luar ...
Dialock

Jawaban:

25

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.

Ilmari Karonen
sumber
Perhatikan bahwa biasanya atan2(y,x), bukan atan2(x,y).
sam hocevar
@ Sam: Ups, sudah diperbaiki. Tentu saja, atan2(x,y)akan berhasil juga, jika seseorang hanya mendaftarkan judul kompas dalam urutan searah jarum jam mulai dari utara sebagai gantinya.
Ilmari Karonen
2
Ngomong-ngomong, saya benar-benar berpikir ini adalah jawaban yang paling mudah dan keras.
sam hocevar
1
@TheLima:octant = round(8 * angle / 360 + 8) % 8
Ilmari Karonen
1
Apakah dicatat bahwa ini dapat dengan mudah dikonversi ke 4-arah kompas: quadtant = round(4 * angle / (2*PI) + 4) % 4dan menggunakan enum: { E, N, W, S }.
Spoike
10

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

masukkan deskripsi gambar di sini

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

atan2() bekerja dengan cara berikut:

masukkan deskripsi gambar di sini

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:

masukkan deskripsi gambar di sini

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

MichaelHouse
sumber
4
Cara mudah untuk "mengubahnya menjadi sudut" adalah dengan menggunakan atan2, meskipun perlu diingat bahwa 0 derajat mungkin akan timur dan bukan utara.
Tetrad
1
Anda tidak perlu angle >=cek dalam kode di atas; misalnya jika sudutnya kurang dari 45 maka utara akan telah dikembalikan sehingga Anda tidak perlu memeriksa apakah sudut> = 45 untuk pemeriksaan timur. Demikian pula Anda tidak perlu cek sama sekali sebelum kembali ke barat - itu satu-satunya kemungkinan yang tersisa.
MrKWatkins
4
Saya tidak akan menyebut ini cara ringkas untuk mendapatkan arah. Tampaknya agak kikuk dan akan membutuhkan banyak perubahan untuk menyesuaikan ini dengan "resolusi" yang berbeda. Tidak berbicara tentang banyak ifpernyataan jika Anda ingin pergi untuk 16 arah atau lebih.
bummzack
2
Tidak perlu menormalkan vektor: sudut tetap sama atas perubahan besarnya.
Kylotan
Terima kasih @bummzack, saya telah mengedit posting untuk membuatnya lebih ringkas dan mudah untuk meningkatkan presisi hanya dengan menambahkan lebih banyak nilai enum.
MichaelHouse
8

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];
    }    
}
Lars Viklund
sumber
2
Implementasi ini juga dapat ditulis tanpa cabang dan vektor tanpa terlalu banyak kesulitan.
Promit
1
A mapdengan float2sebagai kuncinya? Ini tidak terlihat sangat serius.
sam hocevar
Itu "pseudo-code" dengan cara didaktik. Jika Anda menginginkan implementasi yang dioptimalkan secara panik, GDSE kemungkinan bukan tempat untuk mencari pasta-copy Anda. Sedangkan untuk menggunakan float2 sebagai kunci, float dapat secara tepat mewakili seluruh angka yang kami gunakan di sini, dan Anda dapat membuat komparator yang sangat baik untuk mereka. Kunci titik mengambang hanya tidak cocok jika mengandung nilai khusus atau Anda mencoba mencari hasil yang dihitung. Iterasi melalui urutan asosiatif baik-baik saja. Saya bisa saja menggunakan pencarian linear dalam sebuah array, tentu saja, tapi itu hanya akan sia-sia.
Lars Viklund
3

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)

ChrisC
sumber
1
Ini luar biasa, tetapi membuat kesalahan serupa dengan yang saya buat dalam usaha saya sendiri. Jawabannya dekat tetapi tidak benar. Sudut batas antara E dan NE adalah 22,5 derajat, tetapi ini terpotong pada 26,6 derajat.
izb
Max(x, y)seharusnya Max(Abs(x, y))bekerja untuk kuadran negatif. Saya mencobanya dan mendapatkan hasil yang sama dengan izb - ini mengubah arah kompas pada sudut yang salah. Saya kira itu akan beralih ketika heading.y / heading.x melintasi 0,5 (jadi nilai bulat beralih dari 0 ke 1), yaitu arctan (0,5) = 26,565 °.
amitp
Cara berbeda untuk menggunakan bilangan kompleks di sini adalah dengan mengamati bahwa penggandaan bilangan kompleks melibatkan rotasi. Jika Anda membuat bilangan kompleks yang mewakili 1/8 rotasi di sekitar lingkaran, maka setiap kali Anda mengalikannya, Anda memindahkan satu oktan. Jadi Anda dapat bertanya: dapatkah kita menghitung berapa banyak perkalian yang diperlukan untuk pergi dari Timur ke pos saat ini? Jawaban untuk "berapa kali kita harus memperbanyak dengan ini" adalah logaritma . Jika Anda mencari logaritma untuk bilangan kompleks ... ia menggunakan atan2. Jadi ini akhirnya setara dengan jawaban Ilmari.
amitp
-2

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"};
}
Ray Tayek
sumber
mengapa ini ditolak?
Ray Tayek
Kemungkinan besar karena tidak ada penjelasan di balik kode Anda. Mengapa ini solusinya dan bagaimana cara kerjanya?
Vaillancourt
apakah kamu menjalankannya?
Ray Tayek
Tidak, dan diberi nama kelas, saya berasumsi Anda melakukannya dan itu berhasil. Dan itu bagus. Tetapi Anda bertanya mengapa orang-orang menolak dan saya menjawab; Saya tidak pernah menyiratkan bahwa itu tidak berhasil :)
Vaillancourt
-2

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)
theodore panagos
sumber
Untuk saat ini, ini hanya sekelompok karakter yang tidak masuk akal; mengapa ini solusi yang akan bekerja untuk pertanyaan itu, bagaimana cara kerjanya?
Vaillancourt
Saya menulis formula ketika saya menulis jn excel dan bekerja dengan sempurna.
theodore panagos
= MOD ((4-2 * (1 + SIGN (X1)) * (1-SIGN (Y1 ^ 2)) - (2 + SIGN (X1)) * SIGN (Y1) - (1 + SIGN (ABS (SIGN) (X1 * Y1) * ATAN ((ABS (X1) -ABS (Y1)) / (ABS (X1) + ABS (Y1)))) - PI () / (8 + 10 ^ -15))) / 2 * SIGN ((X1 ^ 2-Y1 ^ 2) * (X1 * Y1))), 8)
theodore panagos
-4

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.

Philipp
sumber
2
Maaf, tapi itu tidak memberikan jawaban tepat yang saya cari. Dengan kode itu hanya akan menghasilkan "N" jika vektor tepat utara, dan NE atau NW jika x adalah nilai lainnya. Yang saya butuhkan adalah arah kompas terdekat, misalnya jika vektor lebih dekat ke N daripada NW maka akan menghasilkan N.
izb
Apakah ini benar-benar memberikan arah terdekat? Tampaknya vektor (0,00001,100) akan memberi Anda timur laut. sunting: Anda mengalahkan saya untuk itu izb.
CiscoIPPhone
Anda tidak mengatakan bahwa Anda menginginkan arah terdekat.
Philipp
1
Maaf, saya menyembunyikannya di judul. Seharusnya lebih jelas di badan pertanyaan
izb
1
Bagaimana dengan menggunakan norma tak terbatas? Membagi dengan max (abs (vector.components)) memberi Anda vektor dinormalisasi sehubungan dengan norma itu. Sekarang Anda bisa menulis tabel check-up kecil berdasarkan if (x > 0.9) dir |= DIR_Edan sisanya. Seharusnya lebih baik daripada kode asli Phillipp dan sedikit lebih murah daripada menggunakan norma L2 dan atan2. Mungkin .. atau mungkin tidak.
teodron