Получите многоугольники близко к лату, длинные в MySQL

Question

Кто-нибудь знает способ извлечь все полигоны в БД MySQL в пределах заданного расстояния от точки? Фактическое расстояние не так важно, поскольку оно рассчитывается для каждого найденного многоугольника позже, но было бы огромной оптимизацией просто выполнить этот расчет для многоугольников, которые "близки".

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

Какие-либо предложения?

Answer 1

Медленная версия (без пространственных индексов):

SELECT  *
FROM    mytable
WHERE   MBRIntersects(mypolygon, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance))

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

Затем создайте SPATIAL INDEX на поле, которое содержит координаты вершин и просто выполните этот запрос:

SELECT  DISTINCT polygon_id
FROM    vertices
WHERE   MBRContains(vertex, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance))

Все будет намного проще, если вы храните UTM координаты в вашей базе данных, а не широта и долгота.

Answer 2

Я не думаю, что есть один ответ на это. Обычно это вопрос о том, как организовать ваши данные так, чтобы они использовали пространственную локализацию, присущую вашей проблеме.

Первой идеей, которая приходит мне в голову, будет использование сетки, назначение каждой точки квадрату и проверка выбора квадрата, в котором находится точка, и окружающих ее точек. Если мы говорим о бесконечных сетках, то используем хеш-значение квадрата, это даст вам больше очков, чем нужно (если у вас есть коллизии), но все равно уменьшит сумму на кучу. Конечно, это не сразу применимо к полигонам, это просто мозговой штурм. Возможный подход, который может привести к слишком большому количеству коллизий, будет состоять в том, чтобы ИЛИ все хэшированные значения вместе и выбрать все записи, в которых хэши AND с этим значением отличны от нуля (не уверен, возможно ли это в MySQL), возможно, вы захотите использовать большое количество бит, хотя.

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

Answer 3

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