Porównywanie kątów i wypracowywanie różnicy

Chcę porównać kąty i poznać odległość między nimi. W przypadku tej aplikacji pracuję w stopniach, ale działałoby to również w radianach i gradach. Problem z kątami polega na tym, że zależą one od arytmetyki modułowej, tj. 0–360 stopni.

Powiedzmy, że jeden kąt wynosi 15 stopni, a drugi 45. Różnica wynosi 30 stopni, a kąt 45 stopni jest większy niż 15 stopni.

Ale to się psuje, gdy masz, powiedzmy, 345 stopni i 30 stopni. Mimo że porównują się prawidłowo, różnica między nimi wynosi 315 stopni zamiast prawidłowych 45 stopni.

Jak mogę to rozwiązać? Mógłbym napisać kod algorytmiczny:

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

Ale wolałbym rozwiązanie, które unika porównań / gałęzi i opiera się całkowicie na arytmetyki.

Oto moja uproszczona, bez rozgałęzienia, bez porównania, bez wersji min / max:

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

Usunięto moduł, ponieważ dane wejściowe są wystarczająco ograniczone (dzięki Martinowi za wskazanie tego).

Dwa abs, trzy odejmowania.

Mimo że porównują się prawidłowo, różnica między nimi wynosi 315 stopni zamiast prawidłowych 45 stopni.

Co sprawia, że ​​uważasz, że 315 jest niepoprawny? W jednym kierunku wynosi 315 stopni, w drugim - 45. Chcesz wybrać, który jest najmniejszy z 2 możliwych kątów i wydaje się, że z natury wymaga warunkowego. Nie można go rozwiązać za pomocą arytmetyki zawijania (tj. Za pomocą operatora modułu), ponieważ wraz ze stopniowym zwiększaniem jednego kąta kąt między nimi rośnie, aż osiągnie 180, a następnie zaczyna spadać.

Myślę, że albo musisz sprawdzić oba kąty i zdecydować, który kierunek chcesz zmierzyć, albo obliczyć oba kierunki i zdecydować, który wynik chcesz.

Zawsze istnieje sztuczka polegająca na zrobieniu obu gałęzi i pozostawieniu jednego z wyników porównania:

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

Nie wiem, jak to zrobić bez porównań , ale zwykle gałąź powoduje, że kod jest wolny i długi, a nie porównanie. Przynajmniej moim zdaniem jest to bardziej czytelne niż odpowiedź Martina (każdy dobry programista C rozpozna go jako ekwiwalent bezgałęziowy i zobaczy, co robi), ale również mniej wydajny.

Ale, jak powiedziałem w moim komentarzu, algorytmy bez rozgałęzień są dobre na procesorach z głębokimi potokami i złymi prognozami - mikrokontroler ma zwykle mały potok, a komputer stacjonarny zwykle ma dobre przewidywanie, więc jeśli nie celujesz w konsolę do gier, wersja rozgałęziona jest prawdopodobnie najlepszą trasą, jeśli zmniejsza liczbę instrukcji.

Jak zawsze profilowanie - które może być tak proste jak liczenie operacji dla twojego systemu - da ci prawdziwą odpowiedź.

Zakładając, że prawda przyjmuje wartość -1, a fałsz - 0, a „~”, „&” i „|” są bitowe nie , a i czy operatorzy odpowiednio, a my pracujemy z uzupełnionych do dwóch arytmetyka:

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

A co z tym?

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

Dodanie 360 ​​ma na celu uniknięcie różnic ujemnych, ponieważ moduł liczby ujemnej zwraca wynik ujemny. Otrzymasz mniejszy z dwóch możliwych wyników.

Nadal istnieje dorozumiana decyzja, ale nie wiem, jak jej uniknąć. Zasadniczo porównujesz dwa kąty, obliczając różnicę zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara, i wydaje się, że wyraźnie chcesz mniejszej z tych dwóch różnic. Nie wiem, jak uzyskać ten wynik, nie porównując ich. To znaczy bez użycia „abs”, „min”, „max” lub jakiegoś podobnego operatora.

Chociaż twoje pytanie nie zawierało odniesienia do nich, zamierzam pracować nad założeniem, że twoje pytanie dotyczące obliczania kąta wynika z chęci poznania minimalnego kąta między dwoma wektorami .

To obliczenie jest łatwe. Zakładając, że A i B są wektorami:

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

Jeśli nie masz wektorów i chciałbyś skorzystać z tego podejścia, możesz zbudować wektory długości jednostkowej, biorąc pod uwagę swoje kąty new Vector2( cos( angle ), sin ( angle ) ).

Zasadniczo to samo co odpowiedź JasonD, z wyjątkiem użycia operacji bitowych zamiast funkcji wartości bezwzględnej.

Zakłada się, że masz 16-bitowe krótkie liczby całkowite!

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

Myślę

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

Ponieważ zależy ci tylko na wyeliminowaniu rozgałęzień i „złożonych” operacji wykraczających poza arytmetykę, polecam to:

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

Nadal potrzebujesz abstam, mimo że wszystkie kąty są pozytywne. W przeciwnym razie zawsze wybierany będzie najbardziej negatywny wynik (i zawsze będzie dokładnie jedna negatywna odpowiedź na pozytywne, unikalne a i b przy porównywaniu ab i ba).

Uwaga: Nie zachowa to kierunku między kątem 1 i kątem 2. Czasami potrzebujesz tego do celów AI.

Jest to podobne do odpowiedzi CeeJay, ale eliminuje wszystkie moduły. Nie wiem, jaki jest koszt cyklu abs, ale zgaduję, że to 1 lub 2. Trudno też powiedzieć, jaki jest koszt min. Może 3? Tak więc wraz z 1 cyklem na odejmowanie ta linia powinna kosztować około 4 do 9.

Uzyskać mniejszy względny kąt w podpisanym (+/-) postaci, z perspektywy mają wobec niedostatku :

• najwyżej 180 stopni | PI radianów
• - podpisany, jeśli jest przeciwny do ruchu wskazówek zegara
• + podpisany, jeśli zgodnie z ruchem wskazówek zegara

Stopnie

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

Radians

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

Racjonalne uzasadnienie

Natknąłem się na ten wątek po tym, jak to rozgryzłem, szukając rozwiązania, które pozwoli uniknąć modulo; jak dotąd nie znalazłem żadnego . To rozwiązanie służy do zachowania znaku perspektywy, ponieważ @ jacob-phillips poprosił o ten komentarz . Istnieją tańsze rozwiązania, jeśli potrzebujesz tylko najkrótszego kąta bez znaku.

To stare pytanie, ale natknąłem się na tę samą sprawę - musiałem uzyskać różnicę kątową, najlepiej bez gałęzi i ciężkiej matematyki. Właśnie z tym skończyłem:

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

Ograniczeniem jest to, że „b” nie powinien mieć więcej niż „N” obrotów w porównaniu z „a”. Jeśli nie możesz tego zapewnić i możesz zezwolić na dodatkowe operacje, użyj tego jako pierwszej linii:

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

Wpadłem na pomysł z 13. komentarza tego posta: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-two-angles-keeping-the- znak

chyba mógłbym powiedzieć

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

oczywiście biorąc pod uwagę, że kąt jest mierzony w stopniach.