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

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>, пересекает любой из ограничивающих сегментов многоугольника.

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