Mais rápida maneira de encontrar distância entre dois Lat / Long Pontos

StackOverflow https://stackoverflow.com/questions/1006654

  •  06-07-2019
  •  | 
  •  

Pergunta

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

Eu estou tentando encontrar a distância entre um ponto e muitos outros pontos através de uma consulta. Não é tão rápido como eu quero que ele seja especialmente com mais de 100 batidas por segundo.

Existe uma consulta mais rápida ou, possivelmente, um sistema mais rápido com excepção mysql para isso? Eu 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 fornecido está em Miles . Se você precisa de Quilômetros , o uso 6371 vez de 3959.

Foi útil?

Solução

  • Crie seus pontos usando valores Point de tipos de dados Geometry na tabela MyISAM. A partir do MySQL 5.7.5, mesas InnoDB agora também suportam índices SPATIAL.

  • Criar um índice SPATIAL sobre estes 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, em MySQL 5.1 e acima: 

    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 irá selecionar todos os pontos de aproximadamente dentro da (@lat +/- 10 km, @lon +/- 10km) caixa.

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

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

  • Possivelmente aplicar multa adicional de filtragem para a conta para a grande distância círculo (para grandes distâncias)

Outras dicas

Não é uma resposta MySql específica, mas vai melhorar o desempenho de sua instrução SQL.

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

O que você pode fazer antes de executar este sql, é criar quatro pontos que atraem uma caixa de 20 unidades de um lado, com o seu ponto no centro ou seja .. (x1, y1). . . (X4, Y4), onde (x1, y1) é (givenlong + 10 unidades, givenLat + 10 unidades). . . (givenLong - 10units, givenLat -10 unidades). Na verdade, você só precisa de dois pontos, superior esquerdo e inferior direito chamada eles (X1, Y1) e (X2, Y2)

Agora, o seu SQL uso declaração destes pontos para excluir linhas que definitivamente são mais do que 10U de seu ponto dado, ele pode usar índices nas latitudes e longitudes, assim será também ordens de magnitude mais rápido do que o que você tem atualmente.

por exemplo. 

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

A abordagem caixa pode retornar falsos positivos (você pode pegar pontos nos cantos da caixa que estão> 10U do ponto dado), então você ainda precisa para calcular a distância de cada ponto. No entanto, este novo será muito mais rápido porque você limitou drasticamente o número de pontos de teste para os pontos dentro da caixa.

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

EDIT:? Isso pode ser colocado em uma instrução SQL

Eu não tenho idéia o que o MySQL ou PHP é capaz de, desculpe. Eu não sei onde é o melhor lugar para construir os quatro pontos, ou como poderiam ser passados ??para uma consulta de mysql no PHP. No entanto, uma vez que você tem os quatro pontos, não há nada que impeça você combinar sua própria instrução SQL com o meu. 

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 construir uma instrução SQL que declara quatro carros alegóricos (X1, Y1, X2, Y2) e calcula-los antes que o instrução select "main", como eu disse, eu não tenho idéia se isso pode ser feito com MySql. No entanto eu ainda estaria inclinado a construir os quatro pontos em C # e passá-los como parâmetros para a consulta SQL.

Desculpe, não posso ser de mais ajuda, se alguém pode responder às partes específicas do MySQL e PHP deste, sinta-se livre para editar esta resposta para fazê-lo.

Verifique esta apresentação para uma boa resposta. Basicamente ele mostra a duas diferentes abordagens mostrado nos comentários, com uma explicação detalhada sobre por que / quando você deve usar um ou o outro e por que o "na caixa" cálculo pode ser muito interessante.

Geo Distância Pesquisa com MySQL

em este post , a seguinte função MySql foi publicado. Eu não testei muito, mas pelo que eu recolhidos a partir do post, se sua latitude e longitude campos são indexados , isso pode 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 ;

Exemplo de uso: Assumindo uma tabela chamada Places com campos de latitude e longitude:

get_distance_in_miles_between_geo_locations seleccione (-34.017330, 22.809500, latitude, longitude) como distance_from_input de lugares;

