Метод Брезенхема для разложение отрезка в растр

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

Рассмотрим работу алгоритма для первого октанта, где угловой коэффициент лежит в диапазоне от 0 до 1.

Для первого октанта ошибка определяется вдоль вертикальной оси, обозначим ее через е. Нарастание ошибки на каждом единичном шаге, вдоль оси Х, зависит от величины углового коэффициента e_i+1 = e_i + m. Начальное значение ошибки, используемое для выбора положения второй точки отрезка - р1, (напомним, начальная и конечные точки отрезка лежат точно на сетке растра) равно угловому коэффициенту отрезка – m. Схема процесса растеризации приведена на рисунке 1 А), где узлы сетки соответствуют центам пикселей. Изменение второй координаты происходит только при е > = 0.5, величина ошибки при этом корректируется и определяется как e_i = e_i - 1. Из-за этого данный алгоритм иногда называют методом серединной точки. Изменение величины ошибки в ходе разложения отрезка показано на рис. 1 Б). Очевидно, что если сдвинуть график вниз на 0.5, то при выборе приращения, можно рассматривать не величину ошибки, а только ее знак. Так как ошибка в данном случае величина относительная (рассчитывается на основании предыдущего значения) то для изменения графика достаточно просто уменьшить начальное значение ошибки: e₀= e₀ – 0.5.

Алгоритм построения отрезка для первого октанта следующий:

На входе: координаты начальной (x1, y1) и конечной (x2, y2) точек отрезка.

·​ определить значение углового коэффициента m;

·​ вычислить начальное значение ошибки e₀, с учетом сдвига;

·​ в цикле от x1 до x2 выполняем:

§​ выводим пиксель;

§​ если ошибка больше или равна 0, то увеличиваем y на единицу и корректируем значение ошибки (уменьшаем на единицу);

§​ увеличиваем значение ошибки на величину углового коэффициента;

§​ приращиваем координату х на единицу;

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

34. Заполнения многоугольников: простой алгоритм заполнения с затравкой.

Используя стек, можно разработать простой алгоритм заполнения гранично-определенной области. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Когда новые значения добавляются или помещаются в стек, все остальные значения опускаются вниз на один уровень. Когда значения удаляются или извлекаются из стека, остальные значения всплывают или поднимаются вверх на один уровень. Такой стек на­зывается стеком прямого действия или стеком с дисциплиной обслуживания “первым пришел, последним обслужен” (LIFO). Простой алгоритм заполнения с затравкой можно представить в следующем виде:

Простой алгоритм заполнения с затравкой и стеком:

Поместить затравочный пиксел в стек

Пока стек не пуст

Извлечь пиксел из стека.

Присвоить пикселу требуемое значение.

Для каждого из соседних к текущему 4-связных пикселов проверить: является ли он граничным пикселом или не присвоено ли уже пикселу требуемое значение. Проигнорировать пиксел в любом из этих двух случаев. В противном случае поместить пиксел в стек.

Алгоритм можно модифицировать для 8-связных областей, если просматривать 8-связные пиксели, а не только 4-связные. Приведем более формальное изложение алгоритма, в котором предполагается существование затравочного пиксела и гранично-определенной области

35. Заполнения многоугольников: построчный алгоритм заполнения с затравкой.

Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.

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

В переменных Х_лев и Х_прав запоминаются крайний левый и крайний правый пикселы интервала.

В диапазоне Х_лев < = x < = X_прав проверяются строки, расположенные непосредственно над и под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.

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

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

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

Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.

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

В переменных Х_лев и Х_прав запоминаются крайний левый и крайний правый пикселы интервала.

В диапазоне Х_лев и Х_прав проверяются строки, расположенные непосредственно над и под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т.е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.

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