Заполнение области

Алгоритм построчного сканирования

Рис. 3.21

Есть область, граница которой разложена в растр. Требуется: заполнить область внутри. Пусть внутри задана точка “boundary” — значение граничных . “old” – значение внутри области до заполнения. “new” – значение внутри области новое.

Объект заключается в прямоугольную оболочку и проверяется принадлежность объекту.

Проводится построчное сканирование. Находится со значением “boundary”, , следующий за ним и имеющий значение “old” меняется на “new” и так до тех пор, пока не будет встречен еще один со значением “boundary”. После этого осуществляется переход на следующую строку.

Рис. 3.22

Недостаток: Просматривается больше , чем необходимо.

Метод заполнения с затравкой

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

4-х связная обл. 8-связная обл.

Рис. 3.23

Алгоритм:

1) Поместить затравочный в стек.

2) Пока стек не пуст:

а) извлечь из стека;

б) присвоить требуемое значение;

в) для каждого из соседних 4-хсвязных проверить:

- является ли он граничным;

- не присвоено ли требуемое значение.

г) проигнорировать в любом из этих двух случаев.

иначе поместить в стек.

Пример:

Рис. 3.24

Стек

0 11 12 13

1 10 2

2 3

3 2 14

4 5 13 15 14 16

6 3 1 17

7 8 3 5 18 17 16

9 10

Заполнение линиями

Для заданной т. (x, y) определяется и заполняется максимальный отрезок, содержащий эту т. и лежащий внутри области. Потом в поисках еще не заполненных проверяются отрезки, лежащие выше и ниже. Если такие находятся, то функция рекурсивно вызывается дальше. Алгоритм эффективен и для областей с отверстиями.