08. Заполнение многоугольников. Алгоритмы заполнения по ребрам, с перегородкой, со списком ребер и флагом. - p1xelse/CG GitHub Wiki

Алгоритм заполнения по рёбрам

Введем соглашение:

Пиксель может иметь либо цвет фона, либо цвет закраски.

Считаем, что эти 2 цвета дополняют друг друга (инвертируют).

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

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

Последовательно обрабатывается каждое ребро многоугольника, причем ребра могут обрабатываться в произвольном порядке!

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

Пример обработки последовательно каждого ребра:

Если брать не выпуклый многоугольник, то цвет каждого пикселя может изменяться многократно! Если пиксель изменяет свой цвет четное кол-во раз, то получим фоновый цвет. Если нечетное => цвет закраски.

Оценка эффективности алгоритма (по времени)

1. Многократное считывание текущего цвета пикселя (столько раз, сколько изменяем цвет пикселя)
2. Конкретный пиксель будет изменять свой цвет столько раз, сколько ребер расположено левее этого пикселя.
3. Приходится обрабатывать не только те пиксели, которые находятся внутри многоугольника, но и пиксели за его пределами.

Алгоритм крайне неэффективный!

Алгоритм заполнения с перегородкой

Модификация алгоритма заполнения по ребрам.

Эффективность повышается за счет введения перегородки.

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

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

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

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

За счет введения перегородки сокращается кол-во раз смены пикселем цвета. Но все равно обрабатываются пиксели, расположенные вне многоугольника!

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

Если выбрать перегородку неправильно, можно еще сильнее уменьшить эффективность алгоритма.

Оценка эффективности алгоритма (по времени)

1. Многократное считывание текущего цвета пикселя (столько раз, сколько изменяем цвет пикселя)
2. Конкретный пиксель будет изменять свой цвет столько раз, сколько ребер расположено левее этого пикселя, если пересечение со сканирующей строкой находится левее перегородки. Если же пересечение расположено правее перегородки, то пиксель будет изменять свой цвет столько раз, сколько ребер расположено правее этого пикселя.
3. Приходится обрабатывать не только те пиксели, которые находятся внутри многоугольника, но и пиксели за его пределами.

Куров отметил, что для выпуклых многоугольников введение перегородки не дает существенного выигрыша.

Алгоритм заполнения со списком рёбер и флагом

В этом алгоритме хранится информация о ребрах в виде массива или списка.

Вводится в рассмотрение еще и флаг - признак расположения очередного пикселя внутри или вне многоугольника. Флаг = истина, если пиксель расположен внутри; флаг = ложь, если пиксель расположен вне многоугольника.

Этот алгоритм требует выполнения 2 шагов:

1. Очерчивание границ многоугольника
2. Заполнения многоугольника

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

Должен быть задан цвет заполнения.

В этом алгоритме точка пересечения определяется не геометрически, а графически - анализируя цвет очередного пикселя!

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

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

На рисунке изображён экстремальный случай в котором использование оболочки мало эффективно.

Оценка эффективности по времени

Критерии быстродействия для алгоритмов заполнения:

1. Кол-во изменений цвета каждого пикселя
2. Кол-во считываний цвета каждого пикселя
3. Кол-во обрабатываемых пикселей (обрабатываем пиксели вне заполняемой области или нет).

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

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

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

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

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