A maneira mais rápida de encontrar a distância entre dois pontos lat / longos

Atualmente, tenho pouco menos de um milhão de locais em um banco de dados mysql, todos com informações de longitude e latitude.

Estou tentando encontrar a distância entre um ponto e muitos outros pontos através de uma consulta. Não é tão rápido quanto eu quero, especialmente com mais de 100 hits por segundo.

Existe uma consulta mais rápida ou possivelmente um sistema mais rápido que não seja o mysql para isso? Estou usando esta consulta:

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

Nota: A distância fornecida é em milhas . Se você precisar de Quilômetros , use em 6371vez de 3959.

• Crie seus pontos usando Pointvalores de Geometrytipos de dados na MyISAMtabela. A partir do Mysql 5.7.5, as InnoDBtabelas agora também suportam SPATIALíndices.

• Crie um SPATIALíndice nesses pontos

• Use MBRContains()para encontrar os valores:

  SELECT  *
  FROM    table
  WHERE   MBRContains(LineFromText(CONCAT(
          '('
          , @lon + 10 / ( 111.1 / cos(RADIANS(@lon)))
          , ' '
          , @lat + 10 / 111.1
          , ','
          , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @lat - 10 / 111.1 
          , ')' )
          ,mypoint)

ou MySQL 5.1acima e abaixo:

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

Isso selecionará todos os pontos aproximadamente dentro da caixa (@lat +/- 10 km, @lon +/- 10km).

Na verdade, isso não é uma caixa, mas um retângulo esférico: segmento da esfera de latitude e longitude. Isso pode diferir de um retângulo simples na Terra Franz Joseph , mas bastante próximo a ele na maioria dos lugares habitados.

• Aplique filtragem adicional para selecionar tudo dentro do círculo (não o quadrado)

• Possivelmente aplique filtragem fina adicional para levar em consideração a grande distância do círculo (para grandes distâncias)

Não é uma resposta específica do MySql, mas melhorará o desempenho da sua instrução sql.

O que você está efetivamente fazendo é calcular a distância de cada ponto da tabela, para ver se está dentro de 10 unidades de um determinado ponto.

O que você pode fazer antes de executar este sql é criar quatro pontos que desenham uma caixa de 20 unidades de um lado, com o seu ponto no centro, ou seja. (x1, y1). . . (x4, y4), onde (x1, y1) é (dado + 10 unidades, dado + Lat + 10 unidades). . . (determinadoLongo - 10 unidades, dadoLat -10 unidades). Na verdade, você só precisa de dois pontos, superior esquerdo e inferior direito, chame-os (X1, Y1) e (X2, Y2)

Agora, sua instrução SQL usa esses pontos para excluir linhas que definitivamente são mais de 10u do seu ponto especificado, ela pode usar índices nas latitudes e longitudes, portanto haverá ordens de magnitude mais rápidas do que as que você possui atualmente.

por exemplo

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

A abordagem da caixa pode retornar falsos positivos (você pode pegar pontos nos cantos da caixa que são> 10u a partir do ponto especificado), portanto, você ainda precisa calcular a distância de cada ponto. No entanto, isso novamente será muito mais rápido, porque você limitou drasticamente o número de pontos a serem testados nos pontos dentro da caixa.

Eu chamo essa técnica de "Pensar dentro da caixa" :)

Edição: isso pode ser colocado em uma instrução SQL?

Não tenho idéia do que o mySql ou Php é capaz, desculpe. Eu não sei onde o melhor lugar é construir os quatro pontos, ou como eles podem ser passados ​​para uma consulta mySql em Php. No entanto, depois de ter os quatro pontos, não há nada que o impeça de combinar sua própria instrução SQL com a minha.

select name, 
       ( 3959 * acos( cos( radians(42.290763) ) 
              * cos( radians( locations.lat ) ) 
              * cos( radians( locations.lng ) - radians(-71.35368) ) 
              + sin( radians(42.290763) ) 
              * sin( radians( locations.lat ) ) ) ) AS distance 
from locations 
where active = 1 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;

Eu sei que com o MS SQL eu posso criar uma instrução SQL que declara quatro carros alegóricos (X1, Y1, X2, Y2) e os calcula antes da instrução de seleção "principal", como eu disse, não tenho idéia se isso pode ser feito com MySql. No entanto, eu ainda estaria inclinado a criar os quatro pontos em C # e passá-los como parâmetros para a consulta SQL.

Desculpe, não posso ajudar mais, se alguém puder responder a partes específicas do MySQL e Php, sinta-se à vontade para editar essa resposta.

A seguinte função MySQL foi publicada nesta postagem do blog . Não testei muito, mas pelo que coletei na postagem, se seus campos de latitude e longitude estiverem indexados , isso poderá funcionar bem para você:

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(
  geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), 
  geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) 
    + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) 
    * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) 
    * 60 * 1.1515);
END $$

DELIMITER ;

Uso da amostra:

Assumindo uma tabela chamada placescom campos latitude& longitude:

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;

Eu precisava resolver um problema semelhante (filtrando linhas pela distância do ponto único) e, combinando a pergunta original com respostas e comentários, criei uma solução que funciona perfeitamente para mim no MySQL 5.6 e 5.7.

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance

