Как определить, по часовой или против часовой стрелки задан многоугольник?
Многие алгоритмы (например, проверка точки внутри выпуклого за O(log n)) требуют, чтобы многоугольник был задан против часовой стрелки. Как проверить ориентацию обхода и при необходимости развернуть его?
2 ответа
Ориентация обхода определяется знаком ориентированной площади (формула шнуровки без abs):
long long area2(const vector<P>& p); // см. формулу Гаусса, без abs
bool isCCW(const vector<P>& p) {
return area2(p) > 0; // против часовой
}
void makeCCW(vector<P>& p) {
if (area2(p) < 0) reverse(p.begin(), p.end());
}
Логика: ориентированная площадь положительна для обхода против часовой стрелки (CCW) и отрицательна для обхода по часовой (CW) — в стандартной системе координат, где y растёт вверх. Если знак не тот, просто разворачиваем список вершин через reverse.
Сложность — O(n) на подсчёт площади, целые числа, без epsilon. Это надёжнее, чем смотреть на знак cross в одной случайной вершине: у невыпуклого многоугольника отдельные вершины могут давать «неправильный» локальный поворот, а интегральная площадь — всегда корректна.
Осторожно с системой координат. В олимпиадах обычно ось Y направлена вверх (математическая), и тогда положительная площадь = CCW. Но если в задаче y растёт вниз (например, координаты пикселей экрана), визуальное «против часовой» инвертируется. Алгоритмически ничего не меняется — важно только быть консистентным: один раз зафиксируй соглашение «положительная area2 = CCW» и держись его во всех функциях (точка в многоугольнике, выпуклая оболочка). Путаница с ориентацией — классический источник зеркально неверных ответов.