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

 

1-й метод. Вычисляем векторные произведения смежных сторон многоугольника. Векторное произведение V ₁ Ä V ₂ =
=(V _{X 1} * V _{Y 2} – V _{Y 1} * V _{X 2}) * k, где k – единичный вектор, перпендикулярный плоскости, несущей векторы сомножителей.

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

 

 

 

Рис. 6.7. Алгоритм Кируса-Бека

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

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

 

Рис. 6.8. Определение факта выпуклости многоугольника
(вариант – многоугольник выпуклый)

Рис. 6.9. Определение факта выпуклости многоугольника
(вариант – многоугольник невыпуклый)

 

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

Вычисление уравнения внутренней нормали

 

Нормаль к стороне многоугольника можно вычислить, если вспомнить, что скалярное произведение пары перпендикулярных векторов равны нулю. Если n_x и n_y – неизвестные компоненты нормали к известному вектору (V_x, V_y) стороны многоугольника, то

n * V = (n_x * i + n_y * j) (V_x * i + V_y * j) = n_x * V_x + n_y * V_y = 0,

где i и j – единичные векторы, параллельные осям X и Y, следовательно,

n_x * V_x = – n_y * V_y,

так как нас интересует только направление нормали, то пусть
n_y = 1 и тогда n_x = – (V_y / V_x) * i + j. Если вектор стороны многоугольника образован парой вершин V_i и V_{i +1} и если скалярное произведение нормали и вектора от V_i до V_{i + 2} положительно, то n – это внутренняя нормаль, иначе – внешняя, и получить внутреннюю нормаль можно, умножив ее на минус 1.

 

Задание на лабораторную работу № 6

"Алгоритмы отсечения отрезков"

1. Постройте окно отсечения.

2. Постройте отрезок, пересекающий окно отсечения.

3. Произведите отсечение отрезка с помощью любого алгоритма.

4. Выделите другим цветом отсекаемую часть отрезка.

5. Повторите пп. 2 и 3 для полностью видимых и невидимых отрезков.

6. Сравните эффективность различных алгоритмов отсечения.

7. Чем отличаются алгоритмы Коэна-Сазерленда и FC-ал-горитм от алгоритма Кируса-Бека?