Dados dos lat / longs, ¿cómo puedo saber si están dentro de 1 milla el uno del otro?

8

Estoy tratando de implementar una verificación muy eficiente para ver si dos puntos están a una milla uno del otro, o no.

Mi enfoque actual es calcular la distancia de Haversine y luego verificar para ver si es menos de una milla.

La eficiencia importa en este caso porque tengo que calcular este indicador sí / no para grandes conjuntos de registros.

Solo me importa si están dentro de una milla , nada más sobre la distancia me importa.

Entonces, ¿cuál es la forma más eficiente de saber si dos puntos lat / long están a una milla de distancia?

En respuesta a los comentarios, estoy haciendo esto en SQL Server. Mi codigo esta abajo.

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;
distance sql-server algorithm software-recommendations JosephStyons
fuente
¿Qué ha resultado su investigación como posible candidato hasta ahora?
PolyGeo
1
¿Está buscando una solución de software o está creando su propio código? ¿Qué has intentado hasta ahora?
MaryBeth
2
¿Qué hay de malo con solo verificar la distancia de Haversine? Puede ahorrar un poco de tiempo de procesamiento simplemente verificando la distancia plana: a una milla, la Haversine no hará una gran diferencia.
Tom
44
¿podrías usar geomA.STDistance (geomB) <d?
Ian Turton
2
La comprobación de "distancia plana" sugerida por @Tom podría malinterpretarse fácilmente: para funcionar correctamente, necesita una interpretación cuidadosa. Uno es el siguiente. Suponiendo que nunca tenga que comparar puntos a través del meridiano de 180 grados o los polos, podría aplicar la fórmula pitagórica a las coordenadas (lat1, cos (lat1) * lon1), (lat2, cos (lat2) * lon2). En otras palabras, comparar (lat1-lat2) ^ 2 + (cos (lat1) * lon1-cos (lat2) * lon2) ^ 2 a 1/69 ^ 2 (todo en grados) le dice si los dos puntos están separados por una milla (con una precisión de una fracción de un porcentaje). Si esto es más rápido que Haversine no está claro.
whuber

Respuestas:

2

Pruebe este método; puede que no sea el mejor, pero podría limitar su espacio de búsqueda a unos pocos y, por lo tanto, ayudarlo a acelerar el proceso.

  1. Crea amortiguadores de media milla alrededor de cada punto
  2. Disuelva los tampones resultantes: asegúrese de que no haya multipolígonos
  3. Cualquier punto que se encuentre fuera de este polígono ahora está excluido del espacio de búsqueda

Asegúrese de haber creado índices espaciales y verifique si este procedimiento ha mejorado el tiempo de respuesta de su consulta. También puede refinar el enfoque creando una tabla cercana (ESRI ArcGIS tiene una herramienta) con 1 milla como criterio.

addcolor
fuente
los amortiguadores deben tener un radio de una milla, ¿no?
radouxju
@radouxju, dos millas y media de cada punto son 1 milla de distancia.
addcolor
1
No lo entiendo O desea crear una capa de polígono basada en un conjunto predefinido de puntos, luego use este polígono con un algoritmo de "punto en polígonos" para averiguar si los nuevos puntos están dentro de una milla (entonces necesita calcular el búfer de radio de una milla ... O trabaje directamente con todos los puntos, con buffers de media milla, disuelva y luego seleccione los buffers aislados según el área (que necesita calcular). Tenga en cuenta que 1) crear buffers de 1 milla es bastante costoso 2) disolver es bastante caro. Solo la opción 1 tiene sentido para mí, si reutiliza los polígonos varias veces.
radouxju
2

Si trabaja a nivel mundial, puede evitar calcular muchos pecados y cos mediante simples pruebas directas:

La primera prueba para detectar puntos antes de calcular haversine es excluir el punto donde @DLAT> 0.015 grados (podría ser más preciso, pero prefiero la seguridad).

En un segundo paso, también puede hacer esto con @DLON en un rango de latitud dado con un valor conservador (por ejemplo, entre -60 y 60 grados, excluya @DLON> 0.03 (= 0.015 / cos (60)).

Debido a que 1 milla es bastante pequeña, rara vez necesitará calcular Haversine con estas dos reglas (excepto si trabaja en áreas polares), y podría reemplazar Haversine con Pitágoras (2 cosenos versus 2 senos y 2 cosenos con Haversina) como se mencionó por @whuber.

radouxju
fuente