Алгоритм Мичнера для построения окружности

В данном алгоритме окружность строится во втором октанте из начальной точки (0, R) по часовой стрелке. Остальные части окружности достраиваются по алгоритму, описанному выше. Т.к. построение ведется во втором октанте, то имеется только две приоритетные точки, по которым можно продолжать построение: (x_i + 1, y_i) и (x_i + 1, y_i – 1). В данном алгоритме рассматриваются две погрешности и их сумма:

;

;

.

Если eⁱ > 0, то выбираем точку (x_i+1, y_i-1), иначе - точку (x_i+1, y_i).

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

для точки (x_i+1, y_i) - eⁱ⁺¹= eⁱ+4*x_i+6;

для точки (x_i+1, y_i-1) - eⁱ⁺¹= eⁱ+4*(x_i-y_i)+10;

для начальной точки (R,0) e¹=3-2*R.

Задание на лабораторную работу № 3
"Алгоритмы генерации окружности"

1. Центр окружности находится в середине экрана (как вариант, координаты центра окружности вводятся вручную).

2. На экране изображается сетка псевдопикселов.

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

4. Постройте другим цветом "настоящую" окружность.

5. Сравните полученные результаты. Сделайте выводы.

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

7. Назовите критерий выбора следующей точки в алгоритме Брезенхема.

8. Сравните два алгоритма.

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

Цель: Изучить алгоритмы построчного заполнения
многоугольников

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

Следующий шаг – прямоугольная оболочка – наименьший прямоугольник, содержащий данную фигуру (рис. 4.1 а). Но в случае, изображенном на рис. 4.1 б) эффективность алгоритма тоже оставляет желать лучшего.

Рис. 4.1. Прямоугольная оболочка

Более эффективный метод заполнения состоит в следующем.

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

Рис. 4.2. Простейший метод заполнения многоугольника

Для строки Y = 2:

X < 1 – цвет закраски – фон;

1 ≤ X ≤ 8 – цвет закраски – цвет многоугольника;

X > 8 – цвет закраски – фон.

Для строки Y = 4:

X < 1 - цвет закраски – фон;

1 ≤ X ≤ 3 – цвет закраски – цвет многоугольника;

3 ≤ X < 5 – цвет закраски – фон;

5 ≤ X ≤ 8 – цвет закраски – цвет многоугольника;

X > 8 – цвет закраски – фон.

Для определения интенсивности и цвета пикселов рассматриваются пары отсортированных точек пересечения по возрастанию X.

Для строки Y = 2: 1, 8.

Для строки 4: 1, 3, 5, 8 и закрашивается область между парами, остальное – фон.

Трудности возникают при пересечении вершин (рис. 4.3).

Рис. 4.3. Пересечение вершин сканирующими строками

Для строки Y = 2 точки пересечения: 2, 2, 5, т.е. нечетное количество пересечений и, следовательно, необходимо учитывать только одну точку пересечения с ребрами (а именно 2, 5).

Однако, при использовании этого критерия, для строки Y = 6 получаем точки пересечения: 1, 4, 7, т.е. опять нечетное количество пересечений и, в данном случае, необходимо учитывать точку (1, 6) дважды – (1, 1, 4, 7).

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

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

Исходный многоугольник изображен на рис. 4.4 а). Ребро P1 – P2 параллельно оси абсцисс и, следовательно, его не учитываем. Обработке ребра
P2 – P3 соответствует рис. 4.4 б), ребра P3 – P4 – рис. 4.4 в), ребра P4 – P5 – рис. 4.4 г) и, наконец, ребра P5 – P1 – рис 4.4 д). Причем ребра многоугольника можно обрабатывать в произвольном порядке. Недостатком этого метода является многократная обработка "правых" пикселов.

Задание на лабораторную работу № 4
"Алгоритмы построчного заполнения многоугольников"

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

2. Используя один из алгоритмов закрасить многоугольник.

3. При этом при построчном заполнении – ввести программную задержку после прохождения очередной сканирующей строки, а при заполнении по ребрам ввести задержку после обработки каждого ребра.

4. Сравните алгоритмы.

Рис. 4.4. Пример алгоритма заполнения по ребрам

Не нашли, что искали? Воспользуйтесь поиском по сайту: