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


27

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.


Czy w związku z tym problemem możemy założyć, że podane kąty mieszczą się w przedziale [0,360] lub (- nieskończony, + nieskończony)? Na przykład, czy algorytm powinien także działać na porównaniu -130 stopni z 450?
egarcia

Załóżmy, że kąty są znormalizowane do tego zakresu.
Thomas O

Odpowiedzi:


29

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.


Nie potrzebujesz modulo, wartości wejściowe są ograniczone do zakresu [0,360] (patrz komentarz Thomasa do pierwotnego zgłoszenia). Całkiem schludnie.
Martin Sojka

Ach, tak, masz rację. Kiedy próbowałem, miałem mniej rygorystyczny wkład.
JasonD

ale co, jeśli chcesz zachować znak różnicy, abyś mógł stwierdzić, który jest po lewej?
Jacob Phillips

9

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.


Przepraszam, że powinienem to wyjaśnić. Jeśli zrobiłeś to w odwrotnej kolejności, 30 - 345 to -315, a ujemny kąt nie ma większego sensu. Chyba szukam najmniejszego kąta między nimi. tzn. 45 stopni jest mniejsze niż 315.
Thomas O

2
Ale nie ma „odwrotności” - masz 2 kąty i 2 rodzaje obrotu, które możesz wykonać, aby dopasować jeden do drugiego. Kąt ujemny ma idealny sens - w końcu to tylko miara obrotu od dowolnej osi.
Kylotan

Jeśli chcesz najmniejszy kąt, abs (a1% 180 - a2% 180) da ci ten kąt. Nie powie ci jednak kierunku. Usunięcie mięśni brzucha zapewni najmniejszy kąt „przejścia z„ a1 ”na„ a2
Chewy Gumball,

2
@Chewy, co? Różnica między 180 a 0 nie wynosi 0, a różnica między 181 a 0 nie wynosi 1 ...
dash-tom-bang

1
@ dash-tom-bang Masz rację. Nie wiem, o czym myślałem, ale teraz, gdy znów na to patrzę, nie było wcale poprawne. Proszę zignorować mój poprzedni komentarz.
Chewy Gumball,

4

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ź.


2

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

+1, ponieważ jest sprytny, ale na mikrokontrolerze jest to prawdopodobnie znacznie gorsze niż wersja rozgałęziająca.

Zależy trochę od mikrokontrolera, ale tak, zwykle nie jest tego warte; (krótki) skok warunkowy jest zazwyczaj wystarczająco szybki. Trzecie i piąte wiersze można również przepisać, aby były nieco szybsze przy użyciu operacji xor (^) w ten sposób, ale dla zachowania przejrzystości pozostawiłem je w bieżącej formie: temp1: = temp2 ^ ((temp2 ^ -temp2) & ~ temp1), temp2: = temp1 ^ ((temp1 ^ (360 - temp1)) & ~ temp2)
Martin Sojka

1

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.


Istnieje kilka sposobów obliczania wartości min, maks i abs ints bez instrukcji gałęzi, jednak ponieważ jest to mikrokontroler, gałąź jest prawdopodobnie najszybszym sposobem. graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

1

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 ) ).


1
Procesor, nad którym pracuję, to mały mikrokontroler. Nie ma sensu używać funkcji wyzwalania do generowania wektora, aby uzyskać różnicę między kątami, każdy cykl jest cenny.
Thomas O

1
W mikrokontrolerze jestem trochę zaskoczony, że nie lepiej jest używać gałęzi, ale w mojej odpowiedzi nie ma dużo arytmetyki, jeśli naprawdę chcesz uniknąć rozgałęziania.
JasonD

Cóż, gałąź ma dwa cykle, a dodawanie / odejmowanie / etc to jeden cykl, ale rozgałęzianie zajmuje również dodatkową pamięć programu. To nie jest krytyczne, ale byłoby miło.
Thomas O

Mam wrażenie, że twoja odpowiedź jest prawidłowa, a moja błędna, ale nie mogę się zastanowić , dlaczego tak jest. :)
Kylotan,

1

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

0

Myślę

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

0

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.


0

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.


0

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


-1

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.


1
Nie wierzę, że to rozwiązuje problem w pytaniu. 345% 360 == 345, a abs (345-30) wciąż wynosi 315.
Gregory Avery-Weir

@Gregory: okej !, przepraszam za błąd. Edytuję odpowiedź, sprawdź tę nową. :)
Wisznu

1
Nawiasem mówiąc, kąt1 = kąt1% 360; kąt2 = kąt 2% 360; var distance = Math.abs (angle1-angle2); jest taki sam jak var odległość = Math.abs (kąt1-kąt2)% 360 - po prostu wolniej.
Martin Sojka
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.