Как мне эффективно искать все ориентиры в пределах определенного ориентира?

14

Я пытаюсь начать с гео-поискового проекта, который найдет все ориентиры в 10 км / миль (не важно для этой истории) конкретной достопримечательности.

Например, допустим, у меня есть база данных с 1 000 000 ориентиров. Чтобы найти все ориентиры в радиусе 10 миль от ориентира с определенными координатами, мне нужно будет рассчитать расстояние между ориентиром из моего поиска и 1 000 000 ориентиров.

Есть ли лучший способ сделать это?

В качестве альтернативы я подумал о том, чтобы классифицировать достопримечательности, такие как страна, регион, город, район, бизнес, исторический и т. Д. Таким образом, чтобы бизнес мог быть частью района или города. Город - это часть региона, страны и т. Д. Это может сузить список вычислений, но все равно выглядит много работы, чтобы поиск был быстрым и точным.

Может ли помочь API Карт Google?

Дарио Гранич
источник
5
Вы, вероятно, могли бы устранить многие из них, просто выполнив быстрый расчет манхэттенского расстояния, а затем выполнив второй фильтр, чтобы исключить ориентиры, которые находятся в пределах 10-километрового квадрата, но находятся за пределами 10-километрового радиуса.
Нил
3
Какие технологии баз данных вы используете? Ответ не зависит от базы данных.
jpmc26
1
@Neil В качестве второго прохода вы можете включить любой ориентир, где x и y находятся в 7 км от начала координат без вычисления фактического расстояния.
JimmyJames

Ответы:

10

Начиная с SQL Server 2008, существует тип данных географии, который хранит местоположения (пары широта / долгота) и облегчает написание запросов, связанных с местоположением.

Существует существующий ответ StackOverflow, в котором это подробно рассматривается.

Основной запрос для поиска ближайших 7 пунктов :

USE AdventureWorks2012  
GO  
DECLARE @g geography = 'POINT(-121.626 47.8315)';  
SELECT TOP(7) SpatialLocation.ToString(), City FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);  

Основной запрос, чтобы найти все в пределах 100 м (второй ответ на вопрос)

-- Get the center point
DECLARE @g geography
SELECT @g = geo FROM yourTable WHERE PointId = something

-- Get the results, radius 100m
SELECT * FROM yourTable WHERE @g.STDistance(geo) <= 100
Flater
источник
11
@KonradRudolph: Как и в случае любого столбца SQL, который используется для запросов к таблице с большим количеством строк. Вы правы, но этот комментарий будет применяться практически к любому запросу SQL, который публикуется как ответ.
Флейтер
2
Где вы прочитали «MS SQL Server» в вопросе?
Док Браун
3
@Flater Я согласен, что это обычно очевидно и избыточно, но формулировка OP, кажется, предполагает, что они не знают о таких механизмах.
Конрад Рудольф
2
@ jpmc26: Вы ошеломлены тем, что я указал верный вариант и не включили какой-либо другой вариант? Какая? Если вы считаете целесообразным добавить PostGIS, добавьте ответ самостоятельно (что вы и сделали) и не прибегайте к критике других людей за то, что они не имеют той же идеи, что и вы.
Флатер
3
Ваш ответ кажется мне в основном просто продаж MS SQL. Ваши комментарии предполагают, что они переключают базы данных на что-то, что стоило бы десятки тысяч долларов, фактически не спрашивая о том, что из-за их ситуации это только выглядит более. Он даже не описывает, как OP может фактически реализовать свой запрос или обсудить тот факт, что использование и обеспечение пространственного индекса не так просто в MS SQL, как в других БД. Также не обсуждается ни одна из основных концепций. Это плохой ответ, независимо от того, является ли он «действительным». Вот почему это беспокоит меня.
jpmc26
29

Использовать базу данных с поддержкой запросов ГИС (географических информационных систем) . Большинство баз данных поддерживают это напрямую или имеют расширения, но детали будут зависеть от базы данных (в своем ответе Флэтер показывает синтаксис для SQL-сервера).

Если вам нужно реализовать такие запросы в вашем приложении, вы можете реализовать структуру данных, которая допускает пространственные запросы, например, дерево kd . Это похоже на бинарное дерево поиска, за исключением того, что каждый уровень дерева разделен на разные координаты измерения. Это позволяет ограничить поиск меньшим набором возможных кандидатов. По сути, вы преобразуете свой поисковый запрос «радиус 10 км» в границы для каждого измерения координат и сжимаете границы по мере повторения в дереве.

Амон
источник
5
Также есть обмен ГИС-стеками
BlueRaja - Дэнни Пфлюгофт
8
PostGIS - лучший бесплатный вариант. Он поддерживает гораздо больше, чем базовые типы и функции ГИС SQL Server. Но это основной функционал.
jpmc26
@amon Я нахожу комментарий jpmc26 хорошим дополнением, и не настолько, чтобы критиковать твой пример. «Если вы хотите начать с нуля, вам не нужно платить за лицензированную БД - эта бесплатная программа с открытым исходным кодом также отлично справится с задачей».
марта 18
11

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

То, на что вы хотите обратить внимание, это запросы «на расстоянии» (запросы на геометрию на определенном расстоянии от некоторой другой геометрии). Это очень стандартная и очень решаемая проблема, которая возможна во всех вышеупомянутых базах данных (и встроена в несколько):

  • PostGIS: ST_DWithin
  • SQL Server: STDistance(непонятно, поддерживается ли использование индекса для версии 3D-географии этой функции)
  • Oracle: SDO_WITHIN_DISTANCE(Это явно не говорит о том, что это вызовет использование индекса. Я бы дважды проверил план запроса. Возможно, вам придется применить a, SDO_FILTERчтобы заставить его использовать индекс.)
  • MySQL: все еще выясняю это.

Обходной путь для запуска использования индекса

В худшем случае, когда у вас возникнут проблемы с тем, чтобы система использовала пространственный индекс с этими запросами, вы можете добавить дополнительный фильтр. Вы бы создали квадратную ограничивающую рамку со сторонами длины 2 * (расстояние поиска), центрированными в вашей точке поиска, и сравнили ограничивающие прямоугольники геометрии таблицы с этим перед проверкой фактического расстояния. Это то, что PostGIS ST_DWithinвыше делает внутренне в любом случае.


Расстояние в ГИС

В то время как пространственные индексы являются фантастическим и абсолютно правильным решением вашей проблемы, расчет расстояния может оказаться логически сложным. В частности, вам нужно беспокоиться о том, в какой проекции (в основном все параметры системы координат) хранятся ваши данные. Большинство 2D проекций (кроме угловых систем координат, таких как различные широты / долготы) значительно искажают длину. Например, проекция Web Mercator (используемая Google, Bing и всеми другими крупными поставщиками базовых карт) расширяет области и расстояния по мере удаления от экватора . Я могу ошибаться, так как я не получил официального образования в области ГИС, но лучшее, что я видел для 2D-проекций, это некоторые конкретные, которые обещают правильные расстояния отединая, постоянная точка во всем мире. (Нет, непрактично использовать разные проекции для каждого запроса; это сделало бы ваши индексы бесполезными.)

Суть в том, что вам нужно убедиться, что ваша математика точна. Самым простым способом сделать это с точки зрения разработки является использование угловых проекций (их часто называют «географическими») и функций, которые поддерживают выполнение математических операций с использованием сфероидальной модели, но эти вычисления немного дороже, чем в 2D-аналогах. и некоторые БД могут не поддерживать их индексацию. Если вы можете получить приемлемую производительность, используя их, тем не менее, это, вероятно, путь. Другим распространенным вариантом являются региональные проекции (например, зоны UTM), в которых расстояния и площади достаточно близки к корректным, если ваши данные ограничены определенной частью мира. Что лучше для вашего приложения, будет зависеть от ваших конкретных требований,

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

jpmc26
источник
3

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

Однако, если бы мне пришлось делать это в базе данных без конкретной поддержки, я бы начал с запроса квадрата, который окружает контур, например (y> (y1 - rad)) AND (y <(y1 + rad)) AND (x> ( х1 - рад)) И (х <(х1 + рад)). Предполагая, что ваши очки имеют примерно равномерное распределение, запрос на квадрат даст вам ваши истинные совпадения плюс около 30% дополнительных ложных совпадений. Затем вы можете удалить ложные совпадения.

Питер Грин
источник
Но без соответствующего пространственного индекса такой запрос будет в худшем случае сканировать всю базу данных, в лучшем случае все элементы в данном диапазоне широты или долготы в зависимости от вашего индекса, то есть «полосу», а не квадрат. Если вы не хотите снижать производительность, используйте базу данных, которая поддерживает пространственные индексы!
Jcaron
@jcaron Я считаю, что этот запрос можно оптимизировать с помощью обычного индекса B-дерева на xи y. (Возможно, в сочетании, возможно, отдельно. Я бы немного
рассказал,
@ jpmc26 Нет, не может. Продумайте это, вы увидите.
августа
@jcaron Может быть, было бы лучше, если бы вы не задумались о чем-то, что явно не так просто. B-деревья могут быть использованы для BETWEENзапросов. Я не понимаю, почему в худшем случае вы не можете иметь 2 индекса, а затем отфильтрованные результаты по каждому индексу объединяются. (Это то, что СУБД делают внутренне, когда считают целесообразным использование нескольких индексов.) Если комбинированный индекс работает, он должен полностью отфильтровать одно измерение на первом уровне, а затем сравнительно быстро сузить на втором уровне.
jpmc26
2
@jcaron на самом деле вы можете использовать индекс для чего-то подобного, y between -68 and -69 and x between 10 and 11но, конечно, пространственный индекс лучше
справится с