Algoritmo para encontrar todas las ubicaciones de latitud y longitud dentro de una cierta distancia desde una ubicación de Lat Lng determinada

Dada una base de datos de lugares con ubicaciones de latitud + longitud, como 40.8120390, -73.4889650, ¿cómo puedo encontrar todas las ubicaciones dentro de una distancia determinada de una ubicación específica?

No parece muy eficiente seleccionar todas las ubicaciones de la base de datos y luego revisarlas una por una, obteniendo la distancia desde la ubicación de inicio para ver si están dentro de la distancia especificada. ¿Existe una buena manera de reducir las ubicaciones seleccionadas inicialmente de la base de datos? Una vez que tengo (¿o no?) Un conjunto reducido de ubicaciones, ¿todavía las reviso una por una para verificar la distancia, o hay una mejor manera?

El idioma en el que hago esto realmente no importa. ¡Gracias!

Empiece por comparar la distancia entre latitudes. Cada grado de latitud se encuentra a aproximadamente 111 kilómetros (69 millas) de distancia. El rango varía (debido a la forma ligeramente elipsoide de la Tierra) de 68.703 millas (110.567 km) en el ecuador a 69.407 (111.699 km) en los polos. La distancia entre dos ubicaciones será igual o mayor que la distancia entre sus latitudes.

Tenga en cuenta que esto no es cierto para las longitudes: la longitud de cada grado de longitud depende de la latitud. Sin embargo, si sus datos están limitados a un área (un solo país, por ejemplo), también puede calcular los límites mínimo y máximo para las longitudes.

Continuará con un cálculo de distancia rápido y de baja precisión que asume tierra esférica:

La distancia d del gran círculo entre dos puntos con coordenadas {lat1, lon1} y {lat2, lon2} viene dada por:

d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))

Una fórmula matemáticamente equivalente, que está menos sujeta a errores de redondeo para distancias cortas es:

d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 +
    cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))

d es la distancia en radianes

distance_km ≈ radius_km * distance_radians ≈ 6371 * d

(6371 km es el radio promedio de la tierra )

Los requisitos computacionales de este método son mínimos. Sin embargo, el resultado es muy preciso para distancias pequeñas.

Luego, si está a una distancia determinada, más o menos, utilice un método más preciso.

GeographicLib es la implementación más precisa que conozco, aunque también se puede usar la fórmula inversa de Vincenty .

Si está utilizando un RDBMS, configure la latitud como clave principal y la longitud como clave secundaria. Consulte por un rango de latitud, o por un rango de latitud / longitud, como se describe anteriormente, luego calcule las distancias exactas para el conjunto de resultados.

Tenga en cuenta que las versiones modernas de los principales RDBMS admiten consultas y tipos de datos geográficos de forma nativa.

Según la latitud, la longitud y la distancia del usuario actual que desea encontrar, la consulta sql se muestra a continuación.

SELECT * FROM(
    SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t
WHERE distance <= @distance

@latitude y @longitude son la latitud y la longitud del punto. La latitud y la longitud son las columnas de la tabla de distancias. El valor de pi es 22/7

Las extensiones de PostgreSQL GIS pueden ser útiles, ya que es posible que ya implemente gran parte de la funcionalidad que está pensando implementar.

Tank´s Yogihosting

Tengo en mi base de datos un grupo de tablas de Open Streep Maps y probé con éxito.

La distancia funciona bien en metros.

SET @orig_lat=-8.116137;
SET @orig_lon=-34.897488;
SET @dist=1000;

SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100;

Estas preguntas pueden resultarle útiles:

• Fórmulas para calcular la proximidad geográfica
• Longitud máxima de un grado decimal de latitud / longitud?

Como mencionó biziclop, una especie de árbol de espacio métrico probablemente sería su mejor opción. Tengo experiencia en el uso de árboles kd y árboles cuádruples para hacer este tipo de consultas de rango y son increíblemente rápidos; tampoco son tan difíciles de escribir. Sugeriría buscar en una de estas estructuras, ya que también le permiten responder otras preguntas interesantes como "¿cuál es el punto más cercano en mi conjunto de datos a este otro punto?"

Lo que necesitas es una búsqueda espacial. Puede utilizar la búsqueda espacial de Solr . También tiene el tipo de datos lat / long incorporado, verifique aquí .

Puede convertir la latitud-longitud al formato UTM, que es un formato métrico que puede ayudarlo a calcular distancias. Entonces puede decidir fácilmente si el punto cae en una ubicación específica.

Dado que dice que cualquier idioma es aceptable, la elección natural es PostGIS:

SELECT * FROM places
WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres;

Si desea utilizar el dato WGS, debe configurarlo $spheroiden'SPHEROID["WGS 84",6378137,298.257223563]'

Suponiendo que haya indexado placespor la geomcolumna, esto debería ser razonablemente eficiente.

Gracias a la solución proporcionada por @yogihosting, pude lograr un resultado similar de columnas sin esquema de mysql con los códigos que se muestran a continuación:

// @params - will be bound to named query parameters
$criteria = [];
$criteria['latitude'] = '9.0285183';
$criteria['longitude'] = '7.4869546';
$criteria['distance'] = 500;
$criteria['skill'] = 'software developer';

// Get doctrine connection 
$conn = $this->getEntityManager()->getConnection();

        $sql = '
               SELECT DISTINCT m.uuid AS phone, (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) AS distance FROM member_profile AS m 
               INNER JOIN member_card_subscription mcs ON mcs.primary_identity = m.uuid
               WHERE mcs.end > now() AND JSON_SEARCH(m.skill_logic, "one", :skill) IS NOT NULL  AND (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) <= :distance ORDER BY distance
               ';
        $stmt = $conn->prepare($sql);
        $stmt->execute(['latitude'=>$criteria['latitude'], 'longitude'=>$criteria['longitude'], 'skill'=>$criteria['skill'], 'distance'=>$criteria['distance']]);
        var_dump($stmt->fetchAll());

Tenga en cuenta que el fragmento de código anterior utiliza la conexión de doctrine DB y PHP

puedes comprobar esta ecuación, creo que te ayudará

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;