Алгоритм DDA (Digital Differential Analyzer)

Строит 8-связную линию

e₀=< 1 ; De=< 1

 

P₁=(1,0) ; P₂=(1,1)

 

В начальный момент

x=0;

y=0;

e=e₀;

Рис. 5. Алгоритм DDA.

 

В силу подобия треугольников, для того чтобы определить, какая из точек (P₁ или P₂) ближе, достаточно сравнить расстояния от точки пересечения P до P₁ и P₂, что равносильно сравнению e с 1/2.

 

Алгоритм:

 

while(x £ a)

{

plot(x,y);

 

if (e>=1/2)

{

// d : диагональное смещение

x++; y++;

e+=De-1 ; // т.к. произошло смещение по y на 1 вверх

}

else

{

// s : горизонтальное смещение

x++;

e+=De;

}

}

 

Недостаток алгоритма:

Работает с числами с плавающей точкой.

 

Модифицируем наш алгоритм так, чтобы он работал с целыми числами:

1) В начале e₀=De -1/2. (чтобы сравнивать с 0);

2) домножим e₀ и De на 2a :

De=2b , e₀=2b-a .

 

Кроме этого, вынося общую для обоих случаев часть из else,приходим к следующему алгоритму, называемому

 

Алгоритм Брезенхема [Bresenham, 1965]

 

while(x £ a)

{

plot (x,y);

 

if (e>=0)

{

// диагональное смещение

y++;

e-=2a ; // раньше это соответствовало e-=1 (смещение по y на 1 вверх)

}

// часть, общая для диагонального и горизонтального смещений

x++;

e+= De ;

}

 

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

Дальнейшая оптимизация может быть произведена, если заметить, что отрезок симметричен относительно прямой, проходящей перпендикулярно ему через его середину; в этом случае можно начинать рисовать сразу с двух концов, что сократит время общей работы алгоритма вдвое:

 

А теперь приведем алгоритм, который работает гораздо медленнее, но обладает наиболее красивой структурой; он основан на идее, схожей с известным алгоритмом Евклида нахождения Наибольшего Общего Делителя двух натуральных чисел.

 

Алгоритм Castle-Pitteway [Castle-Pitteway, 1987]

РисуемAB : A (0,0) -> B (x,y)

 

s и d понимаются в описанном выше смысле

m₁ и m₂ - строки

 

Å - конкатенация строк (например "ssds" Å "sddd"="ssdssddd" )

~ - "переворот" строки (например ~ ("ssdds")="sddss" )

 

b=y;

a=x-y;

m1="s";

m2="d";

 

while (a ¹ b)

{

a= a - b;

m₂=m₁ Å ₂ ;

}

else

{

b=b - a;

m₁=m₂ Å ₁ ;

}

 

После завершения работы алгоритма m= m₂ Å ₁ задает нужную последовательность сдвигов.

 

Доказательство корректности работы этого алгоритма мы опустим ввиду его громоздкости.