«национальный исследовательский томский политехнический университет»

3.6.PDF

Формат PDF (Portable Document Format) предложен фирмой Adobe как независимый от платформы формат, в котором могут быть сохранены и иллюстрации (векторные и растровые), и текст, причем со множеством шрифтов и гипертекстовых ссылок. Для достижения продекларированной в названии переносимости размер PDF-файла должен быть малым. Для этого используется компрессия (для каждого вида объектов применяется свой способ). Например, растровые изображения записываются в формате JPEG.

Для работы с этим форматом компания Adobe выпустила пакет Acrobat. Бесплатная утилита Acrobat Reader позволяет читать документы и распечатывать их на принтере, но не дает возможности создавать или изменять их. Acrobat Distiller переводит в этот формат PostScript-файлы. Многие программы (Adobe PageMaker, CorelDraw, FreeHand) позволяют экспортировать свои документы в PDF, а некоторые – еще и редактировать графику, записанную в этом формате. Обычно в этом формате хранят документы, предназначенные только для чтения, но не для редактирования. Файл в формате PDF содержит все необходимые шрифты. Это удобно и позволяет не передавать шрифты для вывода (передача шрифтов не вполне законна с точки зрения авторского права).

PostScript

Это язык описания страниц, предназначеный для формирования изображений произвольной сложности и вывода их на печать. Для этого в языке имеется широкий набор графических операторов, используемых в произвольной комбинации. Все графические операторы языка, формирующие изображение, можно разделить на три группы. Это:

• 
  векторная графика, позволяющая рисовать прямые линии, дуги, кривые произвольного размера, ориентации, ширины, закрашивать площади любого размера, формы, цвета; цвет для линий или заливок может задаваться в любом из цветовых пространств языка; любой описанный на языке контур может быть границей клипирования изображения; контур клипирования задаёт границы рисуемого изображения;
  
• 
  работа с текстом – для вывода текста произвольного размера в различных гарнитурах, размещая его с произвольной ориентацией в произвольном месте страницы; текст полностью интегрирован с графикой – все текстовые символы трактуются как графические фигуры и могут обрабатываться любым из графических операторов;
  
• 
  растровые изображения позволяют выводить на листе сканированные рисунки или фотографии с масштабированием и ориентацией, источником растра может быть как текущий файл, содержащий программу на PostScriptе, так и внешний; считывание цветовых слоев может вестись как из одного файла, так и из нескольких сепарированных. Изображение, описываемое на языке PostScript, никак не зависит от разрешающей способности выходного устройства и его цветовой глубины (числа цветов). Приближение к конкретным разрешающим возможностям выходного устройства – это процесс, не связанный с описанием изображения на языке PostScript, и выполняется для каждого выходного устройства по-своему. В этом и заключается устройство-независимость языка PostScript. Качество изображения определяется конкретным выходным устройством, его физическими ограничениями.
  

Формирование изображения на выходном устройстве является двухступенчатым процессом:

1. Приложение генерирует устройство независимое изображение на языке PostScript.

2. Система обработки изображения (интерпретатор) интерпретирует изображение (программу) и приближает его к характеристикам конкретного выходного устройства.

4.Растровые алгоритмы

Большинство графических устройств являются растровыми, представляя изображение в виде прямоугольной матрицы (сетки, целочисленной решетки) пикселей (растра), и большинство графических библиотек содержат внутри себя достаточное количество простейших растровых алгоритмов. На Рис. 4. приведена система растровых алгоритмов.

Растровые алгоритмы
Алгоритмы обработки растровых изображений

Алгоритмы перевода графических примитивов в растровую форму

Алгоритмы заполнения областей и многоугольников

Регулировка яркости и контрастности

Масштабирование изображений

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

Алгоритмы фильтрации

Алгоритмы растеризации
Рис. 4.. Классификация растровых алгоритмов

4.1.Алгоритмы растеризации

Прежде чем перейдем к непосредственному рассмотрению возможности перевода математического описания объекта (линии и пр.) в растровую форму, рассмотрим понятие связности. Связность – возможность соединения двух пикселей растровой линией, т. е. последовательным набором пикселей. Возникает вопрос, когда пиксели (x₁, y₁) и (x₂, y₂) можно считать соседними. Для этого вводятся два понятия связности:

