Алгоритм закраски областей, заданных списком вершин

(метод построчного сканирования)

Интерполяция яркости при закраске областей

О линейной интерполяции яркости при закраски области можно говорить, если закрашиваемая фигура плоская т.е. лежит в одной плоскости, например (ХУ).

Рис. 2.9.5.

Плоскость определяется по трём точкам:

Рис. 2.9.6.

|| || - определитель матрицы;

A·x + B·y + D A В D

V = - ¾¾¾¾¾¾¾ = a·x + b·y + g, где a = - ¾, b = - ¾, g = - ¾;

C С C C

V = V₁ + α (х - х₁)+β (у - у₁), где

V – яркость в произвольной точке, V₁ – яркость известная.

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

Существуют различные задачи закраски: выпуклых многоугольников и многоугольников произвольной формы. Начнем с закраски произвольного многоугольника.

Рис.2.9.7.

Сначала находят y_max и y_min. Далее для текущей у-координаты находят крайнее левое и крайнее правое ребро. Начинают с крайнего левого ребра: идут вправо (и закрашивают соответствующие точки) до пересечения со следующим ребром. Также необходим анализ на наличие локальных экстремумов. В этих точках режим закраски не меняется.

Алгоритм работает с помощью 2-х таблиц:

1. таблица ребер (ТР);

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

В ТР заносятся все ребра, а в ТАР лишь те ребра, которые мы пересекаем.

Составление ТР:

Все ребра делятся на группы по нарастанию у-координаты, а внутри группы рёбра упорядочиваются в соответствии с нарастанием х_нач. Ребро в таблицу заносится только 1 раз, горизонтальные ребра игнорируются.

A (1, 2) B (4, 8) C (8, 6) D (7, 2) E (5, 4)

Таблица рёбер:

Группа, №	Ребро	ymin	ymax	хНАЧ	хКОН	∆x	VНАЧ	VКОНЕЧ	∆V
	АВ					0.5
	АЕ
	DC				0.25
	DE				-1
	CB					-2

х_{КОН ¾} х_НАЧ V_{КОНЕЧ ¾} V_НАЧ

Dх = ¾¾¾¾¾¾; DV = ¾¾¾¾¾¾¾;

y_{max ¾} y_min y_{max ¾} y_min