Intervall [0, 2pi)

Bloops

Hallo!

Was ist die effizienteste Methode, um einen Winkel auf das Intervall [0, 2pi) zu mappen? Gibt es da was Besseres als fmod und wie verhält es sich mit negativen Winkeln (welche natürlich ebenfalls ins positive Intervall [0, 2pi) gemapped werden sollen?

Ramanujan

Also ich hätte jetzt fmod benutzt, überprüft, ob das Ergebnis negativ ist und falls ja, 2*pi addiert.

SeppJ

Bloops schrieb:

wie verhält es sich mit negativen Winkeln (welche natürlich ebenfalls ins positive Intervall [0, 2*pi) gemapped werden sollen?

Seit C++11 hat das Ergebnis einer modulo-Operation (auch fmod) das gleiche Vorzeichen wie der Dividend (also die Zahl auf der linken Seite). Vorher (C++98) war dies implementation defined, aber obiges war das übliche Verhalten.

Das heißt du musst fmod(fmod(winkel, 2*pi) + 2*pi, 2*pi) machen. Was besseres fällt mir gerade nicht ein.

Ramanujan

double t = fmod(winkel, 2*pi);
if (t < 0) t += 2*pi;

Könnte schneller sein, das würde ich einfach mal testen.
2*pi würde ich als Konstante speichern und nicht immer neu ausrechnen lassen, wenn es wirklich auf das letzte bisschen Laufzeit ankommt.

Bloops

Ramanujan schrieb:

double t = fmod(winkel, 2*pi);
if (t < 0) t += 2*pi;
Könnte schneller sein, das würde ich einfach mal testen.
2*pi würde ich als Konstante speichern und nicht immer neu ausrechnen lassen, wenn es wirklich auf das letzte bisschen Laufzeit ankommt.

Besten Dank, das war auch mein Ansatz. Ich werds mal profilen.

Werner Salomon

Bloops schrieb:

Was ist die effizienteste Methode, um einen Winkel auf das Intervall [0, 2pi) zu mappen? Gibt es da was Besseres als fmod und wie verhält es sich mit negativen Winkeln (welche natürlich ebenfalls ins positive Intervall [0, 2pi) gemapped werden sollen?

Hallo Bloops,

wenn Du wirklich effizient sein willst, muss man erst mal fragen, wozu das Mappen überhaupt notwendig ist. Oft braucht man es um Summen oder Differenzen von Winkeln zu bestimmen. Darüber hinaus ruft man i.A. auf diesen Winkeln die Trigonometrischen Funktionen auf, also sin und cos und Co. Ich kenne keine Applikation, bei der das nicht so ist.

Mal angenommen es sei so, dann ist es weit aus effizienter gar nicht zu mappen und auch gar nicht mit dem Winkel - sei es in rad oder Grad zu rechnen. Sondern statt dessen gleich mit dem sin- und cos-Wert des Winkels. Die Summe bzw. Differenz wird über die Additionstheoreme bestimmt. Damit entfällt auch das 'Mapping-Problem'.
Ein Winkel a bestehend aus eine Paar double a.sin_,b.sin_; lässt sich so mit einem Winkel b addieren

ergebnis.sin_ = a.sin_*b.cos_ + a.cos_*b.sin_;
ergebnis.cos_ = a.cos*b.cos_ - a.sin_*b.sin_;

Das ist - ein anschließender Aufruf von sin() und cos() vorausgesetzt - etwa 5mal so schnell, wie mit rad zu rechnen und es ist sogar noch etwas genauer, da sich die Ungenauigkeit der Darstellung von PI nicht so auswirkt.

Das ganze in Code gegossen:

#include <boost/operators.hpp>
#include <cmath>
#include <ostream>

namespace
{
    const double PI = std::acos(-1.0);
    const double GRAD2RAD = PI/180.0;
}

class Winkel : boost::additive< Winkel >
{        // ginge auch ohne boost.operators, dann muss man es halt selber hinschreiben
public:
    Winkel() : sin_(0.), cos_(1.) {} // 0°
    Winkel& operator+=( const Winkel& b )
    {
        const double s = sin_*b.cos_ + cos_*b.sin_;
        cos_ = cos_*b.cos_ - sin_*b.sin_;
        sin_ = s;
        return *this;
    }

    // --   trigonometrische Funktionen
    friend double sin( const Winkel& w ) { return w.sin_; }
    friend double cos( const Winkel& w ) { return w.cos_; }

    friend std::ostream& operator<<( std::ostream& out, const Winkel& w )
    {
        return out << std::atan2( w.sin_, w.cos_ ) /GRAD2RAD << "Grad";
    }

private:
    Winkel( double s, double c ) // privat, um Missbrauch auszuschließen
        : sin_( s ), cos_( c )
    {}
    double sin_, cos_;
};

operator-= und tan und cot bitte selber hinzufügen.

Mit dem Winkel kann man schon mal rechnen, aber Du kannst keinen Winkel anlegen, der nicht 0° ist. Dafür gibt es noch einen Trick, der vermeidet, dass man Grad und rad verwechselt. Man macht sich eine Einheitenklasse - hier EinheitGrad und einen operator* mit einem double.

class Winkel;
struct EinheitGrad {};
Winkel operator*( double grad, EinheitGrad );
namespace
{
    const EinheitGrad Grad;
}

und das ganze wird als friend-Funktion in der Klasse Winkel implementiert.

class Winkel : boost::additive< Winkel >
{
public:
    friend Winkel operator*( double grad, EinheitGrad )
    {
        const double winkel_in_rad = grad*GRAD2RAD;
        return Winkel( std::sin(winkel_in_rad), std::cos(winkel_in_rad) );
    }
    // usw. (s.o.)

Um einen Winkel zu erzeugen, schreibt man im Code jetzt z.B.:

Winkel a = 30*Grad;

somit ist klar, was das für ein Winkel ist - und mit rad ginge das natürlich genauso.

Gruß
Werner

Bloops

Hallo Werner,

das ist auch ein sehr interessanter Ansatz. Ich brauche aber wirklich Winkel in [0, 2pi), da diese (nach Diskretisieren) Bestandteil eines Suchgraphen sind. Hierbei ist wichtig, dass gleiche Winkel auch als solche abgebildet werden. Ist etwas komplizierter

knivil

Hierbei ist wichtig, dass gleiche Winkel auch als solche abgebildet werden.

Dann sind Fliesskommazahlen sowieso der falsche Weg. Behalte einfach die orginalen Vektoren und nutze fuer Vergleiche das Skalarprodukt.

SeppJ

knivil schrieb:

Hierbei ist wichtig, dass gleiche Winkel auch als solche abgebildet werden.

Dann sind Fliesskommazahlen sowieso der falsche Weg. Behalte einfach die orginalen Vektoren und nutze fuer Vergleiche das Skalarprodukt.

Häh? Die Idee ist falsch, der Datentyp ist aber richtig.

Bloops

Was für Vektoren auf einmal?

Finds ein bisschen lustig, dass ihr gar nicht genau wisst, warum es im Detail geht, aber einfach mal den Ansatz als falsch bezeichnet

knivil

Ein Schuss ins Blaue, da du ja nichts ueber das eigentliche Problem gesagt hast, nur ueber einen kleinen Teil deiner Realisierung.

SeppJ

Bloops schrieb:

Finds ein bisschen lustig, dass ihr gar nicht genau wisst, warum es im Detail geht, aber einfach mal den Ansatz als falsch bezeichnet

Erfahrung. Wir hatten alle selber mal diese Art Probleme (oder kennen genügend Leute, die diese hatten) und wissen, dass man zuerst schulgeometrisch denkt, dass man wirklich den Absolutwert der Winkel benötigen würde. Aber wir haben gelernt, dass die effiziente Antwort über die Additionstheoreme geht. Meistens jedenfalls. Es gibt seltene Ausnahmen.

Andere typische Alarmzeichen für naive Lösungen, die in der Theorie ganz toll klingen, aber praktisch unbrauchbar sind, sind beispielsweise Taylorreihen oder Matrixdiagonalisierung.

Bloops

knivil schrieb:

Ein Schuss ins Blaue ...

Was soll ich sagen? Daneben.

SeppJ schrieb:

Erfahrung. Wir hatten alle selber mal diese Art Probleme ...

Hm, klingt ein bisschen pauschalisierend oder? :p

Weder addiere ich irgendwelche Winkel noch führe ich sonstige trigonometrische Berechnungen damit durch. Es ehrt euch zwar, dass ihr gar nicht gestellte Fragen beantworten wollt, aber ich bin mir ziemlich sicher mit dem, was ich tue

Die Details hab ich bewusst nicht näher erläutert, weil sie für die ursprüngliche Fragestellung absolut irrelevant sind, und abgesehen davon müsste ich sehr, sehr weit ausholen.

Bloops, Du solltest vielleicht Werners Ansatz noch einmal bedenken. Wenn Du, wie Du schreibst, das als Elemente in einem Suchgraphen brauchst, wäre es da nicht egal, ob das nun ein float, double, hurz, knurz oder was auch immer ist?

Ich glaube, es würde uns hier helfen, Dir zu helfen, wenn Du erläutern könntest, _was_ genau mit dem Wert gemacht werden soll.

Bloops

Aber ihr habt mir doch schon längst geholfen.
Der Suchgraph selbst nutzt übrigens nur Integers.