1. Четырехсвязность: пиксели считаются соседними, если либо их x-координаты, либо их y – координаты отличаются на единицу:

|x₁ – x₂| + |y₁ – y₂| ≤ 1;

2. Восьмисвязность: пиксели считаются соседними, если их x-координаты и y-координаты отличаются не более чем на единицу:

|x₁ – x₂| ≤ 1, |y₁ – y₂| ≤ 1.

На Рис. 4. изображены четырехсвязная и восьмисвязная линии.



Рис. 4.. Классификация растровых алгоритмов

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

4.1.1.Растровое представление отрезка. Алгоритм Брезенхейма

Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки A(x_a, y_a) и B(x_b, y_b). Для простоты будем считать, что

0 ≤ y_b – y_a ≤ x_b – x_a . Тогда отрезок описывается уравнением:

y = y_a + (x–x_a), x Є [x_a, x_b] или y = kx + b.

Отсюда получаем простейший алгоритм растрового представления отрезка:
private void MyLine(int xa, int ya, int xb, int yb, Color color)

{

double k = ((double)(yb - ya)) / (xb - xa);

double b = ya - k * xa;

Bitmap bmp;

bmp = new Bitmap(this.ClientSize.Width,

this.ClientSize.Height);

for (int x = xa; x <= xb; x++){

bmp.SetPixel(x, (int) (k*x + b), color);}

Graphics gr = CreateGraphics();

gr.DrawImage(bmp, 0, 0);

}

Вычислений значений функции y = kx + b можно избежать, используя в цикле рекуррентные соотношения, так как при изменении x на 1 значение y меняется на k:
private void MyLineN(int xa, int ya, int xb, int yb, Color color)

{

double k = ((double)(yb - ya)) / (xb - xa);

double y = ya;

Bitmap bmp;

bmp = new Bitmap(this.ClientSize.Width,

this.ClientSize.Height);

for (int x = xa; x <= xb; x++, y+= k){

bmp.SetPixel(x, (int)y, color);}

Graphics gr = CreateGraphics();

gr.DrawImage(bmp, 0, 0);

}
Приведенные простейшие пошаговые алгоритмы построения отрезка имеют ряд недостатков:

1. 
   Выполняют операции над числами с плавающей точкой, а желательно было бы работать с целочисленной арифметикой;
   
2. 
   На каждом шаге выполняется операция округления, что также снижает быстродействие.
   

Эти недостатки устранены в следующем алгоритме Брезенхейма.

Как и в предыдущем случае, будем считать, что тангенс угла наклона отрезка принимает значение в диапазоне от 0 до 1. Рассмотрим i-й шаг алгоритма (Рис. 4.). На этом этапе пиксель P_i-1 уже найден как ближайший к реальному отрезку. Требуется определить, какой из пикселей (T_i или S_i) будет установлен следующим.

P_i-1 = (r, q)

= (x_i-1, y_i-1)

S_i = (r+1, q)

T_i = (r+1,q+1)

S

T

y=x
Рис. 4.. i-й шаг алгоритма Брезенхейма

В алгоритме используется управляющая переменная d_i, которая на каждом шаге пропорциональна разности между S и T. Если S < T, то S_i ближе к отрезку, иначе выбирается T_i.

Пусть изображаемый отрезок проходит из точки (x₁, y₁) в точку (x₂, y₂). Исходя из начальных условий, точка (x₁, y₁) ближе к началу координат. Тогда перенесем оба конца отрезка с помощью преобразования T(–x₁, –y₁), так чтобы первый конец отрезка совпал с началом координат. Начальной точкой отрезка стала точка (0, 0), конечной точкой – (dx, dy), где dx = x₂ – x₁, dy = y₂ – y₁ (Рис. 4.).

y

q

r

r+1

P_i-1

S

T

x

dy
Рис. 4.. Вид отрезка после переноса в начало координат

Уравнение прямой в этом случае будет иметь вид:

