algorithm - ubicados - Cálculo de distancia entre 2 ciudades

formula de distancia

Question

¿Cómo se calcula la distancia entre 2 ciudades?

Answer 1

@Jared - una pequeña corrección a su ejemplo de código. La última línea del primer ejemplo de código debería decir:

dist = sqrt(dx*dx + dy*dy);

Answer 2

Encuentra el Lat / Lon de la ciudad, luego usa un algoritmo de estimación de distancia para coordenadas Lat / Lon.

Answer 3

Es mejor usar una tabla de búsqueda para obtener la distancia entre dos ciudades.

Esto tiene sentido porque * La Fórmula para calcular la distancia es bastante computacionalmente intensiva .. * Es poco probable que la distancia entre ciudades cambie.

Así que, a menos que las necesidades sean muy específicas (como el mapeo del terreno desde un satélite o algún algoritmo de topografía u otra cosa), debería guardar la lista de ciudades y distancias entre ellas en una tabla y buscarla según sea necesario.

Answer 4

He estado trabajando mucho con esto recientemente. Estoy descubriendo que las nuevas características de SQL2008 realmente lo hacen fácil. Puedo encontrar todos los puntos que están dentro de Xkm de una tabla de grabación de 100k en un tiempo de menos de un segundo ... no muy mal.

El método del gran círculo (suposición esférica) en mi prueba fue de aproximadamente 2,5 millas de distancia cuando se compara con la fórmula de Vincent (suposición elipsoidal, que es lo que es la Tierra).

El verdadero truco es obtener lat y long ... para eso estoy usando Google.

Answer 5

Puede usar el algoritmo A * para encontrar la ruta más corta entre esas dos ciudades y de esta manera tendrá la distancia.

Answer 6

Si estás hablando de la distancia más corta entre dos ciudades reales en un planeta esférico real, como la Tierra, quieres la distancia del círculo grande .

Answer 7

Si estás trabajando en el avión y quieres la distancia euclidiana "en línea recta":

// Cities are points x0,y0 and x1,y1 in kilometers or miles or Smoots[1]
dx = x1 - x0;
dy = y1 - y0;
dist = sqrt(dx*dx + dy*y);

¡No se necesita trigonometría! Solo el teorema de Pitágoras y el hecho de que los cuadrados siempre son positivos, entonces no necesitas dx = abs (x1 - x0), etc. para obtener un número positivo para pasar a sqrt ().

Tenga en cuenta que probablemente podría hacer esto en una línea y un compilador probablemente lo reduciría en el código anterior equivalente:

dist = sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));

[1] http://en.wikipedia.org/wiki/Smoot

Answer 8

si necesita un ejemplo de código, creo que tengo uno que podría desenterrar en casa, pero al igual que muchas de las respuestas anteriores, necesita un db largo / lat para hacer el cálculo

Answer 9

Usas la fórmula Haversine .

Answer 10

Esto es muy fácil de hacer con el tipo de geografía en SQL Server 2008.

SELECT geography::Point(lat1, lon1, 4326).STDistance(geography::Point(lat2, lon2, 4326))
-- computes distance in meters using eliptical model, accurate to the mm

4326 es SRID para el modelo de tierra elipsoidal WGS84

Answer 11

Si necesita tener en cuenta la curvatura de la Tierra, la distancia del Gran Círculo es lo que está buscando. Es probable que el artículo de Wikipedia explique mejor cómo funciona la fórmula que yo, y también está la página del formulario de aviación que abarca más detalles.

Las fórmulas son solo la primera parte del rompecabezas, si necesitas hacer que esto funcione para ciudades arbitrarias, necesitarás una base de datos de ubicación para obtener el lat / long. Afortunadamente, puede obtenerlo gratis de Geonames.org , aunque hay db comerciales disponibles (pregunte en google). Por lo tanto, en general, busque las dos ciudades que desee, obtenga los co-orinates lat / long y conéctelos a la fórmula como en el Ejemplo trabajado de Wikipedia.

Otras sugerencias:

• Para una solución comercial completa, hay PC Miler que muchas empresas de transporte utilizan para calcular las tarifas de envío.
• Realice llamadas a la API de Google Maps (u otra). Si necesita hacer muchas solicitudes por día, considere almacenar en caché los resultados en el servidor.
• También es muy importante considerar la construcción de una base de datos de equivalencia para ciudades, suburbios, ciudades, etc., si cree que alguna vez necesitará agrupar sus datos. Sin embargo, esto se vuelve realmente complicado y es posible que no encuentre una solución única para su problema.

Por último, pero no menos importante, Joel escribió un artículo sobre este problema hace un tiempo, así que aquí tienes: Nueva función: Búsqueda de empleo

Answer 12

Estoy de acuerdo en que una vez que tenga la información, si no va a cambiar, guárdela de alguna manera. @Marko Tinto Gracias por la muestra de T-SQL. Para aquellos que no tienen acceso a SQL Server o prefieren otro método: si necesita una gran precisión, consulte la entrada de Wikipedia en el algoritmo de Vincenty para obtener más información. Creo que hay una implementación de js, que (si no es que ya) se podría portar fácilmente a otros idiomas. Además, en la parte inferior de esa página hay un enlace a geographicLib , que pretende ser 1000 veces más preciso que el algoritmo de Vincenty (si tiene datos tan buenos, podría importar).

¿Por qué usarías algo como el método Vincenty? Porque la tierra no es una esfera perfecta y métodos como ese permiten ingresar un eje mayor y menor más preciso para modelar la Tierra.

Answer 13

yo uso distancy tan simple y limpio

Answer 14

Puedes obtener la distancia entre dos ciudades desde google map api. Aquí hay una implementación de esto en Python

#!/usr/bin/python
import requests
from sys import argv 
def get_distance(origin,destination):
    gmap=''http://maps.googleapis.com/maps/api/distancematrix/json''
    payload={"origins":origin,"destinations":destination,"sensor":''false'' }
    try:
        a=requests.get(gmap,params=payload)
        data = a.json()
        origin = str(data[''origin_addresses''][0])
        destination= str(data[''destination_addresses''][0])
        distance = data[''rows''][0][''elements''][0][''distance''][''text'']
        return distance,origin,destination
    except Exception,e:
        print "The %s or %destination does not exists :(" %(origin,destination)
        exit()

if __name__=="__main__":
    if len(argv)<3:
        print "sorry Check the format"
    else:
        origin=argv[1]
        destination=argv[2]
        distance,origin,destination=get_distance(origin,destination)
        print "%s ---> %s    :   %s" %(origin,destination,distance)

Enlace de ejemplo: https://gist.github.com/sarathsp06/cf063e47bcc515b51c84