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

Каждый пиксел имеет 8 соседей N, NE, NW, W, E, SE, SW, S. Предположим, что во время построения отрезка, мы поставили некоторую точку M (x, y). Тогда следующим мы поставим либо E либо NE пиксел. Как определить, какой из двух вариантов наиболее точно будет продолжать линию? Это можно определить с помощью срединной точки (рис.1) Если отрезок проходит выше срединной точки, то следующим ставится NE пиксел, иначе, если отрезок проходит ниже срединной точки, то ставится E пиксел. Сделать это математически поможет формула отрезка в неявно заданном виде:

F(x, y)=0 – значит точка (x, y) лежит на отрезке

F(x, y)< 0 – выше отрезка

F(x, y)> 0 – ниже отрезка

 

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

А значение функции F в этой точке

Если следующим поставленным пикселем будет E, тогда значение функции в новой срединной точке будет:

В случае NE:

Рассмотрим начальную точку (x1, y1):

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

Единственная неприятность – деление на 2 в первом d. Получившееся значение скорее всего будет вещественным и потребует использование вещественных операций. Однако от этого можно избавиться, использовав следующее преобразование:

Тогда все d становятся целыми

 

Для построения произвольного отрезка перед построением необходимо проверить угол наклона и провести соответствующую зеркальную симметрию:

 

Если 0< =x2-x1< =y2-y1 то меняем местами x и y координаты.

Если тангенс угла наклона меньше 0, то отражаем относительно оси ординат x=-x а затем, если это необходимо, меняем x и y координаты.

 

 

Некоторые дополнительные вопросы построения отрезка