Алгоритм. 1. Сформировать ТР и подготовить ТАР

1. Сформировать ТР и подготовить ТАР

2. Выбор первой координаты сканируемой строки: у = min {y_min};

3. Если у = у_min, то перенос группы из ТР в ТАР.

Таблица активных ребер (ТАР)

Ребро	уНАЧ	хНАЧ	∆х	VНАЧ	∆V
AB			0.5
AE
DC			0.25
DE			-1

4. Упорядочивание ребер в ТАР по возрастанию х_НАЧ.

5. Сканирование (проводят сканирующую строку).
а) переключение режимов по х_НАЧ

б) учёт прохождения через вершины – локальные экстремумы. Если точка – локальный экстремум, то режим следует сохранить. Для отслеживания данной ситуации можно включить в ТР у_max, при совпадении необходим дополнительный анализ.

в) проводить линейную интерполяцию яркости при закраске от (х_НАЧ , V_НАЧ)_i до (х_НАЧ , V_НАЧ)_i+1

6. Удалить из ТАР те ребра, для которых справедливо у = у_max

7. Для всех элементов в ТАР произвести: х_НАЧ = х_НАЧ + ∆х; V_НАЧ = V_НАЧ + ∆V;

8. Переход к следующей сканирующей строке: y=y+1;

9. Проверка на окончание: если y>max{у_max}, то конец, иначе осуществить переход к п.3).

Отсечение плоских фигур (алгоритм Коэна-Сазерленда)

Предварительно необходимо договориться о направлении обхода вершин (по часовой стрелке или против неё). Фигура должна быть замкнутой.

Последовательно производят отсечение многоугольника по четырём границам.

.

Анализ ребер: возможно 4 варианта расположения ребра в пространстве:

Может также возникнуть вариант, когда ребро совпадает с границей.

В случае 1: Добавить в список рисуемых вершин Р;

2: Добавить в список Q;

3: Ничего не добавляется;

4: Добавить в список Р,Q;

Пример: многоугольник задан списком вершин {1,2,3,4,5,6,7,1}

Последовательно переберём все рёбра. Начнем процесс с точки 1 и ребра 1-2. Начнём формировать новый список вершин. В соответствии с ориентацией ребра занесём в выходной список вершину 2 => {2}. Далее рассмотрим ребро 2-3: добавляется точка 8 => {2, 8}

3-4: {2, 8, 9, 4}.

4-5: {2, 8, 9, 4, 10}.

5-6: {2, 8, 9, 4, 10}. Ребро полностью оказалось вне, поэтому ничего не добавляется.

6-7: {2, 8, 9, 4, 10, 11, 7}.

7-1: {2, 8, 9, 4, 10, 11, 7, 1}.

Таким образом, новый список вершин: {2, 8, 9, 4, 10, 11, 7, 1}.

Определение яркости в точке пересечения с областью вывода.

Вычисления проводятся по одной из двух формул:

(1)

(2)

Примечание:

По формуле (1) считают, если |у₂ – у₁| ³ |х₂ – х₁|, по формуле (2) - если

|у₂ – у₁| < |х₂ – х₁|;

Геометрические преобразования