java - mapa - Forma más rápida de calcular la distancia geográfica entre dos puntos
distancia entre dos puntos terrestres (4)
Ese es el algoritmo de haversine, le proporcionará un nivel de precisión decente.
Si realmente son "millones" de puntos, quizás implemente un caché de cálculos que haya realizado ... si encuentra un par de coordenadas, ambas suficientemente cercanas a un par cuya distancia ya ha calculado, luego usa el valor en caché?
O intente guardar en caché algunos de los pasos intermedios, por ejemplo, conversiones de grado a radianes.
Pedí prestado el siguiente método desde algún lugar en Internet (no recuerdo dónde). Pero está haciendo un proceso directo, encontrando la distancia entre dos puntos de GPS. Funciona muy bien, excepto que puede ser un poco lento, ya que lo estoy ejecutando a través de millones de puntos. Me preguntaba si alguien sabe un enfoque que sería computacionalmente menos costoso.
La precisión debe estar en el área general de ''correcta'', pero no necesita ser 100% precisa.
private double distFrom(double lat1, double lng1, double lat2, double lng2) {
double earthRadius = 3958.75;
double dLat = Math.toRadians(lat2-lat1);
double dLng = Math.toRadians(lng2-lng1);
double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
Math.sin(dLng/2) * Math.sin(dLng/2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
return earthRadius * c;
}
}
Ps: efectivamente encontré varias otras preguntas relevantes, pero en realidad no se centran en mi preocupación por la velocidad.
Si sacrificas la precisión, puedes hacer algunas mejoras. Por lo que recuerdo, sin(x) es aproximadamente igual a x para x pequeño. También parece que está computando las mismas cosas varias veces, como: Math.sin(dLat/2) (que en realidad se puede aproximar a dLat/2 como se indicó anteriormente).
Sin embargo, si está haciendo millones de estas operaciones, lo haría en otro lugar.
¿Tu algoritmo es óptimo? ¿Tal vez estás haciendo demasiados cálculos simples?
Si los puntos provienen de la base de datos, ¿puede realizar los cálculos como procedimientos almacenados en el servidor de la base de datos?
Si busca los puntos más cercanos, ¿puede indexarlos de alguna manera?
¿Pueden los índices geoespaciales ayudarlo?
Puede probar la ley de los cosenos para la trigonometría esférica:
a = sin(lat1) * sin(lat2)
b = cos(lat1) * cos(lat2) * cos(lon2 - lon1)
c = arccos(a + b)
d = R * c
Pero será impreciso para distancias cortas (y probablemente solo marginalmente más rápido).
Hay una discusión completa aquí . Sin embargo, la fórmula de haversine es la más correcta, por lo tanto, aparte de lo que otros han sugerido, puede que no haya mucho que puedas hacer. La respuesta de @ Alnitak puede funcionar, pero las conversiones esféricas a cartesianas no son necesariamente rápidas.
Si no le importa ignorar el ligero achatamiento de la Tierra (y su código Haversine publicado lo hace de todos modos) considere preconvertir todas sus coordenadas esféricas (lat / long) en coordenadas cartesianas de longitud de unidad 3D primero, por:
Entonces su distancia esférica entre las coordenadas cartesianas p1 y p2 es simplemente:
r * acos(p1 . p2)
Como p1 y p2 tendrán una unidad de longitud, esto reduce a cuatro multiplicaciones, dos adiciones y una operación de trigonometría inversa por par.
También tenga en cuenta que el cálculo de los productos dot es un candidato ideal para la optimización, por ejemplo, a través de GPU, extensiones MMX, bibliotecas de vectores, etc.
Además, si su intención es ordenar los pares por distancia, potencialmente ignorando pares más distantes, puede diferir la costosa parte r*acos() de la ecuación clasificando la lista solo en el valor del producto de punto, ya que para todas las entradas válidas (es decir, el rango [-1, 1] ) está garantizado que:
acos(x) < acos(y) if x > y
Luego simplemente toma el acos() de los valores que realmente le interesan.
Re: las inexactitudes potenciales con el uso de acos() , esas son realmente solo significativas si estás usando variables de float precisión simple. El uso de un double con 16 dígitos significativos debería permitirle obtener distancias precisas de hasta un metro o menos.