- •Введение
- •Отображение просранства пользователя и машинного носителя
- •Расчет пользовательских и машинных координат
- •Алгоритмы генерирования линий.
- •Генерирование отрезка прямой. Алгоритм Брезенхема
- •Формирование дуги окружности.
- •Кривые Безье.
- •Двумерное отсечение
- •Отсечение прямоугольным окном. Алгоритм Сазерленда-Коуэна.
- •Отсечение выпуклым многоугольным окном. Алгоритм Кируса-Бэка
- •Определение выпуклости многоугольника.
- •Отсечение невыпуклым многоугольником.
- •Заливка областей.
- •Заливка с сортировкой
- •Заливка по ребрам.
- •Cписок активных ребер.
- •Заливка с затравкой.
- •Преобразование координат
- •Преобразования координат в двумерной системе.
- •Преобразования в трех мерной системе координат
- •Двумерные проекции
- •Виды проекций
- •Перспективные проекции
- •Определение координат точки на плоскости проекции
- •Xэ, Yэ - оси системы координат на плоскости проекции (на экране).
- •Точки и линии схода
- •Косоугольные проекции
- •Аксонометрическая проекция
- •Построение проекций трехмерных объектов
- •Затенение отрезка плоскостью при перспективной проекции
- •Удаление затеняемых ребер в аксонометрической проекции
- •Алгоритмы параллельной обработки графической информации
- •Построение сечения объекта.
Отсечение невыпуклым многоугольником.
Отсечение отрезка окном в форме невыпуклого многоугольника можно выполнить двумя способами.
1-ый способ.
Способ предполагает выполнение следующих действий.
Вводятся многоугольники, дополняющие заданный невыпуклый многоугольник до выпуклого.
Выполняется внутреннее отсечение полученным выпуклым многоугольником.
Далее для участка отрезка, полученного в результате этого внутреннего отсечения, осуществляется внешнее отсечение многоугольниками, дополняющими исходный до выпуклого. Полученная часть отрезка и будет видимой частью отрезка при его внутреннем отсечении заданным окном в форме невыпуклого многоугольника
Способ иллюстрируется ниже приведенным рисунком ().
Для окна, представленного на этом рисунке, дополняющим многоугольником будет треугольник СBD. Поэтому сначала выполняется внутреннее отсечение выпуклым многоугольником АBDE, в результате чего получается отрезок t1t3.Далее выполняется внешнее отсечение отрезка t1t3 треугольником СBD. В результате чего будет отброшена часть t1t2 , а оставшаяся часть t2t3 будет являться видимой частью исходного отрезка ТнТк в заданном окне ABCDE.
Рис. 3.4‑32
2-ой способ.
Способ предполагает выполнение следующих действий.
Заданный невыпуклый многоугольник разбивается на несколько выпуклых многоугольников.
Выполняется внутреннее отсечение заданного отреза всеми выпуклыми многоугольниками, составляющими исходнвъый не выпуклый многоугольник.
Отображение всех частей отрезков, полученных при выполнении пункта 2, позволит получить часть исходного отрезка, являющуюся результатом внутреннего отсечения исходного отрезка заданным невыпуклым многоугольником.
Наиболее удобным является разбиение исходного многоугольника на треугольники, которые всегда выпуклые. Эта процедура может быть выполнена следующим образом.
Определяются диагонали исходного многоугольника, соединяющие стороны его внутренних углов.
Из найденных диагоналей выбирается минимальная и соответствующий ей треугольник отбрасывается.
Далее процесс повторяется для оставшейся части многоугольника до тех пор, пока оставшаяся часть не станет треугольником.
Последний и отброшенные треугольники будут представлять собой множество треугольников, смоставляющих исходный многоугольник.
Для многоугольников, приведенного на следующем рисунке(Рис. 3.4 -33), отсечение треугольников будет выполняться в последовательности, соответствующей приведенной на рисунке нумерации диагоналей.
Рис. 3.4‑33
Достоинством данного способа является то, что нет необходимости проверять отдельные углы на выпуклость. Угол с минимальной диагональю, не звисимо от того, является ли исходный многоугольник выпуклым или нет, всегда будет не больше 1800.
Заливка областей.
Решение данной задачи обеспечивает придания всем внутренним точкам области, заданной своими границами, которые состоят из отдельных ребер, одинакового значение оптического параметра. В простейшем случае в результате заливки все внутренние точки рассматриваемой области приобретают один цвет (область как бы заливается чернилом заданного цвета).
При решении этой задачи для уменьшения количества обрабатываемых точек, целесообразно рассматривать только те точки пространства, которые находятся в габаритном прямоугольнике, построенном для заданной области (Рис.4-1).
В некоторых случаях существенного уменьшение количества обрабатываемых точек можно достигнуть, если габаритную фигуру для исходной области, представленной невыпуклым многоугольником, построить на основе габаритных прямоугольников отдельных выпуклых компонент заданной невыпуклой области, как это показано на приведенном рисунке (Рис.4-2Рис. 4.2 -36).
Рис.4-1.
На рисунке используются следующие обозначения:
y1max, y1min, x1max, x1min – габаритные размеры первой выпуклой составляющей исходного невыпуклого многоугольника;
y2max, y2min, x2max, x2min – габаритные размеры второй выпуклой составляющей исходного невыпуклого многоугольника.
Рис.4-2.
Для решения задачи заливки области используются различные способы, к числу которых относятся:
заливка с сортировкой;
заливка по ребрам;
заливка с использованием перегородки;
заливка с затравкой.
заливка с затравкой с использованием соседних групп.