- •0.2 Генерация векторов
- •0.2.1 Цифровой дифференциальный анализатор
- •0.2.2 Алгоритм Брезенхема
- •0.2.3 Улучшение качества аппроксимации векторов
- •Модифицированный алгоритм Брезенхема
- •0.2.4 Улучшение качества изображения фильтрацией
- •0.3 Генерация окружности
- •0.3.1 Алгоритм Брезенхема
- •Для варианта 1:
- •Для вариантов 5 и 6:
- •Для вариантов 2 и 3:
- •Для варианта 7:
- •0.4 Заполнение многоугольника
- •0.4.1 Построчное заполнение
- •0.4.2 Сортировка методом распределяющего подсчета
- •0.5 Заливка области с затравкой
- •0.5.1 Простой алгоритм заливки
- •0.5.2 Построчный алгоритм заливки с затравкой
0.5.2 Построчный алгоритм заливки с затравкой
Использует пространственную когерентность:
· пикселы в строке меняются только на границах;
· при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел.
Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пиксела [], что приводит к существенному уменьшению размера стека.
Последовательность работы алгоритма для гранично определенной области следующая:
Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.
Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ, соответственно.
Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.
То же самое проделывается для строки выше закрашиваемой.
В Приложении 6 приведена процедура V_FAST, реализующая рассмотренный алгоритм. За счет несложной модификации служебных процедур запроса и записи строк изображения, данная процедура может заливать изображение, размещенное в файле.