15

Estou fazendo uma função em , na qual, dada uma coordenada GPS, ele buscará no banco de dados os locais registrados, que não são necessariamente fixos, dentro de uma determinada distância.

A minha dúvida é: como calculo a distância entre as coordenadas passadas e a coordenada registrada no banco de dados?

Dado que, possuo a seguinte função em PHP que calcula a distância entre duas coordenadas:

function calcDistancia($lat1, $long1, $lat2, $long2)
{
    $d2r = 0.017453292519943295769236;

    $dlong = ($long2 - $long1) * $d2r;
    $dlat = ($lat2 - $lat1) * $d2r;

    $temp_sin = sin($dlat/2.0);
    $temp_cos = cos($lat1 * $d2r);
    $temp_sin2 = sin($dlong/2.0);

    $a = ($temp_sin * $temp_sin) + ($temp_cos * $temp_cos) * ($temp_sin2 * $temp_sin2);
    $c = 2.0 * atan2(sqrt(a), sqrt(1.0 - a));

    return 6368.1 * $c;
}

E não estou conseguindo traduzir para uma expressão do tipo:

SELECT cidade.cid_id 
FROM cidade 
WHERE (expressão) < $distance

O que me sugerem?


Outra alternativa seria buscar todos os locais usando SQL (como tradicional) e verificar as distâncias usando PHP. Mas fico na dúvida, há alguma diferença no desempenho em relação a abordagem anterior?

4
  • Não seria mais viável ter uma tabela com a distância entre cada cidade? Commented 13/03/2014 às 13:04
  • 1
    @FelipeAvelar Não seria possível pois os valores seriam dinâmicos. A cidade nesse caso é só ilustrativo, estou trabalhando com "locais", que podem não ser fixos.
    – Lucas Lima
    Commented 13/03/2014 às 13:06
  • Implemente esta função no banco (stored function) e use seu comando SQL normalmente. dev.mysql.com/doc/refman/5.7/en/stored-routines.html
    – user4552
    Commented 13/03/2014 às 13:10
  • 3
    Outro ponto a considerar é o que o MySQL possui uma extensão para trabalhar com dados espaciais: dev.mysql.com/doc/refman/5.7/en/spatial-extensions.html
    – user4552
    Commented 13/03/2014 às 13:55

6 Respostas 6

14

Primeira essa função em PHP está incorreta (talvez tenha sido adaptada de uma versão em C++?). Uma versão corrigida é:

function calcDistancia($lat1, $long1, $lat2, $long2)
{
    $d2r = 0.017453292519943295769236;

    $dlong = ($long2 - $long1) * $d2r;
    $dlat = ($lat2 - $lat1) * $d2r;

    $temp_sin = sin($dlat/2.0);
    $temp_cos = cos($lat1 * $d2r);
    $temp_sin2 = sin($dlong/2.0);

    $a = ($temp_sin * $temp_sin) + ($temp_cos * $temp_cos) * ($temp_sin2 * $temp_sin2);
    $c = 2.0 * atan2(sqrt($a), sqrt(1.0 - $a));

    return 6368.1 * $c;
}

Com essa versão, fiz o seguinte teste:

echo '1: ' . calcDistancia(-11.531371, -46.559372, -11.686069, -46.305313) . "\n";
echo '2: ' . calcDistancia(-23.524487, -47.441711, -23.549078,-46.614304) . "\n";

E o resultado foi:

1: 32.574603346655

2: 84.362785480187

Nota: no teste 2, coloquei a distância de Sorocaba até São Paulo. O resultado parece bem satisfatório, pois de carro a distância é de aproximadamente 100km, mas em linha reta é realmente algo entre 80 a 90.

Veja o código no Codepad


Com base nisso, fiz a seguinte função MySQL:

CREATE FUNCTION DISTANCIA(
  lat1 DOUBLE, 
  long1 DOUBLE, 
  lat2 DOUBLE, 
  long2 DOUBLE) 
RETURNS DOUBLE DETERMINISTIC
BEGIN
    DECLARE d2r DOUBLE;
    DECLARE dlong DOUBLE;
    DECLARE dlat DOUBLE;
    DECLARE temp_sin DOUBLE;
    DECLARE temp_cos DOUBLE;
    DECLARE temp_sin2 DOUBLE;
    DECLARE a DOUBLE;
    DECLARE c DOUBLE;

    set d2r = 0.017453292519943295769236;

    set dlong = (long2 - long1) * d2r;
    set dlat = (lat2 - lat1) * d2r;

    set temp_sin = sin(dlat/2.0);
    set temp_cos = cos(lat1 * d2r);
    set temp_sin2 = sin(dlong/2.0);

    set a = (temp_sin * temp_sin) + (temp_cos * temp_cos) * (temp_sin2 * temp_sin2);
    set c = 2.0 * atan2(sqrt(a), sqrt(1.0 - a));

    return 6368.1 * c;

END//

Testei a função da seguinte forma:

