algorithm - saber - lector de coordenadas

¿Cómo puedo hacer búsquedas de rango eficientes+contar con datos de latitud/longitud?

Question

Estoy trabajando con un gran conjunto de puntos representados por pares de latitud / longitud (los puntos no son necesariamente únicos, podría haber varios puntos en el conjunto que están en la misma ubicación). Los puntos se almacenan en una base de datos.

Lo que necesito hacer es encontrar una forma de realizar una búsqueda de manera eficiente para obtener la cantidad de puntos que se encuentran dentro de un radio dado (digamos, 25 millas) de un punto arbitrario. No es necesario que el recuento sea 100% exacto; lo que es más importante, debe ser rápido y razonablemente cercano al recuento correcto. Hacer esto con SQL es posible, al usar una consulta con algo de trigonometría en la cláusula WHERE para filtrar puntos por su distancia a un punto de referencia. Desafortunadamente, esta consulta es muy, muy costosa y no es probable que el almacenamiento en caché proporcione mucha ayuda porque las ubicaciones estarán muy dispersas.

En última instancia, estoy buscando construir algún tipo de estructura en memoria que sea capaz de manejar este tipo de operaciones de manera eficiente, intercambiando parte de la precisión y vitalidad de los datos (tal vez reconstruyéndola solo una vez al día) a cambio de velocidad. . He estado investigando kd-trees, pero aún no tengo claro qué tan bien se puede aplicar a los datos de latitud / longitud (a diferencia de los datos x, y en un plano 2d).

Si alguien tiene ideas o soluciones que debería considerar, realmente lo agradecería, así que gracias de antemano.

Answer 1

¿Podría proporcionar una muestra de su consulta cara existente?

Si está haciendo el cálculo correcto de círculo máximo basado en tomar el seno () y el coseno () del punto de referencia y los otros puntos de datos, entonces se podría hacer una optimización muy sustancial almacenando esos valores sin / cos en la base de datos además de los valores lat / long.

Alternativamente, simplemente use su base de datos para extraer un rectángulo de lat / long range que coincida, y solo luego filtre los que están fuera del verdadero radio circular.

Pero tenga en cuenta que un grado de longitud es una distancia algo más corta en latitudes altas que en el ecuador. Sin embargo, debería ser fácil determinar la relación de aspecto correcta para ese rectángulo. También tendría errores si necesita considerar áreas muy cercanas a los polos, ya que una selección de rectángulo no podría hacer frente a un círculo que se superpone a un polo.

Answer 2

Este UDF (Servidor SQL) obtendrá la distancia entre dos puntos lat / lon:

CREATE FUNCTION [dbo].[zipDistance] (
    @Lat1 decimal(11, 6),
    @Lon1 decimal(11, 6),
    @Lat2 decimal(11, 6),
    @Lon2 decimal(11, 6)
)
RETURNS
    decimal(11, 6) AS
BEGIN

    IF @Lat1 = @Lat2 AND @Lon1 = @Lon2
        RETURN 0 /* same lat/long points, 0 distance = */

    DECLARE @x decimal(18,13)
    SET @x = 0.0

    /* degrees -> radians */
    SET @Lat1 = @Lat1 * PI() / 180
    SET @Lon1 = @Lon1 * PI() / 180
    SET @Lat2 = @Lat2 * PI() / 180
    SET @Lon2 = @Lon2 * PI() / 180

    /* accurate to +/- 30 feet */
    SET @x = Sin(@Lat1) * Sin(@Lat2) + Cos(@Lat1) * Cos(@Lat2) * Cos(@Lon2 - @Lon1)
    IF 1 = @x
        RETURN 0

    DECLARE @EarthRad decimal(5,1)
    SET @EarthRad = 3963.1

    RETURN @EarthRadius * (-1 * ATAN(@x / SQRT(1 - @x * @x)) + PI() / 2)

END

Y, obviamente, puede usar esto en una consulta separada, como por ejemplo:

SELECT * FROM table WHERE [dbo].[zipDistance] < 25.0

Answer 3

Usa R-Trees .

En Oracle, utilizando Oracle Spatial, puede crear un índice:

CREATE INDEX ix_spatial ON spatial_table (locations) INDEXTYPE IS MDSYS.SPATIAL_INDEX;

eso creará un R-Tree para ti y buscará sobre él.

Puede usar cualquier Earth Model le guste: WGS84 , PZ-90 etc.

Answer 4

Utilice algún tipo de árbol de búsqueda para datos espaciales, por ejemplo, un árbol cuádruple . Más estructuras de datos de este tipo se mencionan en "Ver también".

Answer 5

Puede encontrar una excelente explicación de la sugerencia de Bombe en el artículo de Jan Philip Matuschek " Encontrar puntos dentro de una distancia de una latitud / longitud usando coordenadas delimitadas ".

Answer 6

No creo que debas usar esta solución. Después de haber pensado al azar sobre esto hace unos días, creo que al medir la distancia desde un punto específico, las ubicaciones de los cuadrados de la cuadrícula se basarán en círculos en lugar de en una cuadrícula uniformada. Cuanto más lejos estés de 0,0 eres menos preciso será.

Lo que hice fue tener 2 valores adicionales en mi clase PostalCode. Cada vez que actualizo el Long / Lat en un PostalCode, calculo una X, Y distancia de Long 0, Lat 0.

public static class MathExtender
{
    public static double GetDistanceBetweenPoints(double sourceLatitude, double sourceLongitude, double destLatitude, double destLongitude)
    {
        double theta = sourceLongitude - destLongitude;
        double distance =
            Math.Sin(DegToRad(sourceLatitude))
            * Math.Sin(DegToRad(destLatitude))
            + Math.Cos(DegToRad(sourceLatitude))
            * Math.Cos(DegToRad(destLatitude))
            * Math.Cos(DegToRad(theta));
        distance = Math.Acos(distance);
        distance = RadToDeg(distance);
        distance = distance * 60 * 1.1515;
        return (distance);
    }


    public static double DegToRad(double degrees)
    {
        return (degrees * Math.PI / 180.0);
    }

    public static double RadToDeg(double radians)
    {
        return (radians / Math.PI * 180.0);
    }
}

Luego actualizo mi clase así:

private void CalculateGridReference()
{
    GridReferenceX = MathExtender.GetDistanceBetweenPoints(0, 0, 0, Longitude);
    GridReferenceY = MathExtender.GetDistanceBetweenPoints(0, 0, Latitude, 0);
}

Así que ahora tengo una distancia de cuadrícula x, y (en millas) desde la referencia de cuadrícula 0,0 para cada fila en mi base de datos. Si quiero encontrar todos los lugares con 5 millas de largo / lat, primero obtendría la referencia de la cuadrícula X, Y (digamos 25,75) luego buscaría 20 ... 30, 70 ... 80 en la base de datos, y más filtrar los resultados en memoria usando

MathExtensder.GetDistanceBetweenPoints(candidate.Lat, candidate.Long, search.Lat, search.Long) < TheRadiusOfInterest

La parte en DB es ultra rápida, y la parte en memoria funciona en un conjunto más pequeño para hacerlo ultra preciso.