Точка внутри многоугольника

Задача: дан многоугольник и точка, нужно понять — внутри, снаружи или на границе.

Сначала граница

Границу проверяют отдельно и до всего остального: пройти по всем сторонам и спросить, лежит ли точка на отрезке. Это $O(n)$ и целиком в целых числах.

Так делают не для удобства: почти все алгоритмы «внутри или снаружи» на границе ведут себя непредсказуемо, и разбирать её внутри общего кода дороже, чем отдельным проходом.

Луч из точки

Пустим из точки луч (скажем, вправо) и посчитаем, сколько раз он пересекает границу. Нечётное число — внутри, чётное — снаружи.

Тонкость одна, зато неприятная: если луч попадает точно в вершину, пересечение считается дважды или не считается вовсе. Лечится так — сторона учитывается, только если её концы лежат по разные стороны от горизонтали точки, причём один конец строго выше, другой не выше:

bool inside = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
    if ((p[i].y > q.y) != (p[j].y > q.y)) {
        long double x = p[i].x + (long double)(q.y - p[i].y) * (p[j].x - p[i].x) / (p[j].y - p[i].y);
        if (x > q.x) inside = !inside;
    }
}

Несимметричное сравнение > и <= в условии — это и есть решение проблемы вершин: каждая вершина засчитывается ровно один раз.

Выпуклый случай

Если многоугольник выпуклый и вершины даны по порядку, есть способ за $O(\log n)$ на запрос.

Возьмём вершину $p_0$ как центр. Все остальные вершины видны из неё под углами, идущими монотонно. Двоичным поиском найдём сектор, в который попадает точка, — и останется одна проверка «с какой стороны от стороны $p_i p_{i+1}$»:

if (cross(p[1] - p[0], q - p[0]) < 0) return false;        // левее первого сектора
if (cross(p[n-1] - p[0], q - p[0]) > 0) return false;      // правее последнего
int i = верхняя граница двоичным поиском по cross(p[i] - p[0], q - p[0]);
return cross(p[i+1] - p[i], q - p[i]) >= 0;

Весь поиск — в целых числах, деления нет. Это важно: подход с лучом требует вещественного пересечения, а этот — нет.

Что выбрать

условие	подход	стоимость запроса
один запрос, любой многоугольник	луч	$O(n)$
много запросов, выпуклый	двоичный поиск	$O(\log n)$
много запросов, невыпуклый	заметающая прямая офлайн	$O((n + q)\log n)$

Смежное

• Точка на прямой, луче и отрезке;
• Площадь многоугольника.