Определение факта выпуклости многоугольника
1-й метод. Вычисляем векторные произведения смежных сторон многоугольника. Векторное произведение V1 Ä V2 =
=(VX1 *VY2 – VY1 * VX2) *k, где k – единичный вектор, перпендикулярный плоскости, несущей векторы сомножителей.
Выводы: если все значения произведений равны нулю – многоугольник вырождается в отрезок; есть как положительные, так и отрицательные знаки произведений – многоугольник невы-пуклый; все произведения либо неотрицательные, либо неположительные – многоугольник выпуклый.
Рис. 6.7. Алгоритм Кируса-Бека
2-й метод. Одна из вершин выбирается как базовая, вычисляются векторные произведения пар векторов, начинающихся в этой базе и заканчивающиеся в вершинах многоугольника. Выводы аналогичны предыдущему методу.
3-й метод. Для каждой i-й вершины окна перенести ее так, чтобы эта вершина совпадала с началом координат. Повернуть многоугольник так, чтобы (i + 1)-я вершина оказалась на положительной полуоси X. Вычислить знак ординаты (i + 2)-вершины. Если знаки ординат всех (i + 2)-х вершин либо неположительны, либо неотрицательны, то многоугольник выпуклый, иначе – невыпуклый (рис. 6.8 и 6.9). Достоинством последнего метода явля-
Рис. 6.8. Определение факта выпуклости многоугольника
(вариант – многоугольник выпуклый)
Рис. 6.9. Определение факта выпуклости многоугольника
(вариант – многоугольник невыпуклый)
ется то, что с его помощью можно разбить невыпуклый многоугольник на несколько выпуклых многоугольников, хотя разбиение может оказаться неоптимальным, и некорректно разбиваются многоугольники, стороны которых пересекаются между собой.
Вычисление уравнения внутренней нормали
Нормаль к стороне многоугольника можно вычислить, если вспомнить, что скалярное произведение пары перпендикулярных векторов равны нулю. Если nx и ny – неизвестные компоненты нормали к известному вектору (Vx, Vy) стороны многоугольника, то
n *V= (nx * i + ny *j) (Vx * i+ Vy *j) = nx *Vx + ny *Vy = 0,
где i и j – единичные векторы, параллельные осям X и Y, следовательно,
nx *Vx = – ny *Vy,
так как нас интересует только направление нормали, то пусть
ny = 1 и тогда nx = – (Vy / Vx) * i + j. Если вектор стороны многоугольника образован парой вершин Vi и Vi+1 и если скалярное произведение нормали и вектора от Vi до Vi + 2 положительно, то n – это внутренняя нормаль, иначе – внешняя, и получить внутреннюю нормаль можно, умножив ее на минус 1.
Задание на лабораторную работу № 6
"Алгоритмы отсечения отрезков"
1. Постройте окно отсечения.
2. Постройте отрезок, пересекающий окно отсечения.
3. Произведите отсечение отрезка с помощью любого алгоритма.
4. Выделите другим цветом отсекаемую часть отрезка.
5. Повторите пп. 2 и 3 для полностью видимых и невидимых отрезков.
6. Сравните эффективность различных алгоритмов отсечения.
7. Чем отличаются алгоритмы Коэна-Сазерленда и FC-ал-горитм от алгоритма Кируса-Бека?