| love_bach |
|---|
| не используя гис и т.п. нужен алгоритм |
Если полигоны выпуклые - то легко. Для всех полигонов задается
направление обхода (например по часовой стрелке). Далее решается
уравнение типа "положение точки относительно прямой" для каждого
отрезка из образующих полигон. (Метод 1)
Для вогнутых есть алгоритм четности. Из точки выпускают луч коллинеарно
оси X. И если количество пересечений с гранями полигона четно или нечетно
то принимается решение. Сложность этого метода только в формальных
договоренностях о том как быть если луч проходит через точку и как задать
направление обхода.
Вогнутые полигоны можно представить логической суперпозицией двух выпуклых А и Б.
При этом решать булево выражение типа A и не-Б.
Еще есть метод дробления полигона на набор выпуклых трапеций. Для трапеции
поиск попадания - тривиален. Плюс тут можно делать всякие оптимизации
по скорости. (Метод 3). Для методов 1 и 3 возможны еще оптимизации
по методу BSP деревьев (если ищется скоростное решение).
Плюс для всех-всех методов имеет смысл строить выпуклый BoundingVolume
и делать тривиальные оптимизации.
Из экзотики еще есть метод основанный на интеграле по контуру для
кусочно-линейной функции но я его не помню. Кодил когда-то на Basic как
самый первый метод инженерной графики.