Если полигон выпуклый, то проверку попадания внутрь можно реализовать проверяя попадание точки между двух ребер (по горизонтали),
причем ребра (правые и левые по отдельности) точно сортируются по вертикали → эффективный поиск ребер, с какими нужно сравнивать (например двоичное деление).
Данному алгоритму глубоко наплевать, что полигон будет невыпуклый, если этого не заметно на горизонтальных секущих:
Так “песочные часы” или “банан” (если они расположены вертикально) хоть и не являются выпуклыми - все равно подходят под алгоритм.
Или, сказав по другому, можно произвольно (только, чтобы в результате не пересекались между собой ребра), изменять координаты X любых ребер в (ранее) выпуклом полигоне и полученные при этом многоугольника нас устроят.
Как наверное все уже догадались, не подходящие для нас регионы можно просто разрезать на несколько “полувыпуклых” и проверять на попадание в один из них (если резать без добавления новых точек - т.е. под углом - то может потребоваться проверять до получившихся двух полигонов - иначе один).
Правда тут еще нужно рассматривать варианты попадания на ребра (в том числе горизонтальные и как отдельный вариант, границу разрезанных сложных полигонов), если этот случай имеет отличия от попадания внутрь.
Верно, это довольно быстрая реализация алгоритма “луча”.
Кстати, там описан и уход от деления.
Приведенный мной алгоритм для (полу)выпуклого многоугольника для случая проверки одной точки проигрывает, так как требует довольно объемной подготовки, но ее можно сделать один раз для многоугольника независимо от числа точек (да еще и, теоретически, запоминать в БД). А если многоугольник с большим числом вершин (десятки и сотни) и мы с ним сравниваем сотни и тысячи точек - то ускорение получается на порядок, а то и порядки. Если провести небольшую оценку - то можно определить число граней до которого применять “луч”, а после уже этот.
проверяем первую точку пути,
если точка в полигоне
то путь попадает в гранцу
иначе
проверяем последнюю точку
если точка в полигоне то путь попадает в границу
иначе - путь не попадает в границу
Такая мысль: надо еще над качественными оценками подумать (приблизительные быстрые вычисления) – например, берём вышеупомянутый ббокс (это же и есть тот самый прямоугольник, который описывает наш полигон? (upd: в который вписан наш полигон. Так менее двусмысленно) ), если путь в него не влез (находится за пределами полигона), значит не влезет и в наш точный полигон. Тут всего четыре точки по углам, проверка быстрее. А если влез, тогда уж гонять по “долгой” схеме точного определения по влезанию в полигон из сотен точек.
По крайней мере, часть вычислений можно откинуть, для тех путей кои не лезут в ббокс.
Но если их по вашей прикидке будет меньше, чем влазящих, тогда такая проверка только замедлит процесс, это понятно.
у меня на конвертацию всей России уходит минут 30, правда, сначала она режется на куски.
причём принадлежность точки полигону проверяется в двух местах: при привязке улиц к городам и при привязке островов к озёрам. второе тормозит значительно сильнее
использую функции из перловых библиотек Math-Polygon и Math-Geometry-Planar
Я строю ббокс по максимальным и минимальным координатам полигона ± чуть-чуть и точки из базы отбираются только те, что попадают в ббокс, то есть проверять лучом не надо, при квадратном ббоксе все проверяется просто сравнением координат - больше/меньше.
Имхо тут можно было бы класть полигон на сетку как описано здесь, затем гонять по нему точки. +я бы неприменно отсортировал сами точки по горизонтали/вертикали, чтобы на обработку сразу шли точки из “полосы” bbox’а.
Edit: от оптимизаций типа замены деления на умножение много не выиграешь. Нужно снижать сложность алгоритма.
Еще стоит добавить проверку на промежуточную точку, если оба конца попали на границу.
И считать, что трассу проходящую через город нужно порезать на границах (все равно там КЛАДР и принадлежность к н/п меняется).
Кстати, а почему на некоторых улицах левый КЛАДР. Например на Ленинградке в Химках - “77…”?
Есть у меня сильное подозрение, что Ленинградка в Химках это Москва и КЛАДР правильный… Ща проверю.
UPD. Глупость написал. Есть Химкинский кусок. Граница прерывается. А вот почему бот его подтянул - не знаю. Надо попробовать порезать его по границе Мск/область и посмотреть .что будет. Так ,как оно сейчас нарисовано, не должно было попасть вообще никуда.
Нарезка на 14 кусков должна дать выигрыш по сравнению с монолитным на порядок (каждый кусок до 14^2 раз ну и всего 14), а если учесть необходимость поместить все это в память (своп) - то и того больше.
Но зато возникают “граничные эффекты” - трудоемкость обрезки полувытянутых отношений, невозможность определить принадлежность к стране (если никакой кусок границы не попал - да и там понять с какой стороны какая может быть невозможно).
Еще мысль пришла, можно ведь ббокс брать еще и внутренний, вписаный в полигон. В той же Москве отсекается приличный кусок. Вот только как вычислять его координаты, чтобы и захватывал побольше и не вылез за границы. Буду рад идеям…
тогда это не вписанный ббокс. Его проще руками сделать, типа вырожденный случай.
я так понимаю, ты хочешь и обратного быстрого отсечения – кто заведомо принадлежит полигону…
Скажем так:
if. (полигон называется Москва/Питер?)
{обрабатываем по спец.ветке со своим (полу-)вписанным ббоксом:
попали, решение готово, вываливаемся из поиска; break}
else. {если не попали – в общую ветку}
В общей ветке: накрываем улицу _о_писанным ббоксом
if (не попал?)
{на проверку след. полигона, goto Скажем так}
else (попал)
{на подробный долгий алгоритм}
Именно, хочется быстро отсечения. Ибо именно в городах много путей, тоесть большее количество точек для проверки. Отсекая кусок мы сразу выигрываем в скорости. Да, я могу задать внутренний ббокс для большого города руками. но для всех - замучаюсь. А ведь надо еще проверять, не сместилась ли граница с прошлого прогона…
Проще тогда рубить на сетку, определить внутренние квадраты, наружные квадраты и квадраты, через которые проходит граница полигона.
все, что в наружных - сразу выбрасываем
все, что во внутренних - сразу принимаем
все, что в квадратах с границей - проверяем по полной
А квадраты ты как проверять будешь? Это с дорогами мы можем считать, что если начало и конец в полигоне, то она вся в полигоне. А квадрат по четырем точкам не проверишь… Проверять несколько точек по каждой стороне с определенным шагом?
