Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
diplomnaya_rabota_5_Vosstanovlen.doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
4 Мб
Скачать
☆

2.4.5 Алгоритмы заливки

 

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

Виды заливок:

- простой алгоритм заливки с затравкой;

- построчный алгоритм заливки с затравкой.

 

По способу задания области заливки делятся на два типа:

1) Гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселев границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселев внутренней части области налагаются два условия - они должны быть отличны от кода пикселев границы и кода пикселя перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселями с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;

2) Внутренне-определенные, нарисованные одним определенным кодом пикселя. При заливке этот код заменяется на новый код закраски.

 По способам доступа к соседним пикселям области делятся на 4-х и 8-ми связные.

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

 В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пиксели области [20].

4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно. Так, область на рис.2.16.(а) мы можем заполнить любым алгоритмом, а область на рис.2.16. (б), состоящую из двух примыкающих 4-х связных областей можно заполнить только 8-ми связным алгоритмом.

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

Рисунок.2.16.– Связность областей и их границ

 

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

- в рекурсивной реализации;

- в итеративной реализации.

Алгоритм заливки в рекурсивной реализации гранично-определенной 4-х связной области выполняется в следующем порядке:

- определяется, является ли пиксель граничным или уже закрашенным;

- если нет, то пиксель перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пикселя.

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

Логика работы итеративного алгоритма заливки 4-х связной гранично-определенной области следующая:

1. Поместить координаты затравки в стек;

2. Если стек не пуст, извлечь из него координаты пикселя;

3. Перекрасить пиксель;

4. Для всех четырех соседних пикселев проверить, является ли он граничным или уже перекрашен;

5. Если нет, то занести его координаты в стек.

 

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

 

Рисунок 2.17. – Заливка 4-х связной области итеративным алгоритмом

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

Построчный алгоритм заливки.

Использует пространственную когерентность, при которой:

- пиксели в строке меняются только на границах;

- при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксель.

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

Последовательность работы алгоритма для гранично-определенной области следующая:

1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.

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

3. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.

4. То же самое проделывается для строки выше закрашиваемой [16].

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]