Winkel zwischen zwei Linien berechnen

Treue Seele

David Scherfgens Website | Konzentrationstest Polizei

26.10.2017, 09:51

Winkel zwischen zwei Linien berechnen

Hi,

ich habe zwei Linien, welche durch die Koordinaten vdata.point1/vdata.point2 und vdata.point2/vdata.point3 definiert werden:

C-/C++-Quelltext

static float get_angle(const struct laser_point *laserPoint)
{
   float this_length,v_lenght;
   float ll,d;
   float vecX1,vecX2,vecY1,vecY2;

   vecX1=(float)(vdata.point1.x-vdata.point2.x);
   vecY1=(float)(vdata.point1.y-vdata.point2.y);
   this_length=sqrtf((vecX1*vecX1)+(vecY1*vecY1));

   vecX2=(float)(vdata.point2.x-vdata.point3.x);
   vecY2=(float)(vdata.point2.y-vdata.point3.y);
   v_lenght=sqrtf((vecX2*vecX2)+(vecY2*vecY2));

   ll = this_length*v_lenght;
   if(ll!=0.0)
   {
      d=(vecX1*vecX2 + vecY1*vecY2) / ll;
      return acosf(d);
   }
   return 1.57079637F;
}

Mit der Funktion oben berechne ich den Winkel zwischen diesen beiden Linien. Meine Frage wäre: lässt sich da noch was in Bezug auf die Geschwindigkeit optimieren?

Der Zwischenschritt mit den Variablen vecX1, vecX2, vecY1, vecY2 dient der Übersichtlichkeit und wird vom Compiler wegoptimiert. Das Ganze läuft auf einem Embedded Device, welches maximal 32 Bit float unterstützt, deswegen gibt es hier keine doubles. Mir würden aktuell nur noch vorberechnete Tabellen für sqrtf() und acosf() einfallen, was aber auf Grund des möglichen Wertebereiches und der geforderten Genauigkeit nicht in Frage kommt.

Gibt es sonst noch Optimierungsmöglichkeiten, die ich gerade nicht sehe?

Danke!

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

26.10.2017, 10:50

Du kannst dir eine Wurzel sparen:

§§\measuredangle(\vec{a}, \vec{b}) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\left|\vec{a}\right|\cdot\left|\vec{b}\right|}\right) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\sqrt{\vec{a}^2}\cdot\sqrt{\vec{b}^2}}\right) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\sqrt{\vec{a}^2\cdot\vec{b}^2}}\right)§§

Zum Seitenanfang

Supermoderator

Wohnort: Graz

26.10.2017, 12:27

Ich würde generell mal die Frage stellen: Wofür genau musst du überhaupt diesen Winkel ausrechnen?

Zum Seitenanfang

Treue Seele

26.10.2017, 12:34

Zitat von »dot«

Ich würde generell mal die Frage stellen: Wofür genau musst du überhaupt diesen Winkel ausrechnen?

Die Antwort wird dich nicht glücklich machen: Um die daraus resultierende Pause zu erhalten! Ja, ist wirklich so...

Zum Seitenanfang

Supermoderator

Wohnort: Graz

26.10.2017, 12:36

D.h. es geht hier um die Zeiger an einer Uhr? Woher kommt die Stellung dieser Zeiger in Vektorform? Und wieso ist das performancekritisch?

Zum Seitenanfang

Treue Seele

26.10.2017, 12:36

Zitat von »David Scherfgen«

Du kannst dir eine Wurzel sparen:

§§\measuredangle(\vec{a}, \vec{b}) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\left|\vec{a}\right|\cdot\left|\vec{b}\right|}\right) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\sqrt{\vec{a}^2}\cdot\sqrt{\vec{b}^2}}\right) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\sqrt{\vec{a}^2\cdot\vec{b}^2}}\right)§§

Ähm das raffe ich nicht - wieso spare ich mir nur eine Wurzel? In dem Teil nach dem ersten "=" ist doch gar keine Wurzel mehr drin!?