coordinatesé campo com tipo POINTe tem SPATIALíndice
6371é para calcular distância em quilômetros
56.946285é latitude para ponto central
24.105078é longitude para ponto central
15é distância máxima em quilômetros

Nos meus testes, o MySQL usa o índice SPATIAL no coordinatescampo para selecionar rapidamente todas as linhas que estão dentro do retângulo e depois calcula a distância real de todos os locais filtrados para excluir locais dos cantos dos retângulos e deixar apenas locais dentro do círculo.

Esta é a visualização do meu resultado:

Estrelas cinzas visualizam todos os pontos no mapa, estrelas amarelas são aquelas retornadas pela consulta do MySQL. Estrelas cinzas dentro dos cantos do retângulo (mas fora do círculo) foram selecionadas MBRContains()e desmarcadas pela HAVINGcláusula.

se você estiver usando o MySQL 5.7. *, poderá usar st_distance_sphere (POINT, POINT) .

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance

SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

Esta é a consulta de cálculo de distância entre os pontos no MySQL, eu a usei em um banco de dados longo, funcionando perfeitamente! Nota: faça as alterações (nome do banco de dados, nome da tabela, coluna etc.) conforme seus requisitos.

set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

fonte

   select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;

Uma função MySQL que retorna o número de metros entre as duas coordenadas:

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

Para retornar o valor em um formato diferente, substitua o 6371000na função pelo raio da Terra em sua unidade escolhida. Por exemplo, quilômetros seriam 6371e milhas seriam 3959.

Para usar a função, basta chamá-la como faria com qualquer outra função no MySQL. Por exemplo, se você tivesse uma mesa city, poderia encontrar a distância entre todas as cidades e todas as outras cidades:

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`

O código completo com detalhes sobre como instalar como plugin do MySQL está aqui: https://github.com/lucasepe/lib_mysqludf_haversine

Eu publiquei este ano passado como comentário. Desde que gentilmente @TylerCollier me sugeriu postar como resposta, aqui está.

Outra maneira é escrever uma função UDF personalizada que retorne a distância do haversine de dois pontos. Esta função pode receber entrada:

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

Então, podemos escrever algo como isto:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

buscar todos os registros a uma distância menor que 40 quilômetros. Ou:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

buscar todos os registros com uma distância inferior a 25 pés.

A função principal é:

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}

Uma aproximação rápida, simples e precisa (para distâncias menores) pode ser feita com uma projeção esférica . Pelo menos no meu algoritmo de roteamento, recebo um aumento de 20% em comparação com o cálculo correto. No código Java, ele se parece com:

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

Não tenho certeza sobre o MySQL (desculpe!).

Certifique-se de conhecer a limitação (o terceiro parâmetro de assertEquals significa a precisão em quilômetros):

    float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);

Aqui está uma descrição muito detalhada da Geo Distance Search com MySQL, uma solução baseada na implementação da Haversine Formula no mysql. A descrição completa da solução com teoria, implementação e otimização de desempenho adicional. Embora a parte de otimização espacial não funcionou corretamente no meu caso. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

Leia a Pesquisa por distância geográfica com o MySQL , uma solução baseada na implementação da Haversine Formula no MySQL. Esta é uma descrição completa da solução com teoria, implementação e otimização de desempenho adicional. Embora a parte de otimização espacial não funcione corretamente no meu caso.

Notei dois erros nisso:

1. o uso de absna instrução select na p8. Eu apenas omiti abse funcionou.

2. a função de distância de busca espacial na p27 não converte em radianos ou multiplica a longitude por cos(latitude), a menos que seus dados espaciais sejam carregados com isso em consideração (não é possível distinguir do contexto do artigo), mas seu exemplo na p26 indica que seus dados espaciais POINTnão são carregados com radianos ou graus.

$objectQuery = "SELECT table_master.*, ((acos(sin((" . $latitude . "*pi()/180)) * sin((`latitude`*pi()/180))+cos((" . $latitude . "*pi()/180)) * cos((`latitude`*pi()/180)) * cos(((" . $longitude . "- `longtude`)* pi()/180))))*180/pi())*60*1.1515  as distance FROM `table_post_broadcasts` JOIN table_master ON table_post_broadcasts.master_id = table_master.id WHERE table_master.type_of_post ='type' HAVING distance <='" . $Radius . "' ORDER BY distance asc";

Usando o mysql

SET @orig_lon = 1.027125;
SET @dest_lon = 1.027125;

SET @orig_lat = 2.398441;
SET @dest_lat = 2.398441;

SET @kmormiles = 6371;-- for distance in miles set to : 3956

SELECT @kmormiles * ACOS(LEAST(COS(RADIANS(@orig_lat)) * 
 COS(RADIANS(@dest_lat)) * COS(RADIANS(@orig_lon - @dest_lon)) + 
 SIN(RADIANS(@orig_lat)) * SIN(RADIANS(@dest_lat)),1.0)) as distance;

Veja: https://andrew.hedges.name/experiments/haversine/

Consulte: https://stackoverflow.com/a/24372831/5155484

Veja: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

NOTA: LEASTé usado para evitar valores nulos como um comentário sugerido em https://stackoverflow.com/a/24372831/5155484