Winkel vergleichen und den Unterschied herausarbeiten

27

Ich möchte Winkel vergleichen und eine Vorstellung von der Entfernung zwischen ihnen bekommen. Für diese Anwendung arbeite ich in Grad, aber es würde auch für Bogenmaß und Absolventen funktionieren. Das Problem bei Winkeln ist, dass sie von einer modularen Arithmetik abhängen, dh 0-360 Grad.

Angenommen, ein Winkel liegt bei 15 Grad und einer bei 45. Der Unterschied beträgt 30 Grad, und der 45-Grad-Winkel ist größer als der 15-Grad-Winkel.

Dies bricht jedoch zusammen, wenn Sie beispielsweise 345 Grad und 30 Grad haben. Obwohl sie richtig verglichen werden, beträgt der Unterschied zwischen ihnen 315 Grad anstatt der korrekten 45 Grad.

Wie kann ich das lösen? Ich könnte algorithmischen Code schreiben:

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

Aber ich würde eine Lösung vorziehen, die Vergleiche / Verzweigungen vermeidet und sich ausschließlich auf Arithmetik stützt.

Thomas O.
quelle
Können wir bei diesem Problem annehmen, dass die angegebenen Winkel im Bereich [0,360] oder (-infinite, + infinite) liegen? Soll der Algorithmus beispielsweise auch einen Vergleich von -130 Grad mit 450 Grad durchführen?
Egarcia
Angenommen, die Winkel sind auf diesen Bereich normiert.
Thomas O

Antworten:

29

Hier ist meine vereinfachte, verzweigungslose, vergleichsfreie, keine Min / Max-Version:

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

Das Modulo wurde entfernt, da die Eingaben ausreichend beschränkt sind (danke an Martin für den Hinweis).

Zwei abs, drei subtrahieren.

