Búsqueda de proximidad

Question

¿Cómo realiza una aplicación una búsqueda de proximidad? Por ejemplo, un usuario escribe un código postal, luego la aplicación enumera todas las empresas dentro de 20 millas ordenadas por proximidad.

Quiero construir algo así en PHP y MySQL. ¿Es correcto este enfoque?

1. Obtener las direcciones de las ubicaciones que me interesan y almacenarlas en mi base de datos
2. Geocodifique todas las direcciones con el servicio de geocodificación de Google
3. Escriba una consulta de base de datos que incluya la fórmula de Haversine para hacer la búsqueda de proximidad y ordenar

¿Está bien? En el paso 3, voy a calcular la proximidad para cada consulta. ¿Es mejor tener una tabla de PROXIMIDAD que enumere la distancia entre cada negocio y algunas ubicaciones de referencia?

Answer 1

Si hay suficientes registros para que la velocidad importe, aquí hay una manera de indexarlos con anticipación.

Defina una cuadrícula de contenedores a unas 20 millas de un lado. Almacene el número de contenedor con el registro de cada tienda. En el momento de la búsqueda, calcule los números de todos los contenedores que se cruzan en un radio de 20 millas desde su punto de búsqueda. Luego recupere todas las tiendas en cualquiera de esos contenedores y proceda como antes.

Answer 2

Usamos esto para hacer muchos miles de puntos. Es importante si está realizando esto en SQL tener un índice en la columna Latitud y Longitud. Intentamos hacer esto en SQL 2008 con índices espaciales, pero realmente no vimos el aumento de rendimiento que esperábamos. Sin embargo, si desea calcular dentro de una cierta distancia de un ZIP, debe pensar si va a utilizar el centroide ZIP o una representación poligonal del código postal.

Haversine forumla es un buen lugar para comenzar.

No hemos tenido problemas de rendimiento al calcular la distancia sobre la marcha, lo calculamos con anticipación para algunas aplicaciones donde conocemos los puntos de antemano y habrá millones de registros.

SELECT
        [DistanceRadius]=
        69.09 *
        DEGREES(
          ACOS(
            SIN( RADIANS(latitude) )*SIN( RADIANS(@ziplat) ) 
           +
            COS( RADIANS(latitude) )*COS( RADIANS(@ziplat) ) 
           *
            COS( RADIANS(longitude - (@ziplon)) )
          )
        )
        ,*
        FROM
            table

    ) sub
WHERE
    sub.DistanceRadius < @radius

Answer 3

Hacemos esto para aproximadamente 1200 ubicaciones. Simplemente usaría la fórmula de Haversine sobre la marcha, aunque dependiendo de su aplicación, podría ser mejor almacenarla en PHP en lugar de SQL. (Nuestra implementación está en .net, por lo que su kilometraje puede variar).

Realmente nuestro mayor inconveniente con la forma en que lo implementamos, es que cada cálculo (hasta hace poco) tenía que calcularse en el nivel de datos que era dolorosamente lento (cuando digo lento, realmente quiero decir que no instantáneo tomó un segundo más o menos), pero eso se debió al hecho de que tuvo que calcular la distancia para las 1200 ubicaciones en función del código postal suministrado.

Dependiendo de la ruta que elija, hay formas de acelerar los cálculos de distancia numérica, observando la longitud y latitud y eliminando las que están fuera de un rango predefinido (por ejemplo, si está buscando todas las direcciones dentro de 20 millas hay un rango de longitud en el que puede calcular en qué direcciones deben ubicarse para estar a 20 millas de distancia). Eso puede acelerar su consulta si es necesario.

Realmente buscamos almacenar todas las combinaciones posibles en nuestra base de datos. En realidad, parece que podría ser un gran almacén de datos, pero realmente no está en el gran alcance de las cosas. Con los índices puede ser bastante rápido, y no tiene que preocuparse por la optimización del algoritmo, etc. Decidimos en contra, porque teníamos la ecuación en C # y nos permitía almacenar en caché la información necesaria para hacer todos los cálculos en el nivel de negocios Cualquiera de los dos funcionará bien, es solo una cuestión de cuál es su preferencia.