Проверка на выпуклость

Материал из Algocode wiki
Версия от 14: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