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

Будем рассуждать подобно алгоритму Брезенхема для отрезков (с соответствующими поправками на 4-й октант) [17]. Из двух возможных пикселов в 4-м октанте (соответствующих вертикальному и диагональному смещениям, которые обозначаются аналогично прежним s и d, см. рис. 4.10) будем выбирать тот, расстояние от окружности до которого меньше.

Рис. 4.8. Расстояния до окружности.

Для того чтобы выбрать один из двух возможных пикселей, будем сравнивать расстояния от них до окружности: где расстояние меньше - тот пиксел и будет искомым. В примере на рис. 4.8 сравниваются расстояния от точек S(x_s, y_s) и D(x_d, y_d) до окружности с радиусом R. Из евклидовой метрики получаем:

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

Рис. 4.9. Приближенное сравнение расстояний.

Уменьшим два слагаемых на приблизительно одинаковые величины:

заменим на ,

заменим на

получим

Таким образом, приближенно

1. D ближе к окружности, чем S

1. S ближе к окружности, чем D

Рис. 4.10. Алгоритм Брезенхема для окружности

Пусть (x, y) - текущий пиксель. Обозначим

Тогда из двух возможных смещений d и s выберем.

1. , т.е. (x+1, y + 1) ближе к окружности, чем (x, y+1):

d: Переходим в (x + 1, y + 1) и придаем соответствующие приращения F, ΔF(s), ΔF(d):

F = F +ΔF(d); ΔF(s) = ΔF(s)+4; ΔF(d) = ΔF(d)+8.

1. , т.е. (x, y+1) ближе к окружности, чем (x + 1, y+1):

s: Переходим в (x, y + 1) и придаем соответствующие приращения F, ΔF(s), ΔF(d):

F = F +ΔF(s); ΔF(s) = ΔF(s)+4; ΔF(d) = ΔF(d)+4.

Если мы начинаем из (-R, 0), то начальные значения будут следующими:

Легко видеть, что в алгоритме все величины, связанные с F, кроме F начального, будут кратны 2. Но, если мы поделим все эти величины на 2 (в дальнейшем значения всех величин уже понимаются в этом смысле), то . Так как приращения F могут быть только целочисленными, то , где ; т.е. если отнять от всех значений, то знак F не изменится для всех T, кроме T = 0. Для того чтобы результат сравнения остался прежним, будем считать, что F = 0 теперь соответствует смещению s.

x = -r; y = 0; F = 1-r;ΔFs = 3;ΔFd = 5-2*r; while(x + y < 0){ plot8(x, y); if(F > 0) { // d: Диагональное смещение F += ΔFd; x++; y++; ΔFs += 2; ΔFd += 4; } else { // s: Вертикальное смещение F += ΔFs; y++; ΔFs += 2; ΔFd += 2; }}

Листинг 4.5. Алгоритм Брезенхема для окружности

Размерность вычислений этого алгоритма (т.е. отношение максимальных модулей значений величин, с которыми он оперирует к модулям исходных данных (в данном случае R)) равна 2.