JasonD
quelle
Sie brauchen das Modulo nicht, die Eingabewerte sind auf den Bereich [0,360] beschränkt (siehe Thomas 'Kommentar zur ursprünglichen Einreichung). Ziemlich ordentlich.
Martin Sojka
Ah ja, du hast recht. Ich hatte weniger strengen Input, als ich es ausprobierte.
JasonD
aber was ist, wenn Sie das Zeichen des Unterschieds beibehalten möchten, damit Sie erkennen können, welches auf der linken Seite ist?
Jacob Phillips
9

Obwohl sie richtig verglichen werden, beträgt der Unterschied zwischen ihnen 315 Grad anstatt der korrekten 45 Grad.

Was lässt Sie denken, dass 315 falsch ist? In einer Richtung sind es 315 Grad, in der anderen Richtung 45. Sie möchten den kleinsten der beiden möglichen Winkel auswählen, und dies scheint an sich eine Bedingung zu erfordern. Sie können es nicht mit Umlauf-Arithmetik lösen (dh mit dem Modul-Operator), da der Winkel zwischen ihnen mit zunehmendem Winkel immer größer wird, bis er 180 erreicht und dann abnimmt.

Ich denke, Sie müssen entweder beide Winkel prüfen und entscheiden, in welche Richtung Sie messen möchten, oder beide Richtungen berechnen und entscheiden, welches Ergebnis Sie erzielen möchten.

Kylotan
quelle
Entschuldigung, ich sollte das klären. Wenn Sie es umgekehrt gemacht haben, ist 30 - 345 -315 und ein negativer Winkel macht nicht viel Sinn. Ich schätze, ich suche den kleinsten Winkel zwischen den beiden. dh 45 Grad ist kleiner als 315.
Thomas O
2
Es gibt jedoch keine Umkehrung - Sie haben 2 Winkel und 2 Arten der Drehung, um eine Übereinstimmung mit der anderen zu erzielen. Ein negativer Winkel macht durchaus Sinn - es ist schließlich nur ein Maß für die Drehung um eine beliebige Achse.
Kylotan,
Wenn Sie den kleinsten Winkel wünschen, gibt Ihnen abs (a1% 180 - a2% 180) diesen Winkel. Es wird Ihnen jedoch nicht die Richtung verraten. Wenn Sie die Bauchmuskeln entfernen, erhalten Sie den kleinsten Winkel zwischen "a1" und "a2"
Chewy Gumball
2
@Chewy, nicht wahr? Der Unterschied zwischen 180 und 0 ist nicht 0, und der Unterschied zwischen 181 und 0 ist nicht 1 ...
Dash-Tom-Bang
1
@ Dash-Tom-Bang Sie sind ganz richtig. Ich weiß nicht, was ich dachte, aber es stimmte überhaupt nicht, wenn ich es mir noch einmal ansehe. Bitte ignoriere meinen vorherigen Kommentar.
Chewy Gumball
4

Es gibt immer den Trick, beide Verzweigungen auszuführen und das Vergleichsergebnis eine auswählen zu lassen:

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

Ich kenne keine Möglichkeit, ohne Vergleiche vorzugehen , aber normalerweise macht der Zweig den Code langsam und lang, nicht der Vergleich. Zumindest ist dies meiner Meinung nach lesbarer als Martins Antwort (jeder gute C-Programmierer erkennt es als verzweigungsloses Äquivalent und sieht, was es tut), aber auch weniger effizient.

Aber wie ich in meinem Kommentar sagte, sind branchless Algorithmen auf Prozessoren mit tiefen Pipelines und schlechter Vorhersage gut - ein Mikrocontroller hat normalerweise eine winzige Pipeline, und ein Desktop-PC hat normalerweise eine gute Vorhersage ist wahrscheinlich der beste Weg, wenn er die Befehlsanzahl verringert.

Wie immer gibt Ihnen die Profilerstellung, die für Ihr System so einfach wie das Zählen von Operationen sein kann, die richtige Antwort.


quelle
2

Angenommen, true ergibt -1 und false ergibt 0 und '~', '&' und '|' sind bitweise nicht , und und bzw. Operatoren, und wir arbeiten mit Zweierkomplementarithmetik:

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 */
Martin Sojka
quelle
+1, weil es klug ist, aber auf einem Mikrocontroller ist dies wahrscheinlich viel schlechter als die Verzweigungsversion.
Kommt ein bisschen auf den Mikrocontroller an, aber es lohnt sich normalerweise nicht; Ein (kurzer) bedingter Sprung ist normalerweise schnell genug. Außerdem können die dritte und fünfte Zeile mit der folgenden xor (^) -Operation etwas schneller umgeschrieben werden, aber ich habe sie aus Gründen der Übersichtlichkeit in der aktuellen Form belassen: temp1: = temp2 ^ ((temp2 ^ -temp2) & ~ Temp1), Temp2: = Temp1 ^ ((Temp1 ^ (360 - Temp1)) & ~ Temp2)
Martin Sojka
1

Was ist damit?

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

Die Addition von 360 dient dazu, negative Unterschiede zu vermeiden, da ein Modulo einer negativen Zahl ein negatives Ergebnis liefert. Dann erhalten Sie das kleinere der beiden möglichen Ergebnisse.

Es gibt immer noch eine implizite Entscheidung, aber ich weiß nicht, wie ich sie vermeiden soll. Grundsätzlich vergleichen Sie die beiden Winkel, indem Sie den Unterschied im oder gegen den Uhrzeigersinn berechnen, und es scheint, dass Sie den kleineren dieser beiden Unterschiede ausdrücklich wünschen. Ich weiß nicht, wie ich dieses Ergebnis erzielen kann, ohne sie zu vergleichen. Das heißt, ohne "abs", "min", "max" oder einen ähnlichen Operator zu verwenden.

CeeJay
quelle
Es gibt verschiedene Methoden, um Min, Max und Abs von Ints ohne Verzweigungsbefehle zu berechnen. Da es sich jedoch um einen Mikrocontroller handelt, ist die Verzweigung wahrscheinlich die schnellste Methode. graphics.stanford.edu/~seander/bithacks.html#IntegerAbs
1

Obwohl Ihre Frage keinen Hinweis darauf enthielt, gehe ich davon aus, dass Ihre Winkelberechnungsfrage darauf zurückzuführen ist, dass Sie den Mindestwinkel zwischen zwei Vektoren kennen wollen .

Diese Berechnung ist einfach. Angenommen, A und B sind Ihre Vektoren:

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

Wenn Sie nicht über Vektoren verfügen und diesen Ansatz verwenden möchten, können Sie anhand Ihrer Winkel Einheitslängenvektoren konstruieren new Vector2( cos( angle ), sin ( angle ) ).

Tetrade
quelle
1
Der Prozessor, an dem ich arbeite, ist ein kleiner Mikrocontroller. Es ist nicht sinnvoll, Triggerfunktionen zu verwenden, um einen Vektor zu generieren, nur um den Unterschied zwischen den Winkeln zu ermitteln. Jeder Zyklus ist wertvoll.
Thomas O
1
Auf einem Mikrocontroller wundert es mich, dass es nicht besser ist, einen Zweig zu verwenden, aber meine Antwort enthält nicht viel Arithmus, wenn Sie Verzweigungen wirklich vermeiden möchten.
JasonD
Nun, eine Verzweigung besteht aus zwei Zyklen und eine Addition / Subtraktion / usw. ist ein Zyklus, aber die Verzweigung beansprucht auch zusätzlichen Programmspeicher. Es ist nicht kritisch, aber es wäre schön.
Thomas O
Ich habe das Gefühl, Ihre Antwort ist richtig und meine ist falsch, aber ich kann nicht verstehen , warum das so ist. :)
Kylotan
1