todos roubado a partir deste post 

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 cálculo da distância entre dois pontos em MySQL, eu tê-lo usado em um longo banco de dados, o perfeito trabalho! Nota:. Fazer as mudanças (nome de banco de dados, nome da tabela, coluna etc) como por suas exigências 

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

Se você estiver usando o MySQL 5.7. *, Então você pode usar st_distance_sphere (ponto, ponto) . 

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

   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;

O código completo com detalhes sobre como instalar o MySQL plug-in está aqui: https://github.com/lucasepe / lib_mysqludf_haversine

Eu postei isso no ano passado como comentário. Desde @TylerCollier gentilmente me sugeriu postar como resposta, aqui está.

Outra forma é escrever uma função UDF personalizado que retorna a distância haversine a partir de dois pontos. Esta função pode tomar entrada: 

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

Assim, podemos escrever algo como isto: 

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

para buscar todos os registros com uma distância de menos de 40 quilômetros. Ou: 

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

para buscar todos os registros com uma distância de menos de 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;
}

Um rápido, simples e aproximação precisa (para distâncias menores) pode ser feito com um projeção esférica . Pelo menos no meu algoritmo de roteamento eu conseguir um aumento de 20% em comparação com o cálculo correto. No código Java que parece: 

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 MySQL (sorry!).

Certifique-se de que você sabe sobre a limitação (o terceiro param 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 Distância Pesquisa com MySQL uma solução baseada na implementação de Haversine Fórmula para mysql. A descrição solução completa com a teoria, implementação e otimização de desempenho. Embora a parte de otimização espacial não funcionou correta no meu caso. http://www.scribd.com/doc/2569355/Geo -Distância-Search-com-MySQL

Ter uma leitura de Geo Distância Pesquisa com MySQL , uma solução com base na implementação de Fórmula Haversine para MySQL. Esta é uma solução completa A inscrição com a teoria, implementação e otimização de desempenho. Embora a parte de otimização espacial não funcionar corretamente no meu caso.

notei dois erros no seguinte:

  1. o uso de abs na instrução select em P8. Eu só omitido abs e funcionou.

  2. a função de pesquisa distância espacial na p27 não converte para radianos ou longitude multiplicar por cos(latitude), a menos que seu dados espaciais é carregado com isso em consideração (não pode dizer a partir do contexto do artigo), mas o seu exemplo em p26 indica que sua POINT dados espaciais não é carregado com radianos ou graus.

A MySQL função 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 6371000 na função com o raio da Terra em sua escolha de unidade. Por exemplo, quilômetros seria 6371 e milhas seria 3959.

Para usar a função, basta chamá-lo como faria com qualquer outra função no MySQL. Por exemplo, se você tivesse um city mesa, você poderia encontrar a distância entre cada cidade para qualquer outra cidade: 

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`

eu precisava para resolver problema semelhante (filtragem linhas de distância do ponto de solteiro) e combinando pergunta original com respostas e comentários, eu vim com uma solução que funciona perfeitamente para mim em ambos 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 POINT e tem índice SPATIAL
6371 é para o cálculo da distância em quilômetros
56.946285 é latitude para o ponto de Central 24.105078 é longitude para o ponto de Central 10 é a distância máxima em quilómetros

Em meus testes, MySQL usa índice espacial no campo coordinates para selecionar rapidamente todas as linhas que estão dentro do retângulo e, em seguida, calcula a distância real para todos os lugares filtrados para excluir locais de cantos retângulos e deixar apenas lugares dentro do círculo.

Esta é a visualização do meu resultado:

mapa

Estrelas cinzentas visualizar todos os pontos no mapa, estrelas amarelas são aqueles retornados pela consulta MySQL. estrelas cinzentos no interior cantos do rectângulo (mas círculo exterior) foram seleccionados por MBRContains() e em seguida desativada pela cláusula HAVING.

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/

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

Veja: http://www.plumislandmedia.net/mysql/ -haversine-mysql mais próximo-loc /

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

$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";
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top