Точка в полигоне: метод трассировки луча

Урок реализует один из самых частых пространственных запросов — «находится ли точка внутри полигона» — классическим методом трассировки луча.

Point-in-polygon — проверка принадлежности точки многоугольнику; метод трассировки луча (ray casting) считает, сколько раз луч из точки пересекает границу полигона.

«В каком районе находится этот адрес?», «Попадает ли датчик в зону охраны?», «Этот клик по карте — внутри страны или в море?» — всё это один и тот же вопрос: лежит ли точка внутри полигона. Для выпуклых фигур есть простые приёмы, но реальные районы бывают какими угодно — с заливами, выступами, вмятинами. Метод трассировки луча работает для любых, даже невыпуклых, полигонов.

Идея чётности пересечений

Выпустим из проверяемой точки луч в любую сторону (удобно — горизонтально вправо) и посчитаем, сколько раз он пересечёт границу полигона. Если число пересечений нечётное — точка внутри; если чётное (включая ноль) — снаружи. Интуиция: каждый раз, входя в фигуру, мы пересекаем границу, и выходя — снова; чтобы оказаться внутри, входов должно быть на один больше, чем выходов.

  Точка снаружи: луч пересекает границу 2 раза (чётно)
      *----->  |####|  -->
               2 пересечения

  Точка внутри:  луч пересекает границу 1 раз (нечётно)
      |##*----->|  -->
               1 пересечение

Реализация

Перебираем рёбра полигона (пары соседних вершин). Ребро пересекает горизонтальный луч точки, если оно «перешагивает» её широту по вертикали, и точка пересечения лежит правее проверяемой $x$:

def point_in_polygon(x, y, poly):
    n = len(poly)
    inside = False
    j = n - 1  # предыдущая вершина (замыкаем на последнюю)
    for i in range(n):
        xi, yi = poly[i]
        xj, yj = poly[j]
        # ребро пересекает горизонтальную линию точки?
        crosses = (yi > y) != (yj > y)
        if crosses:
            x_cross = (xj - xi) * (y - yi) / (yj - yi) + xi
            if x < x_cross:
                inside = not inside
        j = i
    return inside

square = [(0, 0), (4, 0), (4, 4), (0, 4)]
print(point_in_polygon(2, 2, square))  # центр
print(point_in_polygon(5, 5, square))  # снаружи

# Невыпуклый полигон в форме буквы L
L_shape = [(0, 0), (4, 0), (4, 2), (2, 2), (2, 4), (0, 4)]
print(point_in_polygon(1, 3, L_shape))  # в ножке L
print(point_in_polygon(3, 3, L_shape))  # в вырезе

Вывод:

True
False
True
False

Точка $(3, 3)$ лежит в «вырезе» буквы L — формально внутри ограничивающего прямоугольника, но снаружи самой фигуры. Метод луча это правильно отлавливает, что отличает его от наивной проверки «между min и max».

Как работает под капотом

Условие (yi > y) != (yj > y) истинно ровно тогда, когда одна вершина ребра выше широты точки, а другая ниже или на уровне — то есть ребро действительно «перешагивает» горизонтальный луч. Строгое сравнение по одной стороне аккуратно обрабатывает вершины, лежащие точно на луче, чтобы не посчитать пересечение дважды. Сложность — $O(n)$ на одну точку при $n$ вершинах. Если точек миллионы, сначала отсекают по bounding box (быстрая проверка прямоугольником), а уже прошедшие — точным лучом. Граничные случаи (точка ровно на ребре) метод трактует неустойчиво — для них в продакшене берут готовый предикат из shapely.

Частые ошибки

Проверять только bounding box. «Между min и max координат» — не то же самое, что внутри полигона (см. вырез L).
Неверно замкнуть полигон. Последнее ребро соединяет последнюю вершину с первой; об этом легко забыть.
Нестрогие сравнения по широте. Использование >= с обеих сторон удваивает счёт на вершинах, лежащих на луче.

Запрос, который вы используете каждый день

Проверка «точка в полигоне» незаметно работает в десятках сервисов вокруг нас. Когда такси определяет, в каком тарифном поясе вы находитесь, — это точка в полигоне. Когда сайт показывает цены в вашей стране по геолокации — точка в полигоне (страны). Когда служба доставки решает, входит ли адрес в зону обслуживания, когда игра определяет, в какой триггер-зоне игрок, когда метеосервис находит ваш район для прогноза — везде один и тот же алгоритм трассировки луча или его родственники. Эта операция настолько фундаментальна, что её аппаратно ускоряют в графических процессорах (там она называется растеризацией) и оптимизируют в каждой ГИС-библиотеке.

Метод луча красив своей универсальностью — он не требует, чтобы фигура была выпуклой, и работает с любыми, самыми изрезанными контурами районов. Но у него есть честные ограничения, о которых важно знать. Граничные случаи — точка ровно на ребре или на вершине — он трактует неустойчиво, и для них в продакшене берут проверенные предикаты shapely. На больших объёмах его всегда предваряют отсевом по bounding box, иначе линейный проход по тысячам вершин каждого из тысяч полигонов убьёт производительность. И для полигонов с дырками (озеро с островом) логику расширяют: точка внутри внешнего кольца, но внутри дырки — снаружи фигуры. Понимание этих нюансов отделяет «работает на примере» от «работает на реальных данных».

Итог

Метод луча: нечётное число пересечений границы — точка внутри.
Работает для любых полигонов, включая невыпуклые (буква L).
Сложность $O(n)$; для масс точек сначала отсекают по bounding box.
Граничные случаи лучше доверять готовому shapely.