Membandingkan sudut dan menghitung perbedaannya

Saya ingin membandingkan sudut dan mendapatkan gagasan tentang jarak di antara mereka. Untuk aplikasi ini, saya bekerja dalam derajat, tetapi itu juga berfungsi untuk radian dan lulusan. Masalah dengan sudut adalah bahwa mereka bergantung pada aritmatika modular, yaitu 0-360 derajat.

Katakan satu sudut di 15 derajat dan satu di 45. Perbedaannya adalah 30 derajat, dan sudut 45 derajat lebih besar dari 15 derajat.

Tapi, ini rusak ketika Anda memiliki, katakanlah, 345 derajat dan 30 derajat. Meskipun mereka membandingkan dengan benar, perbedaan di antara mereka adalah 315 derajat, bukan 45 derajat yang benar.

Bagaimana saya bisa memecahkan masalah ini? Saya bisa menulis kode algoritmik:

if(angle1 > angle2) delta_theta = 360 - angle2 - angle1;
else delta_theta = angle2 - angle1;

Tapi saya lebih suka solusi yang menghindari membandingkan / cabang, dan bergantung sepenuhnya pada aritmatika.

Inilah versi saya yang disederhanakan, tanpa cabang, bebas-perbandingan, tanpa min / maks:

angle = 180 - abs(abs(a1 - a2) - 180); 

Menghapus modulo, karena inputnya cukup terbatas (terima kasih kepada Martin karena menunjukkannya).

Dua abs, tiga kurangi.

Meskipun mereka membandingkan dengan benar, perbedaan di antara mereka adalah 315 derajat, bukan 45 derajat yang benar.

Apa yang membuat Anda berpikir 315 salah? Di satu arah, itu adalah 315 derajat, di arah lain, itu 45. Anda ingin memilih mana yang terkecil dari 2 sudut yang mungkin dan ini tampaknya secara intrinsik memerlukan persyaratan. Anda tidak dapat menyelesaikannya dengan membungkus aritmatika (mis. Melalui operator modulus) karena ketika Anda secara bertahap meningkatkan satu sudut, sudut di antara mereka tumbuh hingga mencapai 180 dan kemudian mulai menurun.

Saya pikir Anda harus memeriksa kedua sudut dan memutuskan arah mana yang ingin Anda ukur, atau menghitung kedua arah dan memutuskan hasil mana yang Anda inginkan.

Selalu ada trik melakukan kedua cabang dan membiarkan hasil perbandingan memilih satu:

delta_theta = (angle1 > angle2) * (360 - angle2 - angle1)
              + (angle2 > angle1) * (angle2 - angle1);

Saya tidak tahu cara untuk melakukannya tanpa perbandingan , tetapi biasanya cabang adalah apa yang membuat kode lambat dan panjang, bukan perbandingan. Setidaknya menurut saya, ini lebih mudah dibaca daripada jawaban Martin (setiap programmer C yang baik akan mengenalinya sebagai setara tanpa cabang dan melihat apa yang dilakukannya), tetapi juga kurang efisien.

Tapi seperti yang saya katakan di komentar saya, algoritma branchless bagus untuk prosesor dengan saluran pipa yang dalam dan prediksi yang buruk - mikrokontroler biasanya memiliki pipa kecil, dan PC desktop biasanya memiliki prediksi yang baik, jadi kecuali Anda menargetkan konsol game, versi percabangan kemungkinan rute terbaik jika mengurangi jumlah instruksi.

Seperti biasa, pembuatan profil - yang mungkin sesederhana penghitungan op untuk sistem Anda - akan memberi Anda jawaban nyata.

Dengan asumsi true evaluate to -1 dan false mengevaluasi to 0, dan '~', '&' dan '|' bitwise tidak , dan dan atau operator masing-masing, dan kami bekerja dengan aritmatika dua-pelengkap:

temp1 := angle1 > angle2
/* most processors can do this without a jump; for example, under the x86 family,
   it's the result of CMP; SETLE; SUB .., 1 instructions */
temp2 := angle1 - angle2
temp1 := (temp1 & temp2) | (~temp1 & -temp2)
/* in x86 again: only SUB, AND, OR, NOT and NEG are used, no jumps
   at this point, we have the positive difference between the angles in temp1;
   we can now do the same trick again */
temp2 := temp1 > 180
temp2 := (temp2 & temp1) | (~temp2 & (360 - temp1))
/* the result is in temp2 now */

Bagaimana dengan ini?

min( (a1-a2+360)%360, (a2-a1+360)%360 )

Penambahan 360 ada untuk menghindari perbedaan negatif, karena modulo dari angka negatif mengembalikan hasil negatif. Maka Anda mendapatkan yang lebih kecil dari dua hasil yang mungkin.

