Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Является ли многоугольник выпуклым

Дан многоугольник.
Необходимо проверить, является ли он выпуклым многоугольником.

    Если пройти по всем вершинам выпуклого многоугольника против часой стрелки, то можно заметить, что каждая вершина лежит слева от предыдущей стороны.
    Значит, достаточно просто пройти по всем трём смежным вершинам многоугольника и установить, что знак ориентированной площади треугольника этих трёх вершин всегда одинаков. Если это так, то перед нами выпуклый многоугольник, иначе нет.

Асимптотика O(n).

Листинг C++

bool is_convex (vector < point > p)
{
    int l, i, r;
    int n = p.size();
    bool isccw = ccw (p[n - 1], p[0], p[1]);
    for (i = 1; i < n; ++ i)
    {
        l = (i - 1 + n) % n;
        r = (i + 1) % n;
        if (ccw (p[l], p[i], p[r]) != isccw)
            return false;
    }
    return true;
}


25.06.2007, 18:56