Рис.8.3. внутренне - определённые 4- и 8- связные области
На рис.8.3,бпоказано, что для 8-связной области, у которой две подобласти соприкасаются углами, граница 4-связна, а граница 4-связной области 8-связна.
Далее речь в основном пойдет об алгоритмах для 4-связных областей, однако их можно легко переделать для 8-связных областей, если заполнение проводить не в 4, а в 8 направлениях.
С использованием связности областей и стека можно построить простые алгоритмы закраски как внутренне, так и гранично-определенной области.
Стек — это массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Когда новые значения добавляются или помещаются в стек, все остальные значения опускаются вниз на один уровень. Когда значения извлекаются из стека, остальные значения поднимаются вверх на один уровень. Такой стек называется стеком прямого действия или стеком с дисциплиной обслуживания «первым пришел, последним обслужен» (FILO).
Простой алгоритм заполнения с затравкой можно представить в следующем виде:
Простой алгоритм заливки
Заливка выполняется следующим образом:
1)· определяется является ли пиксел граничным или уже закрашенным,
2)· если нет, то пиксел перекрашивается, затем проверяются и, если надо, перекрашиваются 4 соседних пиксела.
Понятно, что несмотря на простоту и изящество программы, рекурсивная реализация проигрывает итеративной в том, что требуется много памяти для упрятывания вложенных вызовов.
Итеративный алгоритм закраски 4-х связной гранично-определенной области.
Логика работы алгоритма следующая:
1 Определить координаты затравки
2Поместить координаты затравки в стек
3 Пока стек не пуст извлечь координаты пиксела из стека.
4Перекрасить пиксел.
5 Для всех четырех соседних пикселов проверить является ли он граничным или уже перекрашен.
6Если нет, то занести его координаты в стек.
На рис. 84 а) показан выбранный порядок перебора соседних пикселов, а на рис. б) соответствующий ему порядок закраски простой гранично-определенной области.
a) Порядок перебора соседних пикселов б) Порядок заливки области
Рисунок 8.4Заливка 4-х связной области итеративным алгоритмом
Такой алгоритм экономнее, так как в стек надо пересылать только координаты.
Рассмотренный алгоритм легко модифицировать для работы с 8-ми связными гранично-определенными областями или же для работы с внутренне-определенными.
Очевидный недостаток алгоритмов непосредственно использующих связность закрашиваемой области - большие затраты памяти на стек, так как на каждый закрашенный пиксел в стеке по максимуму будет занесена информация о еще трех соседних. Кроме того, информация о некоторых пикселах может записываться в стек многократно. Это приведет не только к перерасходу памяти, но и потере быстродействия за счет многократной раскраски одного и того же пиксела. Значительно более экономен далее рассмотренный построчный алгоритм заливки.
Построчный алгоритм заливки с затравкой использует пространственную когерентность:
-· пикселы в строке меняются только на границах;
-· при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел.
Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пиксела, что приводит к существенному уменьшению размера стека.
Последовательность работы алгоритма для гранично-определенной области следующая:
1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.
2. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ, соответственно.
3. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находят крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.
4. То же самое проделывается для строки выше закрашиваемой.