Заполнение области. Алгоритм построчного сканирования, алгоритм заполнения с затравкой. Заполнение линиями.

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

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

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

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

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

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

Алгоритм:

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

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

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

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

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

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

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

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

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

Пример:

Стек

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) определяется и заполняется максимальный отрезок, содержащий эту т. и лежащий внутри области. Потом в поисках еще не заполненных проверяются отрезки, лежащие выше и ниже. Если такие находятся, то функция рекурсивно вызывается дальше. Алгоритм эффективен и для областей с отверстиями.

9. Растровая развёртка многоуг-в (метод использования когерентности сканируемых строк).

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

Дата добавления: 2015-07-14