16. Внутреннее и внешнее отсечение. Определение выпуклости многоугольника; определение нормали; разбиение невыпуклых многоугольников. Триангуляция многоугольников.

Внутреннее отсечение – определяем части отрезка внутри отсекателя и вычерчиваем.

Внешнее отсечение – определяем части вне отсекателя и вычерчиваем.

Определение выпуклости

• Вычислить векторные произведения всех пар смежных сторон.

1. Если все = 0 – многоугольник вырожден в отрезок.
2. Все разных знаков – многоугольник невыпуклый.
3. Все ≥0 – выпуклый, нормали ориентированы влево от рёбер.
4. Все ≤0 – выпуклый, нормали вправо.

• Разбиение

1. Перенести в (0, 0) i-ую вершину
2. Повернуть вокруг (0, 0), чтобы i+1-ая вершина оказалось на +части оси x
3. Вычислить знаки ординат всех i+2-ых вершин
   1. =0 – вырожден в отрезок
   2. одинаковы – выпуклый относительно этого ребра
   3. разные – невыпуклый, разрезаем на 2 части вдоль оси. далее работаем с двумя многоугольниками

Определение внутренней нормали