Алгоритмы компьютерной графики Пешков Анатолий Тимофеевич, БГУИР. 1 отображение просранства пользователя и машинного носителя 4

• Название: 1 отображение просранства пользователя и машинного носителя 4
• Дата: 24.09.2022
• Размер: 1.86 Mb.
• Имя файла: Алгоритмы компьютерной графики Пешков Анатолий Тимофеевич, БГУИР.doc
• Тип: Документы; #693275
• страница: 8 из 20

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

Алгоритм Кируса–Бэка предполагает наличие выпуклого многоугольника, используемого в качестве окна.

Однако на практике весьма часто возникает задача отсечения многоугольником, а информация о том, является он выпуклым или нет изначально не задается. В таком случае, прежде чем начать процедуру отсечения необходимо определить какой задан многоугольник – выпуклый или нет.

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

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

1. 
   в выпуклом многоугольнике все вершины располагаются по одну сторону от линии, несущей любое ребро (по внутреннюю сторону относительно данного ребра);
   
2. 
   все внутренние углы многоугольника меньше 180^о;
   
3. 
   все диагонали, связывающие вершины многоугольника, лежат внутри этого многоугольника;
   
4. 
   все углы многоугольника обходятся в одном направлении ().
   

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

Векторное произведение Wдвух векторовaиb(Рис. Определение выпуклости многоугольника.-31 а)определяется как:

где:

• 
  a_x,a_y,a_z и b_x,b_y,b_z являются проекциями на оси координат X,Y,Z, соответственно, векторов – сомножителей a и b,
  
• 
  i, j, k – единичные векторы по координатным осям X, Y, Z.
  

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




Рис. Определение выпуклости многоугольника.‑31
Если рассматривать двумерное представление многоугольника как представление его в координатной плоскости XY трехмерной системе координат X,Y,Z (Рис. Определение выпуклости многоугольника.-31 b), то выражение для формирования векторного произведения векторов U и V , где векторы U и V являются соседними ребрами, образующими угол многоугольника, можно записать в виде определитель:

Вектор векторного произведения перпендикулярен плоскости, в которой находятся вектора-сомножители. Направление вектора произведения определяется по правилу буравчика или по правилу винта с правой нарезкой.

Для случая, представленного на Рис. Определение выпуклости многоугольника.-31 b), вектор W, соответствующий векторному произведению векторов V,U, будет иметь ту же направленность, что и направленность координатной оси Z.

Учитывая то, что проекции на ось Z векторов –сомножителей в этом случае равны нулю, векторное произведение можно представить в виде:
(3.3-1)
Единичный вектор k всегда положительный, следовательно, знак вектора  векторного произведения будет определяться только знаком определителя  в выше приведенном выражении. Отметим, что на основании свойства векторного произведения, при перестановке местами векторов-сомножителей U и V знак вектора  будет меняться на противоположный.

Отсюда следует, что, если в качестве векторов V и U рассматривать два соседних ребра многоугольника, то порядок перечисления векторов в векторном произведении можно поставить в соответствие c обходом рассматриваемого угла многоугольника или ребер, образующих этот угол. Это позволяет использовать в качестве критерия определения выпуклости многоугольника правило:

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


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

Так как ребра многоугольник задаются в виде координат их концевых точек, то для определения знака векторного произведения удобнее использовать определитель:

Легко показать, что этот определитель эквивалентен определителю в выражении (3.3-1).