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

Внутреннее и внешнее отсечение

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

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

Определение выпуклости многоугольника

Для того, чтобы определить, является ли многоугольник выпуклым, его стороны стоит рассматривать как векторы:

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

C_i C_(i+1)*C_(i+1) C_(i+2)≥0

При этом векторы внутренних нормалей в этом случае ориентированы влево относительно направления векторов обхода.

Если все C_i C_(i+1)*C_(i+1) C_(i+2)=0, то многоугольник вырожденный.

Если среди таких произведений есть как положительные, так и отрицательные величины, то многоугольник невыпуклый.

При этом стоит отметить, что в своей реализации я несколько «упростил» условия выпуклости данного способа, так как мне не требовалось дополнительно опознавать направление внутренних нормалей (определение нормалей было вынесено в другой модуль), поэтому анализируется факт того, что все произведения не изменяют своего знака, либо являются нулевыми значениями (но не все).

Определение нормали

Из курса аналитической геометрии нам известно, что равенство нулю скалярного произведения некоторых двух векторов означает, что эти векторы перпендикулярны. Данный факт мы и будем использовать для того, чтобы определить нормаль к i-ой стороне отсекателя.

Пусть A- некоторый вектор, нормаль к которому мы ищем, а вектор N- искомая нормаль. Запишем формулу для вычисления скалярного произведения двух этих векторов:

A_x N_x+A_y N_y=0

Так как нам требуется найти направление нормали, следовательно можем задать одну из проекций нормали = 1 (в моём случае, это N_x):

A_x+A_y N_y=0

При этом не стоит пренебрегать перед вычислением выражения сверху проверкой на равенство A_y нулю, так как в таком случае требуется задать вектор {0, 1} как вектор нормали заданной стороны. При этом, после выполнения вычислений, стоит проверить также, была определена внутренняя или внешняя нормаль (определяется по знаку скалярного произведения найденной нормали с вектором, заданным по следующей стороне), и во втором случае вернуть вектор, обратный найденному.

Разбиение невыпуклых многоугольников

Невыпуклые многоугольники можно разбить на выпуклые. Опишем алгоритм действий.

Используется 2 операции: перенос и поворот. В общем случае эти операции требуется выполнять не 1 раз (делаем такое преобразование, чтобы очередная i-ая вершина была в начале координат, а отрезок, составленный из i-ой и i+1-ой вершин должен быть параллелен оси Х)

Последовательность действий для i-ой вершины:

1. Перенести многоугольник таким образом, чтобы i-ая вершина оказалась в начале координат.
2. Повернуть многоугольник таким образом, чтобы i+1-ая вершина оказалась бы на положительной полуоси Х.
3. Проанализировать знаки у всех i+2 вершин (то есть у всех, кроме i-ой и i+1-ой). На рисунке видно, что знаки у вершин разные, из чего можно сделать вывод, что многоугольник невыпуклый (если знаки разные - многоугольник невыпуклый). Если все знаки неотрицательные, то многоугольник выпуклый относительно текущей стороны (на самом деле стоит отметить, что условие "неотрицательности" справедливо для многоугольников, у которых вершины обходятся против часовой стрелки. Чтобы алгоритм был более универсальным, можно смотреть на одинаковость знаков, тогда можно будет учесть еще и многоугольники с обходом вершин по часовой стрелки).

Чтобы многоугольник был выпуклым, он должен быть выпуклым относительно каждой своей стороны (то есть для каждой вершины сделать перенос+поворот, анализ вершин и тд)

Если многоугольник оказался невыпуклым, в i+2-ой вершине, то надо найти точки пересечения сторон многоугольника с осью абсцисс. Из найденных точек пересечения выбрать ближайшую к началу системы координат (в нашем случае - точка С, если бы был "гребешок", то надо выбрать ближайшую)

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

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

Так же данным алгоритмом можно определять внутреннюю нормаль в процессе работы (очевидно, что нормаль к стороне многоугольника в преобразованном виде - вертикальная прямая. Знак ее должен совпадать со знаками всех остальных вершин многоугольника (ну то есть мы можем нормаль найти только для выпуклых многоугольников таким методом, но учитывая, что алгоритм может разделить невыпуклый многоугольник на выпуклые, то можно найти и для любого, в принципе)

Триангуляция многоугольников

Тоже не успели (одно из двух), смотреть тут.

Следующий вопрос: 17. Отсечение многоугольников. Алгоритм Сазерленда Ходжмена.

Предыдущий вопрос: 15. Отсечение. Алгоритм Кируса Бека отсечения отрезка.