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

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

Рассмотрим работу алгоритма для первого октанта, где угловой коэффициент  лежит в диапазоне от 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-связные. Приведем более формальное изложение алгоритма, в котором предполагается существование затравочного пиксела и гранично-определенной области