Заливка с затравкой

Заливка с затравкой.

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

 При реализации рассматриваемого способа возможно использование или восьмисвязного, или четырехсвязного соседства, которые поясняются ниже приведенным рисунком (Рис. 4.3‑1).

Рис. 4.3‑1

Процесс закраски  области данном способом иллюстрируется на ниже приведенном рисунке (Рис. 4.3‑2). На рисунке приведена траектория обработки точек с указанием адресов стека, в которые помещаются их координаты. Закрашенная точка соответствует точке-затравке.

Рекомендуемые материалы

Рис. 4.3‑2

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

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

Для уменьшения требуемого объема памяти для организации стека используется модификация этого способа, которая называется «заливка  с затравкой с запоминанием соседних групп».

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

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

Если верхний сосед не закрашен и нет признака верхней группы, то адрес этого соседа записывается в стек и устанавливается признак верхней группы. Если верхний сосед не закрашен, но есть признак верхней группы, то его адрес в стек не записывается.

 Если нижний сосед не закрашен и нет признака нижней группы, то адрес этого соседа записывается в стек и устанавливается признак нижней группы. Если нижний сосед не закрашен, но есть признак верхней группы, то его адрес в стек не записывается.

Если левый сосед не закрашен, то он закрашивается и его адрес запоминается как адрес левого соседа.

Лекция "Поступление и превращение азота" также может быть Вам полезна.

Рис. 4.3‑3

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

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

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

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