Вопросы к 16

К: Вот вы еще тут рассматриваете еще один способ, основанный на преобразовании (определение выпуклости и сразу разрезать ...) Какие операции преобразования используются?

С: Поворот и перенос

С:Соответственно мы должны перенести в начало координат нашу текущую рассматриваемую вершину и i + 1 вершину положить на положительное направление оси OX, таким образом если у нас все наши вершины лежат по одну сторону, то у нас будет выпуклый наш многоугольник. В случае вот как я здесь расписывал разбиение невыпуклых многоугольников, то я соответственно, если вдруг i + 2 вершина находится ниже, то я нахожу точку пересечения и отмечаю самую ближнюю.

К: Какую диагональ мы должны найти? (этот вопрос к триангуляции)

С: Которая расположена внутри нашей фигуры. - 1 требование чтобы она пересекала соединяющие ребра. - 2 требование

К: ребра, которые исходят из вершин, которые она соединяет

Метод с помощью поворота и переноса многоугольника - всегда ли этот метод можно применить?

(?????)Нет.Этот алгоритм не дает оптимального разбиения в смысле минимального числа выпуклых компонент. Кроме того, алгоритм не сможет корректно разбить многоугольник, стороны которого пересекаются между собой.

Как выпуклый разбить?

Взять любую вершину и провести из нее отрезки во все остальные вершины. Можно взять любую точку и провести из нее.

А как быть с невыпуклым?

Тут сложнее. Можем разбивать сам многоугольник на треугольники или дополнять его треугольниками до выпуклого. Для начала надо найти такую вершину, чтобы диагональ, соединяющая данную вершину с какой-либо другой вершиной содержалась бы только внутри многоугольника или проходила только через ребра из тех вершин, которые она соединяет. В геометрии доказано, что в качестве такой вершины надо брать невыпуклую вершину.

Требования к диагонали?

1. Расположена внутри нашей фигуры.
2. Чтобы она пересекала соединяющие ребра.