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

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

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

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

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

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

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

Плюс алгоритма - сортировки не нужны. Можно ребра в произвольном порядке обрабатывать.

. . .

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

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

Алгоритм неэффективный, но простой! 3 Курова из 10.

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

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

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

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

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

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

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

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

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

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

Храним информацию о ребрах в виде массива или списка.
Флаг - признак расположения пикселя внутри или вне многоугольника.

• Флаг = истина, если пиксель расположен внутри
• Флаг = ложь, если пиксель расположен вне

Алгоритм можно разделить на 2 шага выполнения:
1. Очерчивание границ многоугольника.
2. Заполнение

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

Псевдокод

1. Очерчивание границ многоугольника.
2. Цикл по всем строкам, пересекающим ребра многоугольника.
   2.1. Флаг = ложь
   2.2. Цикл по всем пикселям от х до xmax
        2.2.1. Если цвет (x, y) = цвет границы, то инвертировать значение флага
        2.2.2. Если флаг истина, то цвет (x, y) = цвет закраски, иначе цвет (х, у) = цвет фона
   2.3. Конец цикла по х.
3. Конец цикла по у.

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

• Цвет каждого пикселя анализируем и изменяем всего 1 раз!
• Количество обрабатываемых пикселей - много. Обрабатываются пиксели лежащие за пределами многоугольника

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

Но это будет невсегда эффективно. Пример:

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

Акак найти точку пересечения (по Курову)?

Хороший вариант - использовать рекуретное соотношение x = x + dx, где dx - котангенс угла

Следующий вопрос: 09. Алгоритм заполнения с затравкой, простой алгоритм заполнения с затравкой.

Предыдущий вопрос: 07. Растровая развертка сплошных областей. Алгоритм с упорядоченным списком ребер.