== Невыпуклый многоугольник ==
Если Очевидно, что если пустить из точки луч, то по чётности числа пересечений с рёбрами многоугольника можно определить, внутри точка лежит на ребре, сразу вернём trueили снаружи.
ОчевидноПустим луч, чтонапример, если пустить из точки лучпо иксу, то по чётности числа пересечений переберём все рёбра и проверим их на пересечение с рёбрами многоугольника можно определить, внутри точка лежит или снаружилучом.
Пустим лучЛуч может попасть в точку, напримерпри этом прохождение через точку учтётся два раза (по разу для каждого отрезка, по иксу к которым принадлежит точка). Иногда это и за <tex>Oесть то, чего нам хочется (nкогда фигура находится выше или ниже луча)</tex> переберём все рёбра и проверим их на пересечение с лучом, но иногда нам хочется учесть только один раз. Для этого для каждого отрезка учитываем только верхнюю точку. Как проверять: сначала проверим, что ордината точки лежит между ординатами концов ребра, затем Все случаи попадания луча в точку показаны ({{AcronymTODO|посмотримt=Картинка с лучом, до ребра или после него начался луч|для альтернативно одарённых: это делается тоже поворотомпопадающим в точку}}) на рисунке.
Луч может попасть в точкуПолучившийся алгоритм: * заведём счётчик пересечений и проинициализируем его нулём (либо просто заведём переменную типа bool, при показывающую чётность числа пересечений)* для каждого ребра <tex>ab</tex> многоугольника:** если точка запроса <tex>q</tex> лежит на этом прохождение через точку учтётся два раза ребре, то сразу возвращаем true** если <tex>a_y=b_y</tex>, пропускаем этот отрезок, он не влияет на чётность числа пересечений** если <tex>q_y=max(по разу для каждого отрезкаa_y, к которым принадлежит точкаb_y). Иногда это </tex> и есть то<tex>q_x < min(a_x, чего нам хочется (когда фигура находится выше или ниже лучаb_x)</tex>, но иногда нам хочется учесть только один раз. Для этого делаем такую штуку: для каждого отрезка учитываем {{Acronym|только верхнюю точку|А увеличим счётчик пересечений** если отрезок горизонтальный<tex>q_y=min(a_y, то забиваем на негоb_y)</tex>, пропустим это ребро** если точка не <tex>q_y</tex> лежит на нём. После недолгих раздумий между <tex>a_y</tex> и <tex>b_y</tex> и разглядываний смежных отрезков станет очевидноповорот точек <tex>a, что на чётность числа пересечений он никак не влияет}}. Дальше {{Acronym|всё очевидно|Кому не очевидноb, тот может порисовать картинки с лучомq</tex> левый, попадающим в точкуто увеличим счётчик пересечений* если число пересечений чётно, и посчитатьвернём false, сколько раз в каком случае учитывается пересечение}}иначе вернём true Время работы алгоритма составляет <tex>O(n)</tex>.
[https://github.com/BorisMinaev/cg/blob/master/include/cg/algo/point_inside_polygon.h Реализация]
[[Категория: Вычислительная геометрия]]
