double arrow

Алгоритм №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. Завершить выполнение алгоритма.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: