Всем привет!
Гугл обгуглил, яндекс обяндексил по полной, а толку…
В общем и целом ищу пример, как можно проверить принадлежность гео-точки lat,lon к полигону, что она внутри него. Нужно просто true/false. Но все примеры что я смог найти какие-то не те в плане результатов + они никак не связаны с нашим миром карт…
Желательно полигон произвольной формы. Я думаю у кого-то в закромах такое есть.
Заранее благодарен, за информацию по теме.
MySQL (MariaDB), какие-то вроде бы есть.
Зоны в базе, но по идее могут быть выгружены в память пока клиент с нами работает, точка приходит в скрипт, проверяем…
Для точки внутри контура все векторные произведения векторов из точки на пары последовательных точек контура имеют одинаковый знак. Как-то так, или похоже…
единственная возможная проблема - надо, чтоб на луч не попала ни одна вершина, а то могут быть проблемы. для этого, если работаем с координатами, можно точку из поиска подвинуть чуть-чуть вверх или вниз, на величину в половину точности координат вершин.
to wowik: это верно только для выпуклых многоугольников и частных случаев остальных
А что нужно-то? Алгоритм? Библиотека? Готовое решение?
Алгоритм там постой как гвоздь: строим луч из точки в бесконечность и смотрим сколько отрезков из границы полигона с ним пересекается. Если четное число, то снаружи. Если нечетное, то внутри.
Это годится для пары полигонов. Если их хотя бы десяток - уже лучше использовать базу или специальные индексы в памяти.
Вот функции у MySQL, проверяющие принадлежность: Within(g1,g2)
Ну там даже примеры на C есть, чего ещё надо?
Примеры на JavaScript можно в OpenLayers надыбать.
На Java мы JTS юзаем - вполне удобная библиотека с богатыми возможностями.
Ещё важный вопрос проекций. 2D геометрия более-менее работает только на меркаторе и на небольших расстояниях. При работе с градусами и большими расстояниями надо использовать более сложные алгоритмы.