Grundsätzlich die gleiche Antwort wie bei JasonD, außer dass bitweise Operationen anstelle der Absolutwertfunktion verwendet werden.

Dies setzt voraus, dass Sie 16-Bit-Ganzzahlen haben!

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

Ich glaube

delta = (a2 + Math.ceil( -a2 / 360 ) * 360) - (a1 + Math.ceil( -a1 / 360 ) * 360);
Saad Ahmed
quelle
0

Da es Ihnen nur darum geht, Verzweigungen und "komplexe" Operationen zu eliminieren, die über das Rechnen hinausgehen, würde ich Folgendes empfehlen:

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

Sie brauchen immer noch einen, absobwohl alle Blickwinkel positiv sind. Andernfalls wird immer das negativste Ergebnis ausgewählt (und es wird immer genau eine negative Antwort für positives, eindeutiges a und b beim Vergleich von ab und ba geben).

Hinweis: Dadurch wird die Richtung zwischen Winkel1 und Winkel2 nicht beibehalten. Manchmal braucht man das für KI-Zwecke.

Dies ähnelt der Antwort von CeeJay, eliminiert jedoch alle Module. Ich weiß nicht, wie hoch die Zykluskosten sind abs, aber ich vermute, dass es 1 oder 2 sind. Schwer zu sagen, wie hoch die Kosten minauch sind. Vielleicht 3? Zusammen mit einem Zyklus pro Subtraktion sollte diese Zeile also ungefähr 4 bis 9 kosten.

DrZ214
quelle
0

Holen Sie sich den kleineren relativen Winkel in vorzeichenbehafteter (+/-) Form aus der Perspektive von haben in Richtung wollen :

  • höchstens 180 Grad | PI-Bogenmaß
  • -signiert wenn gegen den Uhrzeigersinn
  • + im Uhrzeigersinn signiert

Grad

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

Radiant

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

Begründung

Ich bin auf diesen Thread gestoßen, nachdem ich das herausgefunden hatte, auf der Suche nach einer Lösung, die Modulo vermeidet. Bisher habe ich keine gefunden . Diese Lösung dient zum Erhalten des perspektivischen Zeichens, da @ jacob-phillips diesen Kommentar gefragt hat . Es gibt billigere Lösungen, wenn Sie nur den kürzesten Winkel ohne Vorzeichen benötigen.

angst
quelle
0

Es ist eine alte Frage, aber ich bin auf denselben Fall gestoßen - ich musste einen signierten Winkeldifferenz erhalten und am besten ohne Verzweigungen und schwere Mathematik. Dies ist, was ich am Ende mit:

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

Die Einschränkung ist, dass 'b' nicht mehr als 'N' Rotationen im Vergleich zu 'a' haben sollte. Wenn Sie dies nicht sicherstellen können und zusätzliche Operationen zulassen, verwenden Sie dies als erste Zeile:

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

Die Idee kam mir aus dem 13. Kommentar dieses Beitrags: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-angles-keeping-the- Zeichen

Mikk L.
quelle
-1

Ich denke, ich könnte sagen

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

natürlich, wenn man bedenkt, dass der Winkel in Grad gemessen wird.

Vishnu
quelle
1
Ich glaube nicht, dass dies das Problem in der Frage löst. 345% 360 == 345, und abs (345-30) ist immer noch 315.
Gregory Avery-Weir
@ Gregory: Okay !, der Fehler tut mir leid. Ich bearbeite die Antwort, überprüfe diese neue. :)
Vishnu
1
Übrigens, angle1 = angle1% 360; winkel2 = winkel2% 360; var distance = Math.abs (angle1-angle2); ist dasselbe wie var distance = Math.abs (angle1-angle2)% 360 - nur langsamer.
Martin Sojka