select 
  DISTANCIA(-11.531371, -46.559372, -11.686069, -46.305313) as '1',
  DISTANCIA(-23.524487, -47.441711, -23.549078,-46.614304) as '2';

E o resultado foi:

1                  2
32.574603346655    84.362785480187

O mesmo do PHP!

Veja o Sqlfiddle


Atualização

A resposta do Paulo Rodrigues contém um método de cálculo inline (sem função) mais simples e com resultado muito próximo ao da função.

Fiz um Sqlfiddle para o teste #2 (Sorocaba/São Paulo) da seguinte forma:

select 6371 * 
    acos(
        cos(radians(-23.524487)) * 
        cos(radians(-23.549078)) * 
        cos(radians(-47.441711) - radians(-46.614304)) + 
        sin(radians(-23.524487)) *
        sin(radians(-23.549078))
    )

Obtive o valor 84.393323136458. Não é o mesmo resultado da função e não sei qual está mais correto, porém é uma forma muito mais simples e com boa aproximação!


Considerações de Desempenho

A função acima faz o cálculo bem e não será muito ineficiente porque não faz acesso à base. O problema é que ela exige a varredura de todas as linhas da tabela (table scan), já que não será usado nenhum índice. O mesmo ocorre com a fórmula da atualização acima.

Tabela auxiliar

Se a ideia é calcular a distância entre duas cidades já conhecidas e cadastradas no banco de dados, você pode criar uma tabela auxiliar cuja PK é composta por duas FKs para a cidade, mais um campo com a distância entre as duas. É como se cidade tivesse um relacionamento N:N com ela mesma. Essa tabela teria a distância calculada entre todas as cidades.

Obviamente isso vai exigir uma tabela com bastante registros. O número de cidades ao quadrado, mais precisamente.

Limitar a consulta a faixas de coordenadas

Esta seria uma abordagem híbrida, um pouco parecida com a ideia do @Miguel Angelo.

Ao invés de aplicar a função de distância para localizar cidades próximas comparando todas as cidades, primeiro verifique se o valor absoluto das coordenadas está razoavelmente próximo.

Suponha que você queira buscar a coordenada -23.524487, -47.441711. Então, filtre as cidades cujas coordenadas estão próximas a 23 e 47, depois aplique a função para obter o resultado mais preciso.

Exemplo:

