Заливка по ребрам

Заливка по ребрам.

Смысл данного способа заключается в следующем.

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

- цвет закраски точек области;

- цвет фона.

В исходном состоянии признак цветности  всех точек соответствует значению «фон». При каждом обращении к точке ее признак цветности меняется на противоположный.

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

На Рис. 4.2‑1 приведен пример закраски  многоугольника рассматриваемым способом.

Разновидностью данного способа является заливка с перегородкой.

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

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

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

Рис. 4.2‑1

Способ поясняется ниже приведенным рисунком (Рис. 4.2‑2).

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

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

Рис. 4.2‑2

Cписок активных ребер.

Рассмотрим понятия списка активных ребер на конкретном примере.

На Рис. 4.2‑3 приведен многоугольник в пространстве, которое включает десять растровых линий. В Табл. 4.2‑1 приведен изменяющийся в соответствии с номером текущей растровой строки список активных ребер заданного многоугольника. В полном списке ребер заданного многоугольника ребра упорядочены по координате «Y» их верхнего конца. Если несколько ребер  начинаются на одной и той же координате «Y», то они располагаются в соответствии c координаты «Y»  их нижнего конца. Начало каждого списка для каждой растровой линии отмечается на общем множестве ребер буквой «н», а конец – буквой «к».

Перечень активных ребер можно представить в виде односвязного списка с групповой сортировкой. В этом случае используется несколько групп по количеству растровых строк. В каждую группу включаются ребра,  верхняя точка которых начинается в соответствующей растровой строке. В группе ребра сортируются по координате X. Каждому ребру в группе соответствует одна запись, которая может включать:

- Dy – высота ребра;

- x_п - координата X пересечения ребра с соответствующей растровой линией;

- Dx – величина изменения X для данного ребра при переходе к очередной растровой линии;

- Aс – адрес следующей записи  в группе линией.

Рис. 4.2‑3

Список активных ребер для очередной растровой линии представляет собой остаток списка активных ребер, использовавшийся для предыдущей растровой линии,  увеличенный на группу ребер, соответствующую очередной растровой линии. При переходе к очередной растровой линии в записях активных ребер изменяется  Dy на «-1», а поле x_п изменяется на значение, равное содержимому поля Dx. Кроме того, при переходе к очередной растровой линии из списка активных ребер удаляются ребра,

                                                                                                Табл. 4.2‑1

в записи которых поле «y» после очередной модификации обнулилось.