Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Алгоритм №2. Алгоритм Брезенхема

Рассмотренный выше алгоритм неудобен тем, что в общем случае нам приходится использовать вещественные переменные и операцию деления, что отрицательно сказывается на его быстродействии. Однако можно разработать такой алгоритм генерации отрезков, в котором будет использоваться только целочисленная арифметика, и не будет операций деления и умножения. Быстродействие такого алгоритма также возрастет. Данный алгоритм получил название «алгоритм Брезенхема» по фамилии его автора.

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

Начнем рисовать отрезок с точки А( ). В цикле будем задавать приращение 1 для переменной и будем оставлять либо неизменным, либо также увеличивать на 1. При этом последний выбор будем осуществлять так, чтобы новая точка сетки ( ) располагалась как можно ближе к прямой линии, проходящей через точки А и B рис. 1.3.

С

Рис. 1.3. Пример отрезка.

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

Введем переменную d для обозначения этого расстояния. Потребуем, чтобы .

Последнее неравенство обеспечивает условие для определения необходимости давать приращение переменной .

Теперь можно написать первый вариант реализации алгоритма нахождения координат точек между A и В:

1. Установим значения для переменных d и t: , .

2. Подсветим пиксель с координатами ( ).

3. Увеличим d на величину t, а на 1 (-1).

4. Если , то увеличим на 1, и вычтем 1 из d.

5. Будем повторять пункты 2-4, пока не нарисуем весь отрезок.

Отклонение, вначале устанавливается равным нулю и изменяется на каждом шаге. Поскольку оно показывает, насколько левее точной прямой линии лежит вычисленная точка, то значение d увеличивается на значение t, если y увеличивается на 1 и x остается без изменения. Это условие не выполняется, если значение d превышает 0,5. В этот момент нужно увеличить значение x на 1. Соответственно, и отклонение d должно быть уменьшено на единицу.

Теперь посмотрим, как можно избавиться от вещественных значений переменных t и d и постоянной 0,5.

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

где числитель и знаменатель представляют собой целые числа.

Величина d вычисляется как конечная сумма элементов, каждый из которых равен либо t, либо -1. Поэтому d также можно записать в виде частного со знаменателем равным .

Значит, можно перейти к целочисленным переменным t и d, путем умножения на значение знаменателя. Также просто избавиться от константы 0,5. Для этого нужно дополнительно умножить значение знаменателя на 2. Эта операция может быть заменена простым поразрядным сдвигом на 1 бит влево. Таким образом , где .

Напишем новый вариант реализации нашего алгоритма.

1. Установим значения для переменных d, t и : , , .

2. Подсветим пиксель с координатами ( ).

3. Увеличим d на величину t, а на 1.

4. Если , то увеличим на 1, и вычтем из d.

5. Будем повторять пункты 2-4, пока не нарисуем весь отрезок.

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

1. Отсортируем вершины А и В так, чтобы выполнялось условие .

2. Рассчитаем значения , и .

3. Если , то установим значение , иначе: , и изменим знак у на противоположный.

4. Установим . Если , то установим , . Иначе , . (операцию умножения на 2 везде заменяем поразрядным сдвигом влево на 1 бит).

5. Если , то перейти к пункту 6, иначе к пункту 11.

6. Подсветим пиксель с координатами ( ).

7. Увеличим на 1, а на величину .

8. Если , то увеличить на величину , и вычесть
величину из .

9. Повторять пункты 6-8, пока не нарисуем весь отрезок.

10. Завершить выполнение алгоритма.

11. Подсветим пиксель с координатами ( ).

12. Увеличим на 1, а на величину .

13. Если , то увеличить на 1, и вычесть
величину из .

14. Повторять пункты 6-8, пока не нарисуем весь отрезок.

15. Завершить выполнение алгоритма.

 

Задания к лабораторной работе №1

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

Все задания к лабораторной работе №1 необходимо выполнять, используя псевдопиксель, в виде закрашенного сплошным цветом квадрата размером n х n пикселей. Для выполнения заданий необходимо в первую очередь реализовать соответствующие алгоритмы генерации отрезков на используемом языке программирования. Затем, используя эти алгоритмы, выполнить соответствующий вариант задания.

При выполнении вариантов заданий ЗАПРЕЩАЕТСЯ пользоваться встроенными функциями рисования отрезков!

 

Вариант №1.

Нарисовать наибольший равносторонний треугольник, который поместится в области вывода. Одна из сторон треугольника должна идти вдоль нижней границы области вывода рис. 1.4. Боковые стороны необходимо нарисовать красными линиями, используя алгоритм Брезенхема. Основание нарисовать зеленой линией алгоритмом несимметричного ЦДА. Размер псевдопикселя для всех отрезков составляет 20х20 пикселей.


Рис. 1.4. Наибольший равносторонний треугольник.

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

 

Вариант №2.

Нарисовать наибольший правильный шестиугольник, который поместится в области вывода и построить все его диагонали рис. 1.5. Стороны шестиугольника необходимо нарисовать оранжевым цветом, используя алгоритм несимметричный ЦДА и псевдопиксель размером 20х20 пикселей. Диагонали изобразить тремя различными цветами (красным зеленым и синим) алгоритмом Брезенхема псевдопикселями размером 10х10 пикселей.


Рис. 1.5. Наибольший шестиугольник.

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

 

Вариант №3.

Нарисовать наибольший прямоугольник с соотношением сторон 2/3, который поместится в области вывода и построить все его диагонали рис. 1.6. Прямоугольник расположить по центру экрана. Короткие стороны необходимо расположить параллельно горизонтальной стороне экрана. Прямоугольник необходимо нарисовать красным цветом, используя алгоритм несимметричный ЦДА и псевдопиксель размером 20х20 пикселей. Диагонали изобразить двумя различными цветами (зеленым и синим) алгоритмом Брезенхема псевдопикселями размером 10х10 пикселей.


Рис. 1.6. Наибольший прямоугольник с соотношением сторон 2/3.

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

 

Вариант №4.

Нарисовать наибольшую пятиконечную звезду, которая поместится в области вывода и пятиугольник внутри нее рис. 1.7. Звезду необходимо нарисовать красным цветом, используя алгоритм Брезенхема и псевдопиксель размером 20х20 пикселей. Пятиугольник нарисовать синим цветом алгоритмом несимметричный ЦДА псевдопикселями размером 10х10 пикселей.

 

Рис. 1.7. Наибольшая пятиконечная звезда и пятиугольник.

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

 

Вариант №5.

Нарисовать наибольшую шестилучевую звезду, которая поместится в области вывода рис. 1.8. Стороны верхнего треугольника необходимо нарисовать зеленым цветом, используя алгоритм несимметричный ЦДА и псевдопиксель размером 10х10 пикселей. Стороны нижнего треугольника необходимо нарисовать красным цветом, используя алгоритм Брезенхема и псевдопиксель размером 20х20 пикселей.


Рис. 1.8. Наибольшая шестилучевая звезда.

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

 

Вариант №6.

Нарисовать зеленым цветом наибольшее изображение октаэдра, которое поместится в области вывода рис. 1.9. Стороны октаэдра наиболее близкие к наблюдателю (жирные линии) нарисовать, используя алгоритм несимметричный ЦДА и псевдопиксель размером 20х20 пикселей. Стороны дальние необходимо нарисовать, используя алгоритм Брезенхема и псевдопиксель размером 10х10 пикселей.


Рис. 1.9. Наибольший октаэдр.

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

 

Вариант №7.

Нарисовать красным цветом наибольшее изображение куба, которое поместится в области вывода рис. 1.10. Ребра куба наиболее близкие к наблюдателю (жирные линии) нарисовать, используя алгоритм Брезенхема и псевдопиксель размером 20х20 пикселей. Стороны дальние необходимо нарисовать, используя алгоритм несимметричный ЦДА и псевдопиксель размером 10х10 пикселей.

Рис. 1.10. Наибольший куб.

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

 

Вариант №8.

На базе алгоритма несимметричный ЦДА разработать алгоритм рисования пунктирной линии. Пунктирная линия состоит из отрезков, разделенных промежутками. Длина отрезка не может быть больше
10 псевдопикселей. Длина промежутка составляет половину длины отрезка. Линия начинается и заканчивается отрезком. Все отрезки и промежутки должны иметь примерно одинаковую длину. Используя алгоритм Брезенхема и псевдопиксель 20х20, нарисовать зеленым цветом наибольший прямоугольник, который поместится в области вывода. Диагонали прямоугольника провести пунктирной линией красного цвета, используя псевдопиксель 5х5 рис. 1.11.

Рис. 1.11. Наибольший прямоугольник с диагоналями.

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

 

Вариант №9.

Нарисовать красным цветом наибольшее изображение икосаэдра, которое поместится в области вывода рис. 1.12. Ребра икосаэдра, наиболее близкие к наблюдателю, (жирные линии) нарисовать, используя алгоритм несимметричный ЦДА и псевдопиксель размером 20х20 пикселей. Ребра дальние необходимо нарисовать, используя алгоритм Брезенхема и псевдопиксель размером 10х10 пикселей.

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

 

Рис. 1.12. Наибольший икосаэдр.

 

 


Лабораторная работа №2. Геометрические преобразования на плоскости

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

Задача: Используя матричное представление геометрических преобразований на плоскости, разработать программу анимации плоских фигур.

Результат: программа анимации заданных плоских фигур. Отчет в печатном виде, оформленный в соответствии с приложением 1.

 

Способы представления геометрических преобразований на плоскости

Рассмотрим следующую систему уравнений:

Эти уравнения можно интерпретировать двояким образом:

1. Все точки на плоскости ху перемещаются вправо на расстоя­ние а рис. 2.1.а.

2. Координатные оси х и у перемещаются влево на расстояние а рис. 2.1.б.

 

       
 
   


Рис. 2.1. а) — перенос точек; б) — перенос системы координат

 

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

Пусть необходимо повернуть точку вокруг начала ко­ординат О на угол. Изображение новой точки на рис. 2.2 обоз­начим через .

Рис. 2.2. Поворот вокруг точки О на угол φ

 

Уравнения, задающие поворот точек на плоскости относительно начала координат:

Эта система уравнений описывает поворот вокруг точки О — начала системы координат. Но часто это не то, что нам нужно. Если требуется выполнить поворот относительно заданной точки , то в этих уравнениях можно заменить x на , y на , x’ на, y’ – на :

 

Система уравнений:

описывает изменение масштаба относительно точки О – начала системы координат. При этом координата x всех точек плоскости изменяется в a раз, а координата y – в b раз. Если a = b то искажения изображения объектов не происходит, и тогда говорят о равномерном масштабировании. В противном случае, изображение объектов искажается, и такое преобразование называется неравномерным масштабированием.

Если требуется выполнить масштабирование относительно заданной точки (x0, y0), то в этих уравнениях также можно заменить x на , y на , x’ на , y’ – на :

Система уравнений поворота точки относительно начала координат может быть записана в виде одного матричного уравнения:

Можно записать в матричной форме и систему уравнений для масштабирования:

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

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...