SELECT cidade.cid_id 
  FROM cidade 
 WHERE cidade.latitude BETWEEN ($lat - $distance / 111.19) AND ($lat + $distance / 111.19)
   and cidade.longitude BETWEEN ($long - $distance / 111.19) AND ($long + $distance / 111.19)
   and distancia(cidade.latitude, cidade.longitude,  (expressão) < $distance

As duas primeiras cláusulas irão filtrar a latidade e a longitude. Se você criar um índice para essas colunas, esse filtro será muito eficiente.

Note que na comparação da $distancia com o valor em graus decimais, eu dividi a distância pela constante mágica 111.19 para fazer a conversão do valor em uma aproximação "bruta", isto é, que não leva em conta a curvatura da terra.

Depois, a função distancia() irá melhorar os resultados, pois ao invés de recuperar um "quadrado" geométrico cujas pontas não respeitam a distância, os resultados estarão dentro do círculo cujo raio é a distância.

5
  • Realmente, eu já possuía uma versão implementada em outro programa em C++. Posso editar a função da pergunta ou deixo como está?
    – Lucas Lima
    Commented 13/03/2014 às 13:51
  • @LucasNunes Por mim eu editaria, mas fica a seu critério, acho que todos conseguiram pegar a ideia.
    – utluiz
    Commented 13/03/2014 às 13:59
  • Uma dúvida (vale para a resposta do @Miguel Angelo também), nesse último caso (da busca por faixas de coordenadas), $distance deve ser dado em graus decimais, certo? Por exemplo, se eu quero buscar para uma distancia 5km, eu devo converter 5km para graus decimais?
    – Lucas Lima
    Commented 13/03/2014 às 14:20
  • @LucasNunes Realmente isso passou despercebido. Teria, sim, que aplicar um fator para transformar a distância em graus decimais. Como é em linha reta, seria muito mais simples. Vou atualizar a resposta.
    – utluiz
    Commented 13/03/2014 às 14:31
  • 1
    @LucasNunes Após sua excelente observação, fiz a atualização ajustando o valor da distância para graus decimais de uma forma simplista.
    – utluiz
    Commented 13/03/2014 às 14:45
5

Em MySQL, eu tenho algo assim (não utilizando functions), passando -19.83996, -43.94910, por exemplo:

6371 * acos(cos(radians(-19.83996)) * cos(radians(lat)) * cos(radians(-43.94910) - radians(lng)) + sin(radians(-19.83996)) * sin(radians(lat)))
1
  • 3
    +1 Executei num Sqlfiddle para o teste #2 que fiz na minha resposta e obtive 84.393323136458. Não é o mesmo resultado e não sei qual está mais correto, porém é um método muito mais simples e com boa aproximação!
    – utluiz
    Commented 13/03/2014 às 14:06
5

Eu não calcularia a distância no banco de dados não. Ao invés disso, eu pegaria todos os pontos que estivesses dentro de um quadrado, que facilita a query, e ainda pode fazê-la muito mais rápida pois só usa operadores de maior-que > e menor-que <, e então depois de retornados os resultados para o PHP, ai sim, selecionaria aqueles que tivesses dentro de um certa distância.

Exemplo: Suponha que as coordenadas do GPS sejam $x, $y, que a distância máxima seja $d. Então a query ficaria assim:

$sql = 'SELECT * FROM tabela WHERE coordX > '.($x-$d).' and coordX < '.($x+$d).
    ' and coordY > '.($y-$d).' and coordY < '.($y+$d);

Dessa forma a query vai rodar muito mais rápido. Ai então basta usar a função de calcular distâncias no PHP para que ao invés de retornar tudo que estiver dentro do quadrado, seja retornado tudo que estiver dentro do círculo.

3
  • É uma abordagem interessante se houver muitos dados na base. Mas por recuperar um quadrado, a acurácia do resultado não será tão boa.
    – utluiz
    Commented 13/03/2014 às 13:43
  • 2
    Mas ai é só filtrar no PHP como eu disse. O SQL retorna os que estiverem dentro do quadrado, e depois o PHP filtra os que estiverem dentro do círculo. Commented 13/03/2014 às 13:47
  • 1
    Sim, sim, não tinha visto a atualização ao final. De qualquer forma, dei +1 porque essa solução permite a otimização por índices.
    – utluiz
    Commented 13/03/2014 às 14:00
2

Caso você possa criar uma function em seu banco, vai depender de qual banco está usando, você poderia fazer os cálculos por ela.

Em PLSQL ficaria assim

create or replace
FUNCTION CALCULA_DISTACIA_COORD 
(
    LATITUDE1 IN NUMBER,    
    LONGITUDE1 IN NUMBER,   
    LATITUDE2 IN NUMBER,    
    LONGITUDE2 IN NUMBER    
) RETURN NUMBER AS
    GRAU_RAD NUMBER := 0.0174532925;
    DIST_LATITUDE NUMBER;
    DIST_LONGITUDE NUMBER;
    DISTANCIA NUMBER;
    COEFF_A NUMBER;
    LATITUDE1_RAD NUMBER;   
    LONGITUDE1_RAD NUMBER;  
    LATITUDE2_RAD NUMBER;   
    LONGITUDE2_RAD NUMBER;
BEGIN
    --Conversao de graus para radiandos
    LATITUDE1_RAD   := LATITUDE1 * GRAU_RAD; 
    LONGITUDE1_RAD  := LONGITUDE1 * GRAU_RAD; 
    LATITUDE2_RAD   := LATITUDE2 * GRAU_RAD; 
    LONGITUDE2_RAD  := LONGITUDE2 * GRAU_RAD; 

    DIST_LATITUDE := LATITUDE2_RAD - LATITUDE1_RAD;
    DIST_LONGITUDE := LONGITUDE2_RAD - LONGITUDE1_RAD;
    COEFF_A := power(sin(DIST_LATITUDE/2),2)+cos(LATITUDE1_RAD)*cos(LATITUDE2_RAD)*power(sin(DIST_LONGITUDE/2),2);

    --Calculo da distancia em metros. Valor multiplicado por 6378140, que indica o raio da terra em metros
    DISTANCIA := 6378140*(2*atan2(sqrt(COEFF_A), sqrt(1 - COEFF_A)));

    RETURN DISTANCIA;
END CALCULA_DISTACIA_COORD;

Aparentemente é possível criar functions nas versões mais recentes do mysql, mas nunca testei isso.

Se for possível, você chama a function diretamente no select...

1

segue a função do calculo de distancia do "utluiz" para Swift:

func calculateDistanceFromCoordinate(_latOrigem: Double, _lngOrigem: Double, _latDestino: Double, _lngDestino: Double) -> Double {
    let d2r: Double = 0.017453292519943295769236

    let dlong: Double = (_lngDestino - _lngOrigem) * d2r
    let dlat: Double = (_latDestino - _latOrigem) * d2r

    let temp_sin: Double = sin(dlat/2.0)
    let temp_cos: Double = cos(_latOrigem * d2r)
    let temp_sin2: Double = sin(dlong/2.0)

    let a: Double = (temp_sin * temp_sin) + (temp_cos * temp_cos) * (temp_sin2 * temp_sin2)
    let c: Double = 2.0 * atan2(sqrt(a), sqrt(1.0 - a))

    return 6368.1 * c;
}

//Exemplo:
let distance: Double = calculateDistanceFromCoordinate(-11.531371, _lngOrigem: -46.559372, _latDestino: -11.686069, _lngDestino: -46.305313)
1

Trabalho com dados geoespaciais e o mysql já tem suporte a geolocalização. Neste caso basta utilizar a função st_distance:

ST_Distance(Point(lon1, lat1), Point(lon2,lat2))

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .