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

Идея

Многоугольник будет выпуклым, если при его обходе в каждых трех последовательных вершинах поворот всегда происходит в одну и ту же сторону

Доказательство

Нам нужно, чтобы все углы были < 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