Вопросы к 8 - p1xelse/CG GitHub Wiki

Изначально какого цвета могут быть пиксели?

Любого.

К группе каких алгоритмов относится алгоритм по рёбрам?

К растровым.

Какие проблемы возникают в растровых алгоритмах?

?. Обработка пикселей вне многоугольника (не проблема, - недостаток)

1. Проблема с горизонтальными рёбрами (сопутствует - как решать?)

2. Два раза учитываются экстремумы многоугольника, а если не экстремальная вершина то единожды

Что делать с горизонтальными рёбрами?

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

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

Растровая развертка – это генерация полного изображения (в данном случае – заполненного многоугольника) на основе информации о ребрах и вершинах.

Какая основная идея растровых алгоритмов?

Идея заключается в том, что мы имеем какие-то данные о многоугольнике и заполняем его, для этого нужно понять, расположен очередной пиксел внутри или снаружи.

Где меняется принадлежность пикселей (внутри он или вне).

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

Исходный цвет пикселя обязан быть фоновым у всех пикселей или они могут иметь разные цвета?

Цвет может произвольным. Тут важна только проверка: равен цвету закраски или не равен.

Для чего вводим перегородку?

Чтобы минимизировать количество проверяемых пикселов.

Какая характеристика улучшается за счет перегородки?

Уменьшается время.

Перегородка позволяет не анализировать все внешние пиксели?

Если область является невыпуклой или если есть отверстия, то анализируются лишние пиксели.

В чем отличие алгоритма с флагом от других?

Каждый пиксел обрабатывается 1 раз. Изначально границы должны быть обязательно очерчены. И данный алгоритм отличается способом нахождения точек пересечения.

Справится ли алгоритм с флагом, если нужно заполнить круг?

Да, справится.

Как находятся точки пересечения в алгоритме с флагом?

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

Является ли алгоритм с флагом быстрым?

Да, он быстрый, т.к. пиксели обрабатываются только 1 раз.

issue дополнение -> затравка не хуже (Куров упоминал)

Анализируются ли лишние пиксели в алгоритме с флагом?

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

По мимо закраски, какие есть ещё трудоёмкие операции?

Считывание цвета пикселя.

Как ищем пересечение?

Графически (определяем цвет пикселей грани многоугольника).