Masih ada keputusan implisit, tetapi saya tidak tahu bagaimana menghindarinya. Pada dasarnya Anda membandingkan dua sudut dengan menghitung perbedaan searah jarum jam atau berlawanan arah jarum jam, dan tampaknya Anda secara eksplisit menginginkan yang lebih kecil dari dua perbedaan ini. Saya tidak tahu bagaimana mendapatkan hasil itu tanpa membandingkannya. Yaitu, tanpa menggunakan "abs", "min", "max" atau operator serupa.

Sementara pertanyaan Anda tidak merujuk mereka, saya akan bekerja pada asumsi bahwa pertanyaan perhitungan sudut Anda berasal dari keinginan untuk mengetahui sudut minimum antara dua vektor .

Perhitungan itu mudah. Dengan asumsi A dan B adalah vektor Anda:

angle_between = acos( Dot( A.normalized, B.normalized ) )

Jika Anda tidak memiliki vektor dan ingin menggunakan pendekatan ini, Anda bisa membuat vektor satuan panjang dengan sudut pandang Anda new Vector2( cos( angle ), sin ( angle ) ).

Pada dasarnya sama dengan jawaban JasonD, kecuali menggunakan operasi bitwise bukan fungsi nilai absolut.

Ini dengan asumsi Anda memiliki bilangan bulat pendek 16-bit!

short angleBetween(short a,short b) {
    short x = a - b;
    short y = x >> 15;
    y = ((x + y) ^ y) - 180;
    return 180 - ((x + y) ^ y);
}

kupikir

delta = (a2 + Math.ceil( -a2 / 360 ) * 360) - (a1 + Math.ceil( -a1 / 360 ) * 360);

Karena Anda hanya peduli tentang menghilangkan cabang dan operasi "kompleks" di luar aritmatika, saya akan merekomendasikan ini:

min(abs(angle1 - angle2), abs(angle2 - angle1))

Anda masih membutuhkan absdi sana meskipun semua sudut positif. Jika tidak, hasil paling negatif akan selalu dipilih (dan akan selalu ada tepat satu jawaban negatif untuk positif, unik, dan b ketika membandingkan ab dan ba).

Catatan: Ini tidak akan mempertahankan arah antara angle1 dan angle2. Terkadang Anda membutuhkannya untuk tujuan AI.

Ini mirip dengan jawaban CeeJay, tetapi menghilangkan semua modulos. Saya tidak tahu berapa biaya siklusnya abs, tetapi saya akan menebak itu 1 atau 2. Sulit untuk mengatakan berapa biayanya min. Mungkin 3? Jadi bersama dengan 1 siklus per pengurangan, baris ini harus memiliki biaya sekitar 4 hingga 9.

Dapatkan sudut relatif yang lebih kecil dalam formulir yang ditandatangani (+/-), dari perspektif miliki ke inginkan :

• paling banyak 180 derajat | Radian PI
• -ditandatangani jika berlawanan arah jarum jam
• + ditandatangani jika searah jarum jam

Derajat

PITAU = 360 + 180 # for readablility
signed_diff = ( want - have + PITAU ) % 360 - 180

Radian

PI = 3.14; TAU = 2*PI; PITAU = PI + TAU;
signed_diff = ( want - have + PITAU ) % TAU - PI

Alasan

Saya menemukan utas ini setelah saya menemukan jawabannya, mencari solusi yang menghindari modulo; sejauh ini saya belum menemukannya . Solusi ini adalah untuk melestarikan tanda perspektif, ketika @ jacob-phillips menanyakan komentar ini . Ada solusi yang lebih murah jika Anda hanya membutuhkan sudut unsigned terpendek.

Ini pertanyaan lama tapi saya mengalami kasus yang sama - harus mendapatkan perbedaan sudut yang ditandatangani dan lebih disukai tanpa cabang dan matematika yang berat. Inilah yang akhirnya saya dapatkan:

int d = (a - b) + 180 + N * 360; // N = 1, 2 or more.
int r = (d / 360) * 360;
return (d - r) - 180;

Batasannya adalah bahwa 'b' tidak boleh memiliki lebih dari rotasi 'N' dibandingkan dengan 'a'. Jika Anda tidak dapat memastikannya dan dapat mengizinkan operasi tambahan, gunakan ini sebagai baris pertama:

int d = ((a % 360) - (b % 360)) + 540;

Saya mendapat ide dari komentar ke-13 posting ini: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-two-angles-keeping-the- tanda

saya kira saya bisa mengatakan

angle1=angle1%360;
angle2=angle2%360;
var distance = Math.abs(angle1-angle2);
//edited
if(distance>180)
  distance=360-distance;

tentu saja, mengingat sudut diukur dalam derajat.