Поиск в базе данных данных с привязкой к координатам для произвольной полигональной области

Question

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

Каков был бы наилучший способ достичь этого?

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

Answer 1

Используйте пространственные расширения, большинство баз данных имеют это. В MySql вы можете использовать их только с таблицами MyISAM, которые не являются транзакционными.

http://dev.mysql.com/doc /refman/5.0/en/spatial-extensions.html

Answer 2

Один из способов быстро сократить количество рассматриваемых точек - вычислить ограничивающий прямоугольник для многоугольника (т. е. просто min-x, min-y, max-x, max-y точек в многоугольнике). , а затем выберите точки внутри ограничивающего прямоугольника (т. е. где x находится между min-x и max-x и то же самое для y).

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

Answer 3

Старый хак:

Подсчитайте, сколько раз линия соединялась <point far away> Для <point in question> пересекает любой из ограничивающих сегментов многоугольника.

• Четные числа означают, что точка находится за пределами многоугольника
• Нечетные числа означают, что он находится внутри многоугольника