Optimierung einer Entfernungsberechnungsfunktion

Wenn es Ihr Ziel ist, Entfernungen zu vergleichen (), können Approximationen ( sin und cos -Tabellen-Lookups) die Anzahl der erforderlichen Berechnungen drastisch reduzieren (implementieren Sie quick reject .)

Ihr Ziel ist es, nur mit der tatsächlichen trigonometrischen Berechnung fortzufahren, wenn die Differenz zwischen den approximierten Entfernungen (die zu bewerten oder zu vergleichen sind) unter einen bestimmten Schwellenwert fällt.

z. unter Verwendung von Nachschlagetabellen mit 1000 Abtastwerten (d. h. sin und cos alle 2*pi/1000 abgetastet) beträgt die Nachschlagetunsicherheit höchstens 0,006284. Unter Verwendung der Unsicherheitsberechnung für den Parameter ACos ist die kumulierte Unsicherheit auch die Schwellenunsicherheit , wird höchstens 0,018731 sein.

Wenn also Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) unter Verwendung von sin und cos Nachschlagetabellen für zwei Koordinatenpaare (Distanzen) berechnet wird, ergibt sich eine bestimmte Rangfolge (eine Distanz erscheint größer als die andere basierend auf der Approximation) und die Differenz Modulus ist größer als der obige Schwellenwert, dann ist die Approximation gültig. Andernfalls fahren Sie mit der eigentlichen trigonometrischen Berechnung fort.

Würde der CORDIC -Algorithmus für Sie (in Bezug auf Geschwindigkeit / Genauigkeit) funktionieren?

Ändern Sie die Art, wie Sie long / lat speichern:

Wenn Sie ein long / lat erstellen, berechnen Sie auch den (x, y, z) 3D-Punkt, der die äquivalente Position auf einer Einheitskugel darstellt, die am Ursprung zentriert ist.

Um festzustellen, ob Punkt B näher an Punkt A als Punkt C ist, gehen Sie wie folgt vor:

und um die Entfernung zwischen zwei Punkten zu erhalten:

Sie könnten den Begriff "Radius" entfernen, um die Abstände zu normalisieren.

Wechsel zu Nachschlagetabellen für sin / cos / acos. Wird schneller sein, es gibt viele c / c ++ Fixed-Point-Bibliotheken, die auch diese enthalten.

Hier ist Code von jemand anderem auf Memoization . Das könnte funktionieren, wenn die tatsächlichen Werte mehr geclustert sind.

Hier ist eine SO-Frage zu Fixed Point .

Was ist der Flaschenhals? Ist die Sinus / Cosinus-Funktion oder der Arcsine-Aufruf?

Wenn Ihre Sinus / Cosinus-Aufrufe langsam sind, können Sie den folgenden Satz verwenden, um so viele Aufrufe zu verhindern:

Aber ich mag die Mapping-Idee, damit Sie die Werte, die Sie bereits berechnet haben, nicht neu berechnen müssen. Seien Sie vorsichtig, da die Karte sehr schnell sehr groß werden kann.

Nun, da lat und lon garantiert innerhalb eines bestimmten Bereichs liegen, könnten Sie versuchen, eine Form einer Nachschlagetabelle für Ihre Math. * Methodenaufrufe zu verwenden. Sagen wir, ein Dictionary<double,double>

Ich würde argumentieren, dass Sie vielleicht noch einmal untersuchen möchten, wie Sie diese Funktion als Engpass gefunden haben. (IE haben Sie die Anwendung profiliert?)

Die Gleichung für mich scheint sehr gering und sollte keinen Ärger verursachen. Zugegeben, ich kenne Ihre Anwendung nicht und Sie sagen, dass Sie viele dieser Berechnungen durchführen.

Trotzdem ist es etwas zu beachten.

Ich benutze einen anderen Algorithmus für die Berechnung der Entfernung zwischen 2 Lati / Longi-Positionen, es könnte leichter sein als deins, da es nur 1 Cos Call und 1 Sqrt Call macht.

Jemand hat Memoisierung bereits erwähnt, und das ist ein bisschen ähnlich. Wenn Sie denselben Punkt mit vielen anderen Punkten vergleichen, ist es besser, Teile dieser Gleichung vorher zu berechnen.

statt

habe:

und ich denke, das ist die gleiche Formel wie jemand anders gepostet hat, weil ein Teil der Gleichung verschwinden wird, wenn Sie die Klammern erweitern:)