Чем winding number отличается от ray casting при проверке точки в многоугольнике?
Видел два подхода к «точка в многоугольнике»: метод луча (чётность пересечений) и winding number (сумма углов). Когда они дают разный ответ и какой выбрать? Особенно интересует случай самопересекающегося многоугольника.
2 ответа
Для простого (несамопересекающегося) многоугольника оба метода дают одинаковый ответ. Различие проявляется на самопересекающихся контурах.
- Ray casting считает чётность пересечений луча с границей. Точка «внутри», если число пересечений нечётно — это правило even-odd (чётно-нечётное).
- Winding number считает, сколько раз контур обходит точку (с учётом направления): суммирует знаковые повороты. Точка «внутри», если winding number ≠ 0.
На фигуре типа «звезда» с самопересечениями центральная область по even-odd может оказаться «снаружи» (чётное число пересечений), а по winding number — «внутри» (контур обходит её дважды). Это два разных определения «внутренности», и какое правильное — диктует задача.
Winding можно считать целочисленно через сумму ориентаций рёбер относительно точки, без углов и atan2. Оба метода — O(n) на запрос.
Практическая целочисленная реализация winding через пересечения луча с учётом знака:
int windingNumber(const vector<P>& poly, const P& q) {
int wn = 0, n = poly.size();
for (int i = 0; i < n; i++) {
P a = poly[i], b = poly[(i+1)%n];
if (a.y <= q.y) {
if (b.y > q.y && orient(a, b, q) > 0) wn++; // вверх, q слева
} else {
if (b.y <= q.y && orient(a, b, q) < 0) wn--; // вниз, q справа
}
}
return wn; // 0 = снаружи (для CCW непустой внутренности)
}
Здесь весь счёт идёт через orient в целых числах — никаких atan2 и углов, которые иначе накопили бы ошибку double. Для олимпиадных простых многоугольников чаще берут ray casting (короче), а winding — когда контур может самопересекаться или важна кратность обхода.