Эффективное хранение и запрос GPS-координат

Question

Я хочу создать большую базу данных GPS-координат, которую можно запросить, сказав «Вернуть все координаты, которые находятся в пределах« n »метров от [этой координаты]».

Мне нужно, чтобы он был настолько эффективным, насколько это возможно, чтобы циклически проходить по всем координатам в базе данных и вычислять, находится ли координата в пределах 'n' метров, было бы нежелательным решением.

Есть ли более простое решение?

Спасибо

Answer 1

Обычно я делаю такой запрос, используя широту / долготу. Используя сферическую геометрию, вы можете поместить ограничивающий прямоугольник вокруг определенной точки. Например, скажем, у вас есть точка (X, Y), в которой вы хотите, чтобы все координаты были в пределах 1 мили (преобразование в метры я оставлю в качестве упражнения для читателя). Вы можете определить ограничивающий прямоугольник (X-1, Y-1), (X + 1, Y + 1). Затем вы запрашиваете свою базу данных точек, используя оператор BETWEEN (ВЫБЕРИТЕ foo FROM bar, ГДЕ LAT МЕЖДУ X-1 И X + 1 И ДЛИННЫМ МЕЖДУ Y-1 И Y + 1). Затем вы выполняете расчет расстояния детали, чтобы «закруглить углы» вашей ограничительной рамки.

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

Google "Great Circle Distance" для расчетов.

РЕДАКТИРОВАТЬ: Существует 0,167469 градусов долготы на милю (на самом деле она колеблется от 0,167469 до 0,014564) и 0,014483 градусов широты на милю. Итак, ваша ограничительная рамка (lat - (miles * 0.014483), lon - (miles * 0.167469)), (lat + (miles * 0.014483), lon + (miles * 0.167469))

Answer 2

В SQL Server 2008 существует поддержка для хранения пространственных данных . Я никогда не работал с ним сам, но я знаю, что вы можете создавать запросы того типа, который вам нужен.

Answer 3

Если вы хотите избежать расширения ГИС, я адаптировал функции из этого поста к postgres sql:

create or replace function change_in_lat(miles numeric)
returns double precision as $$
with v as (select
    3960.0 as earth_radius,
    180 / pi() as radians_to_degrees
) select ( miles / earth_radius ) * radians_to_degrees from v;
$$ language sql
returns null on null input;

create or replace function change_in_long(lat numeric, miles numeric)
returns double precision as $$
with v as (select
    3960.0 as earth_radius,
    pi() / 180 as degrees_to_radians,
    180 / pi() as radians_to_degrees
) select (
    miles / (earth_radius * cos(lat * degrees_to_radians))
    ) * radians_to_degrees from v;
$$ language sql
returns null on null input;

используя те из них, вы можете выполнить несколько запросов на окружающие квадраты:

--find all "a"s within 25 miles of any "b"
select * from a join b on (
a.gpslat between
    b.gpslat - change_in_lat(25) and b.gpslat + change_in_lat(25)
and a.gpslong between
    b.gpslong - change_in_long(b.gpslat::numeric, 25)
    and b.gpslong + change_in_long(b.gpslat::numeric, 25)
);

если бы вы использовали его достаточно часто, я уверен, что преобразование операторов в одну функцию будет простым. Хотя я никогда не делал никаких реальных запросов в пределах радиуса.

Для чего-то более сложного вы, вероятно, захотите расширение ГИС, как сказали другие ответы. PostGIS хорош, но я обнаружил, что многие специфические для ГИС функции могут быть трудно получить правильные, и если вы не используете индексы ограничивающего прямоугольника, ваши пространственные запросы могут занять день, если ваш набор данных достаточно большой. Но компромисс между сложностью определенно стоит того, чтобы все такие модные вещи, как вывод ваших данных в формате геоджон и т. Д.

Answer 4

Вслед за Erich - если у вас есть выбор, используйте PostGIS (postgresql), он бесплатный и с открытым исходным кодом, очень ли быстро описываются запросы, которые вы описываете, работает почти на всех платформах, и я говорил, что это бесплатно?

Answer 5

ГИС-базы данных (MS PostgreSQL и т. Д.) Фактически реализуют некоторую структуру данных для двух- или трехмерного поиска областей ( пространственные индексы ). Простейшей структурой является индекс сетки, затем различные поисковые деревья (kd-дерево, quad-дерево) с R-деревом в качестве наиболее часто используемого (обобщенное B-дерево для большего числа измерений). Эти методы кажутся адекватными.

Базовый индекс сетки (разбиение пространства на ячейки сетки и поиск только в соседних ячейках) может быть легко реализован и может сократить время поиска до логарифмического. Деревья поиска немного сложнее реализовать, но есть много реализаций с открытым исходным кодом для многих языков программирования. Однако в большинстве случаев индексирование сетки достаточно эффективно.

Answer 6

Если у вас есть выбор БД, я бы рекомендовал то же самое, что и rwwilden, и использовать SQL 2008 с его возможностями пространственных данных. Если вы не можете использовать это решение или решение, включающее пространственные запросы, вы можете взглянуть на собственную статью Microsoft по Иерархическая треугольная сетка и реализовать ее. SDK для MSSQL '05 также поставляется с готовым решением для HTM, поэтому вы можете просто взять его и преобразовать в любую платформу, на которую вы рассчитываете.

EDIT:

Вот более подробный документ , объясняющий HTM и реализацию. Вы, конечно, можете конвертировать в свою базу данных по вашему выбору. Вы можете найти исходный код полной реализации HTM в SDK для 2005 года.

Answer 7

Многие системы баз данных имеют функцию для работы с геопространственными данными.

Вот сравнение геопространственных функций между SQL Server 2008, PosGIS и MySQL. http://www.bostongis.com/PrinterFriendly.aspx?content_name=sqlserver2008_postgis_mysql_compare