Простой алгоритм заполнения с затравкой
В алгоритмах заполнения с затравкой предполагается, что известен хотя бы один пиксел из внутренней области многоугольника. Алгоритм пытается найти и закрасить все другие пикселы, принадлежащие внутренней области. Области могут быть либо внутренне-, либо гранично-определенными. Если область относится к внутренне-определенным, то все пикселы, принадлежащие внутренней части, имеют один и тот же цвет или интенсивность, а все пикселы, внешние по отношению к области, имеют другой цвет. Это продемонстрировано на рис. 2.12. Если область относится к гранично-определенным, то все пикселы на границе области имеют выделенное значение или цвет, как это показано на рис. 2.13. Ни один из пикселов из внутренней части такой области не может иметь это выделенное значение. Тем не менее пикселы, внешние по отношению к границе, также могут иметь граничное значение. Алгоритмы, заполняющие внутренне-определенные области, называются внутренне-заполняющими, а алгоритмы для гранично-определенных областей - гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие алгоритмы, однако соответствующие внутренне-заполняющие алгоритмы можно получить аналогичным образом.
Внутренне- или гранично-определенные области могут быть 4-или 8-связными. Если область 4-связная, то любого пиксела в области можно достичь с помощью комбинации движений только в 4 направлениях: налево, направо, вверх, вниз. Для 8-связной области пиксела можно достичь с помощью комбинации движений в двух горизонтальных, двух вертикальных и 4 диагональных направлениях (рис. 2.14).
Далее речь в основном пойдет об алгоритмах для 4-связных областей, однако их можно легко переделать для 8-связных областей, если заполнение проводить не в 4, а в 8 направлениях. Используя стек, можно разработать простой алгоритм заполнения гранично-определенной области. Стек - это просто массив или другая структура данных, в которую можно последовательно пометить значения и из которой их можно последовательно извлекать. Когда новые значения добавляются или помещаются в стек, все остальные значения опускаются вниз на один уровень. Когда значения удаляются или извлекаются из стека, остальные значения всплывают или поднимаются вверх на один уровень. Такой стек называется стеком прямого действия. Простой алгоритм заполнения с затравкой можно представить в следующем виде: Простой алгоритм заполнения с затравкой и стеком. Приведем более формальное изложение алгоритма, в котором предполагается существование затравочного пиксела и гранично-определенной области:
Пример 2.3. Алгоритм заполнения многоугольника с затравкой. В качестве примера применения алгоритма рассмотрим гранично-определенную область, содержащую дыру. Она изображена на рис. 2.15.
Вершины многоугольника заданы пикселами (1, 0), (7, 0), (8, 1), (8, 4), (6, 6), (1, 6), (0, 5) и (0, 1). Внутренняя дыра определяется пикселами (3, 2), (5, 2), (5, 3), (3, 3). Затравочный пиксел — (4, 4). Порядок заполнения указан на рисунке линией со стрелками. Числа в квадратике пиксела показывают позицию в стеке, занимаемую пикселом. Когда обработка доходит до пиксела (3, 1), все окружающие его 4-связные пикселы либо уже заполнены, либо являются граничными. Поэтому ни один из пикселов не помещается в стек. Глубина стека в этот момент равна 15. В стеке находятся пикселы (7, 1), (7, 2), (7, 3), (6, 5), (7, 4), (6, 5), (3, 1), (1, 2), (1, 3), (1, 4), (2, 5), (3, 5), (4, 5), (5, 4). После удаления из стека пиксела (7, 1) заполняется колонка (7, 1), (7, 2), (7, 3), (7, 4), при этом ни один новый пиксел в стек не добавляется. Для пиксела (7, 4) снова все 4-связные окружающие пикселы либо уже заполнены, либо являются граничными. Обращаясь к стеку, алгоритм извлекает пиксел (6, 5), его заполнение завершает заполнение всего многоугольника. Дальнейшая o6работка происходит без какого-либо заполнения, и когда стек становится пустым, алгоритм завершает работу.
|
