Как проверить, что многоугольник выпуклый?
Дан многоугольник списком вершин по порядку. Хочу проверить, выпуклый ли он, чтобы потом применять быстрые алгоритмы (точка внутри за O(log n)). Как это сделать корректно, учитывая и обход по часовой, и против, и коллинеарные вершины?
2 ответа
Многоугольник выпуклый тогда и только тогда, когда все повороты на его вершинах имеют один знак (либо все левые, либо все правые). Проверяем знак cross для каждой тройки соседних вершин и убеждаемся, что он не меняется:
bool isConvex(const vector<P>& p) {
int n = p.size();
if (n < 3) return false;
int sign = 0;
for (int i = 0; i < n; i++) {
P a = p[i], b = p[(i+1)%n], c = p[(i+2)%n];
long long cr = (b - a).cross(c - b);
if (cr != 0) {
int s = cr > 0 ? 1 : -1;
if (sign == 0) sign = s;
else if (s != sign) return false; // знак сменился — невыпуклый
}
}
return true;
}
Идея: у выпуклого многоугольника при обходе ты всё время поворачиваешь в одну сторону. Если хоть один поворот в другую сторону — есть «вмятина», многоугольник невыпуклый. Нулевые cross (коллинеарные вершины, развёрнутый угол) пропускаем — они допустимы. Сложность O(n), целые числа, без epsilon.
Тонкости. Во-первых, мы не фиксируем заранее, левые повороты или правые — берём знак первого ненулевого поворота и требуем постоянства. Так функция работает и для CCW, и для CW обхода.
Во-вторых, если задача запрещает три точки на одной прямой (строгая выпуклость), то нулевой cross нужно считать нарушением — тогда замени пропуск на return false при cr == 0. Уточняй по условию.
В-третьих, эта проверка предполагает, что многоугольник простой (без самопересечений). У самопересекающегося контура знаки тоже могут быть одинаковыми, но фигура не выпуклая в обычном смысле. Если самопересечения возможны, их надо проверять отдельно. И не забудь про переполнение cross при больших координатах.