8.4.2. НЕРЕКУРСИВНАЯ ПРОЦЕДУРА ЗАПОЛНЕНИЯ ПО КРИТЕРИЮ СВЯЗНОСТИ

Вместо того чтобы возлагать весь контроль за процессом обхода на систему, управляющую вызовом подпрограммы, мы можем сами заняться этим, причем с большей эффективностью. При работе с растровыми графическими устройствами особенно удобно пользоваться ГСС. В простейшем варианте алгоритм начинает работу с затравочного пиксела и «перемещается» влево до тех пор, пока не будет обнаружен пиксел контура. После этого осуществляется просмотр вправо снова вплоть до контура. Далее заполняется следующая строка, и процесс продолжается до тех пор, пока не будет достигнута самая нижняя часть контура. Эта процедура повторяется для той части области, которая расположена выше начального пиксела. Процесс достаточно прост, однако нетрудно убедиться в том, что он обеспечивает правильное заполнение контура лишь при условии выпуклости соответствующей области. Данную процедуру можно усовершенствовать, чтобы она обеспечивала заполнение невыпуклых областей — необходимо предусмотреть стек, в котором будут храниться пикселы, расположенные в окрестностях максимумов и минимумов контура. Впоследствии эти пикселы выталкиваются из стека и используются в качестве затравочных. Так, в примере, приведенном на рис. 8.7, пикселы будут помещены в стек при заполнении заштрихованной части области. Пикселы и Е будут помещены в стек позже — при обходе незаштрихованной части области. Хотя сама по себе эта идея очень проста, ее правильная реализация требует определенной тщательности.

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

Рис. 8.7. Заполнение невыпуклой области по критерию связности.

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