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

1-й метод. Вычисляем векторные произведения смежных сторон многоугольника. Векторное произведение V₁  V₂ = (V_X1*V_Y2 – V_Y1*V_X2)*k, где k – единичный вектор, перпендикулярный плоскости, несущей векторы сомножителей. Выводы: если все значения произведений равны нулю – многоугольник вырождается в отрезок; есть как положительные, так и отрицательные знаки произведений – многоугольник невыпуклый; все произведения либо неотрицательные, либо неположительные – многоугольник выпуклый.

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

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

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

Нормаль к стороне многоугольника можно вычислить, если вспомнить, что скалярное произведение пары перпендикулярных векторов равны нулю. Если 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.8. Определение факта выпуклости многоугольника (вариант – многоугольник выпуклый)

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

З адание на лабораторную работу № 6 "Алгоритмы отсечения отрезков"

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

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

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

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

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

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

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