Optimización de una función de cálculo de distancia

Question

En mi código tengo que hacer una gran cantidad de cálculos de distancia entre pares de valores lat/long.

el código es el siguiente:

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

(lat2rad por ejemplo, es la latitud convierte en radianes).

He identificado esta función como el cuello de botella de rendimiento de mi aplicación. ¿Hay alguna forma de mejorar esto?

(No puedo usar tablas de búsqueda ya que las coordenadas son variables). También miré this question donde se sugiere un esquema de búsqueda como una grilla, lo que podría ser una posibilidad.

¡Gracias por su tiempo! ;-)

Answer 1

Si su objetivo es clasificar (comparar) distancias, entonces aproximaciones (sin y cos a tabla) podrían reducir drásticamente la cantidad de cálculos requeridos (aplicar rápida rechazar.)

Su objetivo es solo proceder con el cálculo trigonométrico real si la diferencia entre las distancias aproximadas (para clasificar o comparar) cae por debajo de un cierto umbral.

E.g. utilizando tablas de búsqueda con 1000 muestras (es decir, sin y cos muestreadas cada 2*pi/1000), la incertidumbre de búsqueda es como máximo 0,006284. Utilizando uncertainty calculation para el parámetro ACos, la incertidumbre acumulada, también será la incertidumbre de umbral, será como máximo 0.018731.

lo tanto, si la evaluación de Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad) usando sin y cos tablas de búsqueda para dos pares de coordenadas-conjunto (distancias) produce una cierta clasificación (una distancia parece mayor que el otro basado en la aproximación), y el módulo de la diferencia es mayor que la umbral anterior, entonces la aproximación es válida. De lo contrario, proceda con el cálculo trigonométrico real.

Answer 2

¿Cuán exactos necesitas que sean los valores?

Si redondea sus valores un poco, puede almacenar el resultado de todas las búsquedas y verificar si se han utilizado antes de cada cálculo.

Answer 3

Cambiando a tablas de búsqueda para sin/cos/acos. Será más rápido, hay muchas bibliotecas de punto fijo c/C++ que también incluyen esas.

Aquí hay un código de otra persona en Memoization. Lo cual podría funcionar si los valores reales utilizados son más agrupados.

Aquí hay una pregunta sobre SO en Fixed Point.

Answer 4

¿El algoritmo CORDIC funcionaría para usted (en cuanto a velocidad/precisión)?

Answer 5

Bueno, como lat y lon están dentro de cierto rango, puede intentar usar algún tipo de tabla de búsqueda para sus llamadas al método Math. *. Decir, un Dictionary<double,double>

Answer 6

Usando la inspiración de @Brann, creo que se puede reducir un poco el cálculo (hay que advertir que ha pasado mucho tiempo desde que hice esto y será necesario verificarlo). Algún tipo de operaciones de búsqueda de los valores calculados previamente, probablemente, el más rápido, aunque

tiene:

1: ACOS (sen A sen B + COS Un COS B COS (AB))

pero 2: COS (AB) = sen a sen B + COS COS a B

que se reescribir como 3: sen a sen B = COS (AB) - COS Un COS B

sustituir sen a sen B en 1. usted tiene:

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

Precalcula X = COS (AB) e Y = COS A COS B y usted pone los valores en 4

para dar:

ACOS (XY + XY)

cálculos

4 trigonométricas en lugar de 6!

Answer 7

¿Qué es el cuello de la botella? ¿Son las llamadas a la función seno/coseno o la llamada arcoseno?

Si su seno llamadas/coseno son lentos, se puede usar el siguiente teorema para evitar tantas llamadas:

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

pero me gusta la idea de mapeo de modo que usted no tiene que volver a calcular los valores que' ve ya calculado. Aunque tenga cuidado ya que el mapa puede agrandarse muy rápidamente.

Answer 8

Yo diría que es posible que desee volver a examinar cómo encontró que esa función es el cuello de botella. (Es decir, ¿perfiló la aplicación?)

La ecuación para mí parece muy ligera y no debería causar ningún problema. De acuerdo, no conozco su aplicación y usted dice que hace muchos de estos cálculos.

Sin embargo, es algo a tener en cuenta.

Answer 9

cambiar la forma de almacenar a largo/Lat:

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

Al crear una larga/lat, también calcular el (x, y, z) de puntos 3D que representa la posición equivalente en una esfera unidad centrada en el origen.

Ahora, para determinar si el punto B está más cerca del punto A que el punto C, haga lo siguiente:

// 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); 
} 

y para obtener la distancia entre dos puntos:

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); 
} 

Podría quitar el término 'radio', que normaliza de manera efectiva las distancias.

Answer 10

Como alguien más señaló, ¿estás seguro de que este es tu cuello de botella?

He hecho algunas pruebas de rendimiento de una aplicación similar que estoy construyendo, donde llamo un método simple para devolver una distancia entre dos puntos usando un trigonometría estándar. 20,000 llamadas lo coloca justo en la parte superior de la salida de creación de perfiles, sin embargo, no hay manera de que pueda hacerlo más rápido ... Es solo el número de llamadas cortantes.

En este caso, necesito reducir las # llamadas a él ... No es que este sea el cuello de botella.

Answer 11

Utilizo un algoritmo diferente para calcular la distancia entre 2 posiciones de lati/longi, podría ser más ligero que el suyo, ya que solo hace 1 llamada Cos y 1 llamada Sqrt.

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

alguien ya ha mencionado la memorización y esto es un poco similar. Si comparas el mismo punto con muchos otros puntos, entonces es mejor precalcular partes de esa ecuación.

en lugar de

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

tienen:

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

y yo creo que es la misma fórmula que alguien más ha publicado debido a que parte de la ecuación desaparecerá cuando expande los soportes :)