y=x.

Обозначим координаты точки P_i-1 после переноса через (r, q). Тогда S_i = (r+1, q) и T_i = (r+1, q+1).

Из подобия треугольников на Рис. 4. можно записать, что

=.

Выразим S:

S = (r + 1) – q.

T можно представить как T = 1 – S. Используем предыдущую формулу

T = 1 – S = 1 – (r + 1) – q.

Найдем разницу S – T:

S – T = (r + 1) – q – 1 + (r + 1) – q = 2 (r + 1) – 2 q – 1.

Помножим левую и правую часть на dx:

dx (S – T) = 2 dy (r + 1) – 2 q dx – dx = 2 (r dy – q dx) + 2 dy – dx.

Величина dx положительная, поэтому неравенство dx (S – T) < 0 можно использовать в качестве проверки при выборе S_i. Обозначим d_i = dx (S – T), тогда

d_i = 2 (r dy – q dx) + 2 dy – dx.
Поскольку r = x_i-1 и q = y_i-1, то
d_i = 2 x_i-1 dy –2 y_i-1 dx + 2 dy – dx.
Прибавляя 1 к каждому индексу найдем d_i+1:
d_i+1 = 2 x_i dy –2 y_i dx + 2 dy – dx.
Вычитая d_i из d_i+1 получим
d_i+1 – d_i = 2 dy (x_i – x_i-1) – 2 dx (y_i – y_i-1).
Известно, что x_i – x_i-1 = 1, тогда
d_i+1– d_i = 2 dy – 2 dx (y_i – y_i-1).
Отсюда выразим d_i+1:
d_i+1 = d_i + 2 dy – 2 dx (y_i – y_i-1).
Таким образом, получили итеративную формулу вычисления управляющего коэффициента d_i+1 по предыдущему значению d_i. С помощью управляющего коэффициента выбирается следующий пиксель – S_i или T_i.

Если d_i ≥ 0, тогда выбирается T_i и y_i = y_i–1 + 1, d_i+1 = d_i +2 (dy – dx). Если d_i < 0, тогда выбирается S_i и y_i = y_i–1 и d_i+1 = d_i +2 dy.

Начальные значения d₁ с учетом того, что (x₀, y₀) = (0, 0),

d₁ = 2 dy – dx.

Преимуществом алгоритма является то, что для работы алгоритма требуются минимальные арифметические возможности: сложение, вычитание и сдвиг влево для умножения на 2.

Реализация этого алгоритма выглядит следующим образом:
private void BLine(int x1, int y1, int x2, int y2, Color color)

{

int dx, dy, inc1, inc2, d, x, y, Xend;

dx = Math.Abs(x2 - x1);

dy = Math.Abs(y2 - y1);

d = (dy << 1) - dx;

inc1 = dy << 1;

inc2 = (dy - dx) << 1;

if (x1 > x2)

{

x = x2;

y = y2;

Xend = x1;

}

else

{

x = x1;

y = y1;

Xend = x2;

};

Bitmap bmp;

bmp = new Bitmap(this.ClientSize.Width,

this.ClientSize.Height);

bmp.SetPixel(x, y, color);

while (x < Xend)

{

x++;

if (d < 0) d = d + inc1;

else {y++; d = d + inc2;};

bmp.SetPixel(x, y, color);

}

Graphics gr = CreateGraphics();

gr.DrawImage(bmp, 0, 0);

}

Если dy > dx, то необходимо будет использовать этот же алгоритм, но пошагово увеличивая y и на каждом шаге вычислять x.

4.1.2.Растровая развёртка окружности

Существует несколько очень простых, но не эффективных способов преобразования окружностей в растровую форму. Например, рассмотрим для простоты окружность с центром в начале координат. Ее уравнение записывается как x² + y² = R². Решая это уравнение относительно y, получим
y = ± .
Чтобы изобразить четвертую часть окружности, будем изменять x с единичным шагом от 0 до R и на каждом шаге вычислять y. Вторым простым методом растровой развертки окружности является использование вычислений x и y по формулам x = R cos α, y = R sin α при пошаговом изменении угла α от 0 до 90.

Для упрощения алгоритма растровой развёртки стандартной окружности можно воспользоваться её симметрией относительно координатных осей и прямых y = ± x; в случае, когда центр окружности не совпадает с началом координат, эти прямые необходимо сдвинуть параллельно так, чтобы они прошли через центр окружности. Тем самым достаточно построить растровое представление для 1/8 части окружности, а все оставшиеся точки получить симметрией (см. Рис. 4.).

(x, y)

(y, x)

(y, –x)

(x, –y)

(–x, y)

(–y, x)

(–y, –x)

(–x, –y)
Рис. 4.. Восьмисторонняя симметрия

Рассмотрим участок окружности из второго октанта x Є [0, R/]. Далее опишем алгоритм Брезенхейма для этого участка окружности.

На каждом шаге алгоритм выбирает точку P_i (x_i, y_i), которая является ближайшей к истинной окружности. Идея алгоритма заключается в выборе ближайшей точки при помощи управляющих переменных, значения которых можно вычислить в пошаговом режиме с использованием небольшого числа сложений, вычитаний и сдвигов.

Рассмотрим небольшой участок сетки пикселей, а также возможные способы (от A до E) прохождения истинной окружности через сетку (Рис. 4.).

Предположим, что точка P_i-1 была выбрана как ближайшая к окружности при x = x_i-1. Теперь найдем, какая из точек (S_i или T_i) расположена ближе к окружности при x = x_i-1 + 1.

A

B

C

D

E

P_i-1 =(x_i-1, y_i-1)

S_i =(x_i-1 + 1, y_i-1)

T_i =(x_i-1+1, y_i-1 – 1)
Рис. 4.. Варианты прохождения окружности через растровую сетку

Заметим, что ошибка при выборе точки P_i (x_i, y_i) была равна

D(P_i) = (x_i²+ y_i²) – R².
Запишем выражение для ошибок, получаемых при выборе точки S_i или T_i:
D(S_i) = [(x_i-1+ 1)² + (y_i-1)²] – R²;

D(T_i) = [(x_i-1+ 1)² + (y_i-1 – 1)²] – R².
Если | D(S_i) | ≥ | D(T_i) |, то T_i ближе к реальной окружности, иначе выбирается S_i.

Введем d_i = | D(S_i) | – | D(T_i) |.
T_i будет выбираться при d_i ≥ 0, в противном случае будет устанавливаться S_i.

Опуская алгебраические преобразования, запишем d_i и d_i+1 для разных вариантов выбора точки S_i или T_i.
D₁ = 3 – 2 R.
Если выбирается S_i (когда d_i < 0), то d_i+1 = d_i + 4 x_i-1 + 6.

Если выбирается T_i (когда d_i ≥ 0), то d_i+1 = d_i + 4 (x_i-1 – y_i-1) + 10.

Существует модификация алгоритма Брезенхейма для эллипса.

4.1.3.Кривые Безье

Кривые Безье были разработаны в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Касталье (Кастельжо) из компании «Ситроен», где применялись для проектирования кузовов автомобилей. Благодаря простоте задания и манипуляции, кривые Безье нашли широкое применение в компьютерной графике для представления гладких линий.

Построение кривых Безье является решением задачи аппроксимации, то есть построения кривой по узловым точкам. При этом кривая не обязательно проходит через данные точки. В случае кривых Безье, кривая проходит через первую и последнюю точку, а промежуточные точки играют роль рычагов, задающих форму кривой.

Кривая Безье это параметрическая кривая, задаваемая выражением:



где P_i – функция компонент векторов опорных вершин, а b_i,n(t) – базисные функции кривой Безье, называемые также полиномами Бернштейна.





где n – степень полинома, i – порядковый номер опорной вершины.

Наглядный метод построения этих кривых, предложенный де Кастелье, основан на разбиении отрезков, соединяющих исходные точки в отношении t (значение параметра), а затем в рекурсивном повторении этого процесса для полученных отрезков:



Нижний индекс – номер опорной точки, верхний индекс – уровень разбиения. Уравнение n-ого порядка задается

