4. Заполнение многоугольника. Алгоритм заполнения с затравкой.

Задача заполнения многоугольников решается в два этапа:

1. Сначала проводится операция отсечения многоугольника;

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

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

Рассмотрим, каким образом можно заполнить многоугольник, задаваемый замкнутой ломаной линией без самопересечений.

Простейший способ закраски многоугольника состоит в проверки принадлежности каждой точки этому многоугольнику. Более эффективные алгоритмы используют тот факт, что соседние пискелы, вероятно, имеют одинаковые характеристики (кроме пикселов граничных ребер). Это свойство называется пространственной когерентностью.

В случае с многоугольником когерентность пикселей определяется вдоль сканирующей строки. Сканирующие строки обычно изменяются от «верха» многоугольника до его «низа». Характеристики пикселов изменяются только, где ребро многоугольника пересекает строку. Эти пересечения делят сканирующую строку на области закрашенных и не закрашенных пикселов.

0.5.1 Простой алгоритм заливки

Заливка выполняется следующим образом:

 определяется является ли пиксел граничным или уже закрашенным,

 если нет, то пиксел перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пиксела.

Логика работы алгоритма следующая:

Поместить координаты затравки в стек

Пока стек не пуст

Извлечь координаты пиксела из стека.

Перекрасить пиксел.

Для всех четырех соседних пикселов проверить

является ли он граничным или уже перекрашен.

Если нет, то занести его координаты в стек.

0.5.2 Построчный алгоритм заливки с затравкой

Использует пространственную когерентность:

 пикселы в строке меняются только на границах;

 при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел.

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

Последовательность работы алгоритма для гранично определенной области следующая:

1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.

2. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ, соответственно.

3. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.

4. То же самое проделывается для строки выше закрашиваемой.

5. Отсечение отрезков. Двумерный алгоритм Коэна-Сазерленда. Другие методы отсечения отрезков: двумерный алгоритм Кируса-Бека, алгоритм Сазерлспда-Ходгмана, алгоритм отсечения многоугольника Вейлера-Азертона. Трехмерное отсечение отрезков.

Алгоритм отсечения многоугольника должен в результате отсечения давать один или несколько замкнутых многоугольников .