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

Question

Я работаю с большим набором точек, представленных парами широта / долгота (точки не обязательно уникальны, в наборе может быть несколько точек, которые находятся в одном месте). Точки хранятся в базе данных.

Что мне нужно сделать, так это найти способ эффективно выполнить поиск, чтобы получить количество точек, которые находятся в пределах данного радиуса (скажем, 25 миль) от произвольной точки. Счет не должен быть точным на 100% - что более важно, он должен быть быстрым и достаточно близким к правильному счету. Это можно сделать с помощью SQL, используя запрос с некоторой тригонометрией в предложении WHERE для фильтрации точек по их расстоянию до контрольной точки. К сожалению, этот запрос очень и очень дорогой, и кэширование вряд ли окажет большую помощь, поскольку местоположения будут очень распространены.

В конечном счете, я стремлюсь создать некую структуру в памяти, которая сможет эффективно справляться с такого рода операциями - компенсируя некоторую точность и живучесть данных (возможно, перестраивая их только один раз в день) в возвращайся за скоростью. Я проводил некоторые исследования kd-деревьев, но пока не ясно, насколько хорошо это можно применить к данным широты / долготы (в отличие от данных x, y в плоскости 2d).

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

Answer 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);
}

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

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

Часть in DB очень быстрая, а часть in-memory работает на меньшем наборе, чтобы сделать ее сверхточной.

Answer 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 и т. Д.

Answer 3

Используйте какое-то дерево поиска для пространственных данных, например, четырехугольное дерево . Другие структуры данных упоминаются в разделе «См. Также».

Answer 4

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

Answer 5

Этот UDF (SQL Server) поможет вам получить расстояние между двумя точками широты и долготы:

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

Answer 6

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

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

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

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