Optimierung einer Entfernungsberechnungsfunktion

Question

In meinem Code habe ich zwischen Paaren von lat / long-Werten viel Entfernungsberechnung zu tun.

Der Code sieht wie folgt aus:

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

(lat2rad z.B. Breitengrad wird in Radiant umgewandelt).

Ich habe diese Funktion als Leistungsengpass meiner Anwendung identifiziert. Gibt es eine Möglichkeit, dies zu verbessern?

(Ich kann nicht Look-up-Tabellen verwenden, da die Koordinaten variieren). Ich habe betrachteten auch diese Frage , wo ein Lookup-Schema wie ein Gitter vorgeschlagen, das könnte eine Möglichkeit sein.

Vielen Dank für Ihre Zeit! ; -)

Answer 1

Wenn Ihr Ziel Rang ist (vergleiche) Entfernungen , dann Annäherungen (sin und cos Tabelle Lookups) könnte Ihre Menge an Berechnungen drastisch reduzieren, die erforderlich (implementieren schnell ablehnen . )

Ihr Ziel ist es, nur mit der tatsächlichen trigonometrischen Berechnung zu gehen, wenn die Differenz zwischen den angenäherten Entfernungen (bis auf Platz oder vergleichbar) unter einer bestimmten Schwelle.

z. Verwendung von Lookup-Tabellen mit 1000 Proben (das heißt sin und cos jeden 2*pi/1000 abgetastet), ist die Suche Unsicherheit bei den meisten 0,006284. Mit Unsicherheitsberechnung für den Parameter ACos, die kumuliertes Unsicherheit, auch die Schwellen Unsicherheit sein, wird 0.018731 höchstens sein.

Also, wenn die Bewertung Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) Verwendung sin und cos Nachschlagetabellen für zwei Koordinatensatz Paare (Entfernungen) ergibt eine bestimmte Rangfolge (ein Abstand, der größer wird als die anderen zur Annäherung basiert) und die Elastizitätsmodul Differenz größer als der Schwellenwert ist oben, dann ist die Annäherung gültig. Ansonsten mit der tatsächlichen trigonometrischen Berechnung gehen.

Answer 2

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

Answer 3

Mit Inspiration von @Brann ich glaube, Sie die Berechnung ein wenig reduzieren kann (seine lange Warnung, da ich irgendetwas davon haben, und es wird überprüft werden müssen). Eine Art Nachschlag von vorberechneten Werten wahrscheinlich die schnellste obwohl

Sie haben:

1: ACOS (SIN A SIN + COS B A B COS COS (A-B))

2: COS (A-B) = SIN A SIN B + COS COS A B

, die neu geschrieben wird als 3: SIN A SIN B = cos (A-B) - COS COS A B

ersetzen SIN A SIN B in 1. Sie haben:

4: ACOS (COS (A-B) - COS COS A B + A COS COS COS B (A-B))

Sie vorab berechnen X = COS (A-B) und Y = COS A COS B und setzen Sie die Werte in 4

geben:

ACOS (XY + XY)

4 trig Berechnungen anstelle von 6!

Answer 4

Ändern Sie die Art und Weise Sie speichern long / lat:

struct LongLat
{
  float
    long,
    lat,
    x,y,z;
}

Beim Erstellen eines langer / lat, auch berechnet den (x, y, z) 3D-Punkt, der die äquivalente Position auf einer Einheitskugel darstellt am Ursprung zentriert ist.

Nun, um festzustellen, ob Punkt B näher ist A als Punkt zu Punkt C, gehen Sie wie folgt vor:

// is B nearer to A than C?
bool IsNearer (LongLat A, LongLat B, LongLat C)
{
  return (A.x * B.x + A.y * B.y + A.z * B.z) < (A.x * C.x + A.y * C.y + A.z * C.z);
}

und den Abstand zwischen zwei Punkten zu erhalten:

float Distance (LongLat A, LongLat B)
{
  // radius is the size of sphere your mapping long/lats onto
  return radius * acos (A.x * B.x + A.y * B.y + A.z * B.z);
}

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

Answer 5

Schalen Tabellen zum Nachschlagen für sin / cos / acos. Wird schneller, es gibt eine Menge von C / C ++ Fixpunkt Bibliotheken, die auch diejenigen umfassen.

Hier ist der Code von jemand anderem auf memoization . Welche funktionieren könnte, wenn die verwendeten tatsächlichen Werte mehr gruppierten sind.

Hier ist eine Frage SO auf Fixed Point .

Answer 6

Was ist der Flaschenhals? Ist das der Sinus / Cosinus-Funktion aufruft oder der Arcussinus Anruf?

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

1 = sin(x)^2 + cos(x)^2
cos(x) = sqrt(1 - sin(x)^2)

Aber Ich mag die Zuordnung Idee, so dass Sie nicht Werte haben Sie neu zu berechnen haben bereits berechnet. Obwohl vorsichtig sein, da die Karte sehr schnell sehr groß werden kann.

Answer 7

Wie genau müssen Sie die Werte sein?

Wenn Sie Ihre Werte ein wenig abzurunden dann könnte man das Ergebnis aller Lookups speichern und überprüfen, ob sie vor jeder Berechnung verwendet wurden?

Answer 8

Nun, da lat und lange garantiert innerhalb eines bestimmten Bereichs sein, könnten Sie für Sie Math irgendeine Form von einer Lookup-Tabelle versuchen verwenden. * Methodenaufrufe. Sprich, ein Dictionary<double,double>

Answer 9

Ich würde behaupten, dass Sie möchten, erneut prüfen, wie Sie diese Funktion gefunden der Engpass. (IE haben Sie das Anwendungsprofil?)

Die Gleichung erscheint mir sehr leicht und nicht verursachen keine Probleme. Zugegeben, ich weiß nicht, Ihre Anwendung und Sie sagen, Sie eine Menge von diesen Berechnungen.

Dennoch ist es etwas zu prüfen.

Answer 10

Als jemand anders erwähnt, sind Sie sicher, das ist Ihr Engpass?

Ich habe einige Performance-Tests eine ähnliche Anwendung getan, was ich bauen werde, wo ich eine einfache Methode aufrufen, mit Standard-trig eine Entfernung zwischen zwei Punkten zurückzukehren. 20.000 Anrufe es schiebt es ganz oben der Profilierung Ausgang, doch es gibt keinen Weg ich es schneller machen kann ... Es ist nur die Scher Anzahl der Anrufe.

In diesem Fall muss ich die # Anrufe reduzieren ... Nicht, dass dies der Engpass ist.

Answer 11

ich einen anderen Algorithmus verwenden für die Berechnung der Entfernung zwischen 2 lati / longi Positionen, könnte es leichter als bei Ihnen sein, da es nur, dass 1 Cos anrufen und 1 Sqrt Anruf.

public static double GetDistanceBetweenTwoPos(double lat1, double long1, double lat2, double long2)
{
  double distance = 0;
  double x = 0;
  double y = 0;

  x = 69.1 * (lat1 - lat2);
  y = 69.1 * (long1 - long2) * System.Math.Cos(lat2 / 57.3);

  //calculation base : Miles
  distance = System.Math.Sqrt(x * x + y * y);

  //Distance calculated in Kilometres
  return distance * 1.609;
}

Answer 12

hat jemand bereits erwähnt Memoisation und das ist ein bisschen ähnlich. wenn Sie den gleichen Punkt zu vielen anderen Punkten zu vergleichen, dann ist es besser, Teile dieser Gleichung vorauszuberechnen.

statt

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

hat:

double result = Math.Acos(lat2rad.sin * lat1rad.sin 
+ lat2rad.cos * lat1rad.cos * (lon2rad.cos * lon1rad.cos + lon1rad.sin * lon2rad.sin));

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