Как сделать эффективный поиск диапазона + подсчет с помощью данных широты/долготы?

Ответ 1

Я не думаю, что вы должны использовать это решение. Случайно подумав об этом несколько дней назад, я думаю, что, измеряя расстояние от конкретной точки, места сетки квадратов будут основаны на кругах, а не на сетке. Чем дальше от 0,0, тем менее точно это будет!

То, что я сделал, состояло в том, чтобы иметь 2 дополнительных значения в моем классе PostalCode. Всякий раз, когда я обновляю Long/Lat на PostalCode, я вычисляю расстояние X, Y от 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);
    }
}

Затем я обновляю свой класс следующим образом:

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

Итак, теперь у меня есть х, у расстояния сетки (в милях) от координатной сетки 0,0 для каждой строки в моей БД. Если я хочу найти все места с 5 милями длинного/лата, я бы сначала получил ссылку на X, Y (скажем, 25,75), тогда я бы искал 20..30, 70..80 в БД и далее фильтровать результаты в памяти с помощью

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

В части DB очень быстро, а часть в памяти работает на меньшем наборе, чтобы сделать ее более точной.

Ответ 2

Используйте R-Trees.

В Oracle, используя Oracle Spatial, вы можете создать индекс:

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

который создаст для вас R-Tree и выполнит поиск по нему.

Вы можете использовать любой Earth Model, который вам нравится: WGS84, PZ-90 и т.д.

Ответ 3

Используйте какое-то дерево поиска для пространственных данных, например. a quad tree. Более такие структуры данных упоминаются в разделе "См. Также".

Ответ 4

Вы можете найти отличное объяснение предложения Бомбе в статье Ян Филиппа Матушека " Поиск точек в пределах расстояния между широтой и долготой с использованием ограничивающих координат".

Ответ 5

Не могли бы вы предоставить образец существующего дорогостоящего запроса?

Если вы делаете правильное вычисление большого круга, основанное на принятие синуса() и косинус() опорной точки и других точек данных, то весьма существенная оптимизация может быть сделана на самом деле хранить этот грех/созом значений в базе данных в дополнение к значениям lat/long.

В качестве альтернативы просто используйте свою базу данных, чтобы извлечь прямоугольник диапазонов lat/long, которые соответствуют, и только потом отфильтровывать те, которые находятся за пределами истинного кругового радиуса.

Но помните, что одна градус долготы - это несколько более короткое расстояние в высоких широтах, чем на экваторе. Однако должно быть легко определить правильное соотношение сторон для этого прямоугольника. У вас также были бы ошибки, если вам нужно было рассмотреть области, очень близкие к полюсам, поскольку выбор прямоугольника не справился бы с кругом, который перекрывал бы полюс.

Ответ 6

Этот UDF (SQL Server) предоставит вам расстояние между двумя точками 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

И, очевидно, вы можете использовать это в отдельном запросе, например:

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