Dado dois lat / longs, como posso saber se eles estão a menos de 1,6 km um do outro?

8

Estou tentando implementar uma verificação muito eficiente para ver se dois pontos estão a uma milha um do outro, ou não.

Minha abordagem atual é calcular a distância de Haversine e verificar se está a menos de uma milha.

A eficiência é importante nesse caso, porque eu tenho que calcular esse sinalizador de sim / não para grandes conjuntos de registros.

me importo se eles estão a uma milha - nada mais sobre a distância importa para mim.

Então, qual é a maneira mais eficiente de saber se dois pontos lat / long estão a uma milha um do outro?

Em resposta aos comentários, estou fazendo isso no SQL Server. Meu código está abaixo.

CREATE FUNCTION dbo.USR_UFN_HAVERSINE_DISTANCE
(
  @LAT1 FLOAT(18)
 ,@LONG1 FLOAT(18)
 ,@LAT2 FLOAT(18)
 ,@LONG2 FLOAT(18)
 ,@UnitOfMeasure NVARCHAR(10) = 'KILOMETERS'
)
RETURNS FLOAT(18)
AS
BEGIN
  DECLARE
    @R FLOAT(8)
   ,@DLAT FLOAT(18)
   ,@DLON FLOAT(18)
   ,@A FLOAT(18)
   ,@C FLOAT(18)
   ,@D FLOAT(18)
   ;
  SET @R =
    CASE @UnitOfMeasure
      WHEN 'MILES'      THEN 3956.55 
      WHEN 'KILOMETERS' THEN 6367.45
      WHEN 'FEET'       THEN 20890584
      WHEN 'METERS'     THEN 6367450
      ELSE 6367.45  --km
    END
  SET @DLAT = RADIANS(@LAT2 - @LAT1);
  SET @DLON = RADIANS(@LONG2 - @LONG1);
  SET @A = SIN(@DLAT / 2) 
         * SIN(@DLAT / 2) 
         + COS(RADIANS(@LAT1))
         * COS(RADIANS(@LAT2)) 
         * SIN(@DLON / 2) 
         * SIN(@DLON / 2);
  SET @C = 2 * ASIN(MIN(SQRT(@A)));
  SET @D = @R * @C;
  RETURN @D;
END;
JosephStyons
fonte
Qual foi a sua pesquisa como possível candidato até agora?
PolyGeo
1
Você está procurando uma solução de software ou criando seu próprio código? O que você tentou até agora?
23416 MaryBeth
2
O que há de errado em apenas verificar a distância do porto? Você pode economizar um pouco de tempo de processamento apenas verificando a distância plana - a uma milha, a navalha não fará muita diferença.
Tom
4
você poderia apenas usar geomA.STDistance (geomB) <d?
Ian Turton
2
A verificação da "distância planar" sugerida pelo @Tom pode ser facilmente mal interpretada: para funcionar corretamente, é necessária uma interpretação cuidadosa. Um é o seguinte. Supondo que você nunca precise comparar pontos no meridiano de 180 graus ou nos pólos, você pode aplicar a fórmula pitagórica às coordenadas (lat1, cos (lat1) * lon1), (lat2, cos (lat2) * lon2). Em outras palavras, comparar (lat1-lat2) ^ 2 + (cos (lat1) * lon1-cos (lat2) * lon2) ^ 2 a 1/69 ^ 2 (todos em graus) indica se os dois pontos estão separados por uma milha (com uma precisão de uma fração de um por cento). Se isso é mais rápido que Haversine não está claro.
whuber

Respostas:

2

Experimente este método - pode não ser o melhor, mas pode limitar o espaço de pesquisa a alguns e, assim, ajudá-lo a acelerar o processo.

  1. Crie buffers de meia milha em todos os pontos
  2. Dissolver os tampões resultantes - garantir que não haja multipolígonos
  3. Qualquer ponto fora deste polígono agora é excluído do espaço de pesquisa

Certifique-se de criar índices espaciais e verifique se esse procedimento melhorou o tempo de resposta da consulta. Você também pode refinar a abordagem criando uma tabela próxima (o ESRI ArcGIS tem uma ferramenta) com 1 milha como critério.

addcolor
fonte
os buffers precisam ter um raio de uma milha, não precisam?
Radouxju 5/11
@radouxju, duas milhas e meia de cada ponto estão a uma milha de distância.
addcolor
1
Eu não entendo. Você deseja criar uma camada de polígono com base em um conjunto predefinido de pontos e, em seguida, use esse polígono com o algoritmo "ponto em polígonos" para descobrir se novos pontos estão a uma milha (então você precisa calcular o buffer de uma milha e raio) ... Ou trabalhe diretamente com todos os pontos, com buffers de meia milha, dissolva e selecione os buffers isolados com base na área (que você precisa calcular) Observe que 1) criar buffers de milha verdadeiros é bastante caro 2) dissolver é muito caro. Somente a opção 1 faz sentido para mim, se você reutilizar os polígonos várias vezes.
Radouxju 7/11
2

Se você trabalha em nível global, pode evitar calcular muito pecado e cos através de testes simples e diretos:

O primeiro teste para rastrear pontos antes de computar a haversine é excluir o ponto em que @DLAT> 0,015 graus (pode ser mais preciso, mas eu prefiro segurança).

Em uma segunda etapa, você também pode fazer isso com o @DLON em um determinado intervalo de latitude com um valor conservador (por exemplo, entre -60 e 60 graus, exclua o @DLON> 0,03 (= 0,015 / cos (60)).

Como 1 milha é muito pequena, você raramente precisará calcular Haversine com essas duas regras (exceto se trabalhar em áreas polares) e poderá substituir Haversine por Pitágoras (2 cossenos versus 2 senos e 2 cossenos com Haversine), como mencionado por @whuber.

radouxju
fonte