Проверка на выпуклость
Материал из Algocode wiki
Версия от 11:12, 19 декабря 2020; Глеб (обсуждение | вклад) (Новая страница: «==Идея== Многоугольник будет выпуклым, если при его обходе в каждых трех последовательны...»)
Содержание
Идея
Многоугольник будет выпуклым, если при его обходе в каждых трех последовательных вершинах поворот всегда происходит в одну и ту же сторону
Доказательство
Нам нужно, чтобы все углы были < 180 градусов, а из этого следует, что либо для всех трех вершин углы < 180 и мы обходим по часовой стрелке, либо мы идем против часовой стрелки и для всех трех вершин углы > 180.
Алгоритм
Давайте последовательно рассматривать все тройки вершин, для определения поворота угла мы можем использовать векторное произведение.
Код
for (i = 0; i < n; i++) {
if (vect(i, j, k) < 0) {
flag |= 1;
}
else {
flag |= 2;
}
if (flag == 3) {
// не выпуклый
}
}
if (flag != 3) {
//выпуклый
}
}
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin