Точка в многоугольнике
Классический геометрический тест: лежит ли заданная точка внутри многоугольника или снаружи.
Обычное решение — бросание луча: из точки пускают луч в любом направлении и считают, сколько рёбер многоугольника он пересёк; нечётное число означает «внутри», чётное — «снаружи». Альтернатива — число витков (winding number): оно суммирует, сколько раз многоугольник обходит точку, и справляется даже с самопересекающимися фигурами. Оба алгоритма линейны по числу рёбер.
Тест лежит в основе определения попаданий в 2D-играх, кликов по кнопкам неправильной формы, геозон и ГИС. Для выпуклых многоугольников хватает более простой проверки знака относительно каждого ребра; в тяжёлых случаях многоугольник предобрабатывают или индексируют пространственно.