Алгоритмы заполнение многоугольников методом САР

Цель работы: изучение алгоритма с упорядоченным списком ребер.

Простейший способ закраски многоугольника состоит в проверке принадлежности каждой точки этому многоугольнику. Для организации и управления списком активных ребер (САР) можно использовать ряд методов. Сначала отрезки изображения сортируются по наибольшей координате у. В одном из простых методов такой сортировки используются два перемещающихся указателя в отсортированном списке. Указатель начала используется для обозначения начала списка активных ребер, а указатель конца – для обозначения конца этого списка. На рисунке 5.1 представлена сцена из нескольких отрезков с тремя характерными сканирующими строками. Указатель начала в исходном положении устанавливается на начало этого списка, т.е. на отрезок ВС. Указатель конца установлен на тот последний отрезок в списке, который начинается выше рассматриваемой сканирующей строки, т. е. на отрезок BD. При сканировании изображения необходимо корректировать САР, при этом указатель конца передвигают вниз, чтобы включить в список новые отрезки, начинающиеся на текущей сканирующей строке или выше нее. В то же самое время указатель начала передвигают вниз, чтобы исключить отрезки, кончающиеся выше текущей сканирующей строки. Это изображено на рисунке 5.1 для сканирующих строк, помеченных цифрами 2 и 3.

Рисунок 5.1 – Сканирующая строка

Перед сканированием всем ребрам соответствует флаг в значении False. По мере увеличения значения y сканирующей строки ведется проверка условия

Y_imin <= Y_скан <= Y_imax,                                      (5.1)

где Y_imin, Y_imax, Y_скан – минимальная и максимальная координата i-го отрезка и координата сканирующей строки.

Если данное условие выполняется, то флагу соответствующего отрезка присваивается значение True и данный отрезок обрабатывается.

Практическое задание

Разработать программу, закрашивающую объект № 1 методом САР.

Содержание отчета: блок-схема данной программы; краткие ответы на вопросы, приведенные в таблице 5.1; распечатка листа Excel с результатами.

Таблица 5.1 – Вопросы для защиты

Алгоритмы заполнение многоугольников методом заливки

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

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

Используя стек, можно разработать простой алгоритм заполнения гранично-определенной области. Стек (англ. stack – стопка) – абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in – first out, «последним пришёл – первым вышел»). Когда новые значения добавляются или помещаются в стек, все остальные значения опускаются вниз на один уровень. Когда значения удаляются или извлекаются из стека, остальные значения всплывают или поднимаются вверх на один уровень. Со стеком возможны три операции: добавление элемента (push), удаление элемента (pop) и чтение головного элемента (peek).

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

Затравка(х, у) выдает затравочный пиксель

Пиксел(х, у) = Затравка(х, у)       инициализируем стек

Push Пиксел(х, у)

while (стек не пуст)

Pop Пиксел(х, у) извлекаем пиксел из стека

if Пиксел(х, у) < > Нов_значение then

Пиксел(х, у) = Нов_значение

end if

проверим, надо ли помещать соседние пикселы в стек

if (Пиксел(х + 1, у) < > Нов_значение and Пиксел(х + 1, у) < > Гран_значение) then

Push Пиксел (х + 1, у)

if (Пиксел(х, у + 1) < > Нов_значение and Пиксел(х, у + 1) < > Гран_значение) then

Push Пиксел (х, у + 1)

if (Пиксел(х – 1, у) < > Нов_значение and Пиксел(х – 1, у) < > Гран_значение) then

Push Пиксел (х - 1, у)

if (Пиксел(х, у – 1) < > Нов_значение and Пиксел(х, у – 1) < > Гран_значение) then

Push Пиксел (х, у – 1) end if

end while.

В алгоритме проверяются и помещаются в стек 4-связные пиксели, начиная с правого от текущего пикселя. Направление обхода пикселей – против часовой стрелки.

Практическое задание

Составить алгоритм и программу для отображения объекта № 2 методом заливки.

Содержание отчета: блок-схема данной программы; краткие ответы на вопросы, приведенные в таблице 6.1; распечатка листа Excel с результатами.

Таблица 6.1 – Вопросы для защиты