Вид кривой зависит от количества опорных точек. Наиболее часто используются линейные, квадратные, кубические и кривые четвертого порядка.
Линейные кривые

При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P₀ и P₁ определяют его начало и конец. Кривая задаётся уравнением:

B(t) = (1–t) P₀ + t P₁ t Є [0, 1].
Квадратные кривые

Квадратная кривая Безье (n = 2) задаётся 3-я опорными точками: P₀, P₁ и P₂. Кривая задаётся уравнением:
B(t) = (1–t)² P₀ +2t(1-t) P₁ + t² P₂ t Є [0, 1].
Данное уравнение можно получить с помощью метода де Касталье следующим образом. Обозначим опорные точки, как , начало кривой положим в точке P₀ (t = 0) , а конец - в точке P₂ (t = 1); для каждого t Є [0, 1] найдем точку :

,

,

,

таким образом, получим кривую второго порядка.

Точки и лежат на кривых первого порядка (отрезках) соединяющие опорные точки P₀ с P₁ и P₁ c P₂ соответственно. Точки, образующие кривую Безье, лежат на отрезке, соединяющем с пропорционально изменению параметра t (Рис. 4.).



Рис. 4.. Кривая Безье с тремя опорными точками

Кубические кривые

В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:
B(t) = (1–t)³ P₀ + 3t(1-t)² P₁ + 3t²(1-t) P₂ + t³ P₃ t Є [0, 1].
Для получения этой формулы используем аналогичным способом метод де Касталье.

Обозначим опорные точки, как, начало кривой положим в точке P₀ (t = 0) , а конец - в точке P₃ (t = 1); для каждого t Є [0, 1] найдем точку :

,

,

,

,

,

,

таким образом, получим кривую третьего порядка (Рис. 4.).



Рис. 4.. Кривая Безье с четырьмя опорными точками

Четыре опорные точки P₀, P₁, P₂ и P₃, заданные в двух или трехмерном пространстве определяют форму кривой.

Линия берёт начало из точки P₀ направляясь к P₁ и заканчивается в точке P₃ подходя к ней со стороны P₂. То есть кривая не проходит через точки P₁ и P₂, они используются для указания её направления. Длина отрезка между P₀ и P₁ определяет, как скоро кривая повернёт к P₃.

В матричной форме кубическая кривая Безье записывается следующим образом:

где M_B называется базисной матрицей Безье:

Сплайн Безье

Кривые Безье обладают рядом свойств:

1. 
   непрерывность заполнения сегмента между начальной и конечной точками;
   
2. 
   инвариантность относительно аффинных преобразований. Как следствие поворот вокруг точки, масштабирование и изменение пропорций кривой Безье не нарушает ее стабильности;
   
3. 
   кривая Безье принадлежит выпуклой оболочке опорных точек, т.е. кривая всегда располагается внутри фигуры, образованной линиями, соединяющими контрольные точки;
   
4. 
   если все опорные точки лежат на одной прямой, то кривая Безье вырождается в отрезок, соединяющий эти точки;
   
5. 
   кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;
   
6. 
   степень многочлена, представляющего кривую в аналитическом виде, на единицу меньше числа опорных точек.
   

Одним из главных свойств кубических кривых Безье является возможность составления из них сплайнов.

Понятие сплайна пришло из машиностроения, где сплайном называли гибкую линейку, закрепив которую в нужных местах, добивались плавной формы кривой, и затем чертили ее по этой линейке.

В математике под сплайном обычно понимают кусочно-заданную функцию, совпадающую с функциями более простой природы на каждом элементе разбиения своей области определения.

В случае с кривыми Безье сплайн обычно составляется из нескольких кубических кривых. Если точка P_n является стыковочной точкой, для соблюдения условия гладкости кривой в ней, необходимо, что бы выполнялось условие коллинеарности с соседними узловыми точками (Рис. 4.).


Рис. 4.. Соблюдение условия гладкости на стыке кривых Безье

Однако даже такие достаточно развитые средства аппроксимации кривыми Безье не позволяют построить окружность, описываемую параметрически как:


так как sin и cos для достаточно хорошего приближения требуют многочленов высокой степени.

4.1.4.Закраска области, заданной цветом границы

Рассмотрим область, ограниченную набором пикселей заданного цвета и точку (x, y), лежащую внутри этой области.

Задача заполнения области заданным цветом в случае, когда эта область не является выпуклой, может оказаться довольно сложной.

Приведем простейший рекурсивный алгоритм заполнения области:
private void MyPixelFill(int x, int y, Color border_color, Color c_color)

{

Color c = bmp.GetPixel(x, y);

if ((c.ToArgb() != border_color.ToArgb()) &&

(c.ToArgb() != c_color.ToArgb()))

{

bmp.SetPixel(x, y, c_color);

MyPixelFill(x - 1, y, border_color, c_color);

MyPixelFill(x + 1, y, border_color, c_color);

MyPixelFill(x, y - 1, border_color, c_color);

MyPixelFill(x, y + 1, border_color, c_color);

}

}

Заметим, что корректное использование метода GetPixel возможно, если предварительно объекты типа Graphics и Bitmap связаны и инициализируются следующим образом:

bmp = new Bitmap(this.ClientSize.Width, this.ClientSize.Height);

gr = Graphics.FromImage(bmp);

Этот алгоритм является слишком неэффективным, так как для всякого уже отрисованного пикселя функция вызывается ещё 4 раза и, кроме того, этот алгоритм требует слишком большого объёма стека из-за большой глубины рекурсии. Поэтому для решения задачи закраски области предпочтительнее алгоритмы, способные обрабатывать сразу целые группы пикселей, т. е. использовать их «связность» или «когерентность». Если данный пиксель принадлежит области, то, скорее всего, его ближайшие соседи также принадлежат данной области.

Группой таких пикселей обычно выступает полоса, определяемая правым пикселем. Для хранения правых определяющих пикселей используется стек. Словесно опишем улучшенный алгоритм, использующий когерентность пикселей.

Сначала заполняется горизонтальная полоса пикселей, содержащих начальную точку. Затем, чтобы найти самый правый пиксель каждой строки, справа налево проверяется строка, предыдущая по отношению к только что заполненной полосе. Адреса найденных пикселей заносятся в стек. То же самое выполняется и для строки, следующей и за последней заполненной полосой. Когда строка обработана таким способом, в качестве новой начальной точки используется пиксель, адрес которого берется из стека. Для него повторяется вся описанная процедура. Алгоритм заканчивает свою работу, если стек пуст.

4.1.5.Заполнение многоугольника

Часто возникает задача заполнения многоугольников, заданных набором вершин.

Задача заполнения многоугольников решается в два этапа:

1) сначала проводится операция отсечения многоугольника;

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

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

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

Рассмотрим алгоритм Сазерленда-Ходгмана (Sutherland-Hodgman). В алгоритме используется стратегия «разделяй и властвуй», которая позволяет решение общей задачи свести к решению ряда простых и похожих подзадач. Примером такой подзадачи является отсечение многоугольника относительно одной отсекающей границы. Последовательное решение четырех таких задач позволяет провести отсечение относительно прямоугольной области (Рис. 4.).
Рис. 4.. Последовательное отсечение многоугольника

На вход алгоритма поступает последовательность вершин многоугольника V₁, V₂, …, V_n. Ребра многоугольника проходят от V_i к V_i+1 от V_n к V₁. С помощью алгоритма производится отсечение относительно ребра и выводится другая последовательность вершин, описывающая усеченный многоугольник.

Алгоритм «обходит» вокруг многоугольника от V_n к V₁ и обратно к V_n, проверяя на каждом шаге соотношение между последовательными вершинами и отсекающей границей. Необходимо проанализировать четыре случая (Рис. 4.).

Рассмотрим изображенное на Рис. 4. ребро многоугольника, соединяющее вершину s с вершиной p. В первом случае ребро полностью лежит внутри отсекающей границы, к выходному списку добавляется вершина p. Во втором случае в качестве вершин выводится точка пересечения i, поскольку ребро пересекает границу, а начальная точка была выведена при анализе первого случая. В третьем случае обе вершины находятся за пределами границы и ни одна из них не выводится. В четвертом случае к выходному списку добавляется и точка пересечения i, и вершина p.
Внутри