Zum Seitenanfang

Treue Seele

David Scherfgens Website | Konzentrationstest Polizei

26.10.2017, 12:40

Zitat von »dot«

D.h. es geht hier um die Zeiger an einer Uhr? Woher kommt die Stellung dieser Zeiger in Vektorform? Und wieso ist das performancekritisch?

Nein, es geht um gar nichts, was mit Spielen oder Grafik zu tun hat (in keinem meiner Programme, das Know-How in diesem Forum hier ist nur auch sehr gut für andere Anwendungen geeignet). Ohne jetzt großartig ins Detail gehen zu können: das gehört zu einer Maschinensteuerung, die in Echtzeit Positionsdaten verarbeiten und konvertieren muss. Performancekritisch ist das deswegen, weil das Embedded Device, auf dem das passiert, relativ schwachbrüstig ist und trotzdem eine halbe Million Positionen pro Sekunde verarbeiten muss. Die großen Optimiermöglichkeiten sind durch, mittlerweile kratze ich an jeder Nanosekunde herum :-D

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

26.10.2017, 12:45

Zitat von »Elmi«

Ähm das raffe ich nicht - wieso spare ich mir nur eine Wurzel? In dem Teil nach dem ersten "=" ist doch gar keine Wurzel mehr drin!?

Für den Betrag eines Vektors, also §|\vec{a}|§, brauchst du doch eine Wurzel.

Zum Seitenanfang

Supermoderator

Wohnort: Graz

26.10.2017, 12:46

Zitat von »Elmi«

Zitat von »David Scherfgen«

Du kannst dir eine Wurzel sparen:

§§\measuredangle(\vec{a}, \vec{b}) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\left|\vec{a}\right|\cdot\left|\vec{b}\right|}\right) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\sqrt{\vec{a}^2}\cdot\sqrt{\vec{b}^2}}\right) = \cos^{-1}\left(\frac{\vec{a}\cdot\vec{b}}{\sqrt{\vec{a}^2\cdot\vec{b}^2}}\right)§§

Ähm das raffe ich nicht - wieso spare ich mir nur eine Wurzel? In dem Teil nach dem ersten "=" ist doch gar keine Wurzel mehr drin!?

§\mathrm{\mathbf a}§ und §\mathrm{\mathbf b}§ sind Vektoren...

Potentielles Problem mit dieser Lösung ist aber, dass sie immer den kürzesten Winkel liefert. Wenn es tatsächlich um die Zeiger einer Uhr geht, wirst du wohl auch die relative Position der Zeiger zueinander berücksichtigen müssen. In dem Fall würde ich das Kreuzprodukt der beiden Vektoren verwenden. Dessen Richtung gibt Information über die relative Position und dessen Länger ist proportional zum §\sin§ des Winkels...

Zum Seitenanfang

Supermoderator

Wohnort: Graz

26.10.2017, 12:52

Zitat von »Elmi«

Performancekritisch ist das deswegen, weil das Embedded Device, auf dem das passiert, relativ schwachbrüstig ist und trotzdem eine halbe Million Positionen pro Sekunde verarbeiten muss. Die großen Optimiermöglichkeiten sind durch, mittlerweile kratze ich an jeder Nanosekunde herum :-D

Gut, dann die von David gezeigte Lösung. Was für ein Instruction Set hast du denn zur Verfügung? Die reziproke Wurzel lässt sich gut direkt berechnen, in vielen ISAs gibt es spezielle Instructions dafür. Für die relative Ausrichtung dann wie gesagt z.B. die Richtung des Kreuzprodukts (einfach nur das Vorzeichen der z-Koordinate des Kreuzprodukts der zwei in der xy-Ebene liegenden 2D Vektoren anschauen). Das Ausrechnen des Winkels geht über das Skalarprodukt wohl etwas effizienter wie David oben gezeigt hat...