Алгоритм Брезенхема
Брезенхем [16] модифікував алгоритм DDA, щоб він працював у цілих числах. Модифікуємо алгоритм у такий спосіб:
- зменшимо скрізь e на 
, щоб порівнювати з 0;
- домножимо e і Δe на 2a: e0 = 2b - a, Δe = 2b
Приходимо до наступного алгоритму:
// Координати кінців відрізка - (0,0) і (a,b)e = 2b - a;?e = 2b;?e = 2b - 2a; x = 0; y = 0; // (x,y) - Координати поточної крапки while(x < a){ plot(x, y); if(e > 0) { // d : діагональний зсув x++; y++; e += ?e; } else { // s : горизонтальний зсув x++; e += ?e; }}Лістинг 6.2. Алгоритм Брезенхема для відрізка
Алгоритм Брезенхема був створений їм для виводу відрізків на цифрових інкрементальних графобудівниках, які могли здійснювати лише прості одиничні зрушення друкуючої головки. Подальша оптимізація може бути зроблена, якщо помітити, що відрізок симетричний відносно прямій, що проходить перпендикулярно йому через його середину; у цьому випадку можна починати малювати відразу із двох кінців, що скоротить число ітерацій циклу в алгоритмі вдвічі.
Дата добавления: 2015-04-03; просмотров: 1360;