Вне

Случай 1

p-выход

Отсекающая граница

s

Внутри

Вне

Случай 3

(нет выхода)

p
Внутри

Вне

Случай 4

p-второй выход
s

i-первый выход

Внутри

Вне

Случай 2

p
i-выход

s

s
Рис. 4.. Случаи, возникающие при отсечении многоугольников

При отсечении многоугольника описанным алгоритмом возникает проблема, связанная с тем, что появляются ребра, частично совпадающие с границей окон. Лишние ребра можно устранить, введя дополнительную обработку или воспользовавшись более общим и более сложным алгоритмом Вейлера – Азертона.
Заполнение многоугольников

Рассмотрим, каким образом можно заполнить многоугольник, задаваемый замкнутой ломаной линией без самопересечений.

Простейший способ закраски многоугольника состоит в проверке принадлежности каждой точки этому многоугольнику. Более эффективные алгоритмы используют тот факт, что соседние пиксели, вероятно, имеют одинаковые характеристики (кроме пикселей граничных ребер). Это свойство называется пространственной когерентностью.

В случае с многоугольником когерентность пикселей определяется вдоль сканирующей строки. Сканирующие строки обычно изменяются от «верха» многоугольника до его «низа». Характеристики пикселей изменяются только там, где ребро многоугольника пересекает строку. Эти пересечения делят сканирующую строку на области закрашенных и не закрашенных пикселей.

Рассмотрим, какие случаи могут возникнуть при делении многоугольника на области сканирующей строкой.
4

5

6

1

4

5

6

2

y

x
Рис. 4.. Прохождение сканирующих строк по многоугольнику

1. 
   Простой случай. Например, на Рис. 4. сканирующая строка y = 4 пересекает многоугольник при x = 1 и x = 6. Получается три области: x < 1; 1 ≤ x ≤ 6; x > 8. Сканирующая строка y = 6 пересекает многоугольник при x = 1; x = 2; x = 5; x = 6. Получается пять областей: x < 1; 1 ≤ x ≤ 2; 2 < x < 5; 5 ≤ x ≤ 6; x > 6. В этом случае x сортируется в порядке возрастания. Далее список иксов рассматривается попарно. Между парами точек пересечения закрашиваются все пиксели. Для y = 4 закрашиваются пиксели в интервале (1, 6), для y = 6 закрашиваются пиксели в интервалах (1, 2) и (5, 6).
   
2. 
   Сканирующая строка проходит через вершину (Рис. 4.). Например, по сканирующей строке y = 3 упорядоченный список x получится как (2, 2, 4). Вершина многоугольника была учтена дважды, и поэтому закрашиваемый интервал получается неверным: (2, 2). Следовательно, при пересечении вершины сканирующей строкой она должна учитываться единожды. И список по х в приведенном примере будет (2, 4).
   
3. 
   Сканирующая строка проходит через локальный минимум или максимум (см. Рис. 4. при y = 5). В этом случае учитываются все пересечения вершин сканирующей строкой. На рис. Error: Reference source not found при y = 5 формируется список x (1, 4, 4, 6). Закрашиваемые интервалы (1, 4) и (4, 6). Условие нахождения локального минимума или максимума определяется при рассмотрении концевых вершин для ребер, соединенных в вершине. Если у обоих концов координаты y больше, чем y вершины пересечения, то вершина – локальный минимум. Если меньше, то вершина пересечения – локальный максимум.
   

y

x

3

2

4
Рис. 4.. Прохождение сканирующий строки через вершину

Для ускорения работы алгоритма используется список активных ребер (САР). Этот список содержит те ребра многоугольника, которые пересекают сканирующую строку. При пересечении очередной сканирующей строки вершины многоугольника, из САР удаляются ребра, которые находятся выше, и добавляются концы, которые пересекает сканирующая строка. При работе алгоритма находятся пересечения сканирующей строки только с ребрами из САР.