Как определить, лежит ли точка внутри произвольного многоугольника (ray casting)?
Дан простой (возможно невыпуклый) многоугольник и точка. Нужно понять, внутри она, снаружи или на границе. Знаю про «метод луча» — пускаем луч и считаем пересечения, но всё время путаюсь с попаданием луча точно в вершину. Как реализовать надёжно?
2 ответа
Ray casting: пускаем горизонтальный луч из точки вправо и считаем, сколько рёбер он пересекает. Нечётное число — внутри, чётное — снаружи. Чтобы обойти проблему попадания луча точно в вершину, используют асимметричное правило «полуинтервала» по y:
// true = внутри; границу обработай отдельно при необходимости
bool pointInPoly(const vector<P>& poly, const P& q) {
int n = poly.size();
bool inside = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
const P& a = poly[i];
const P& b = poly[j];
// ребро пересекает горизонтальную прямую y = q.y?
if ((a.y > q.y) != (b.y > q.y)) {
// x пересечения ребра с этой прямой, сравниваем с q.x
double xCross = (double)(b.x - a.x) * (q.y - a.y) / (b.y - a.y) + a.x;
if (q.x < xCross) inside = !inside;
}
}
return inside;
}
Хитрость в (a.y > q.y) != (b.y > q.y): условие «строго больше» считает каждую вершину принадлежащей только одному из двух смежных рёбер, поэтому луч, проходящий через вершину, не считается дважды. Сложность O(n) на запрос, память O(1).
Два уточнения. Первое: код выше использует double для xCross. Чтобы остаться в целых, замени деление на сравнение с умножением «крест-накрест» — аккуратно следя за знаком (b.y - a.y). На олимпиаде с целыми координатами это убирает риск epsilon.
Второе: ray casting не отвечает явно про границу — точка на ребре может попасть в любую сторону. Если нужно отличать «на границе», сначала отдельным проходом проверь, лежит ли q на каком-либо ребре (orient(a,b,q)==0 && onSeg(a,b,q)), и только потом запускай основной алгоритм.
Альтернатива — метод winding number (суммирование знаковых углов / пересечений с учётом направления): он корректно работает и для самопересекающихся многоугольников, где чётность луча может обмануть. Для простых многоугольников оба метода эквивалентны, ray casting проще.