загрузка...
загрузка...
На головну

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

Будує 8-зв'язну лінію


e0=<1; De=<1

P1= (1,0); P2= (1,1)

У початковий момент

x = 0;

y = 0;

e = e0;


Мал. 5. Алгоритм DDA.

У зв'язку з подібністю трикутників, для того щоб визначити, яка з точок (P1 або P2) Ближче, досить порівняти відстані від точки перетину P до P1 и P2, Що рівносильно порівнянні 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) На початку e0= De -1/2. (Щоб порівнювати з 0);

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

De = 2b, e0= 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 розуміються в описаному вище сенсі

m1 и m2 - рядки

A - конкатенація рядків (наприклад "ssds" A "sddd" = "ssdssddd")

~ - "Переворот" рядка (наприклад ~ ( "ssdds") = "sddss")

b = y;

a = x-y;

m1 = "s";

m2 = "d";

while (a ? b)

{

a = a - b;

m2= m1 A 2 ;

}

else

{

b = b - a;

m1= m2 A 1 ;

}

Після завершення роботи алгоритму m = m2 A 1 задає потрібну послідовність зрушень.

Доведення коректності роботи цього алгоритму ми опустимо через його громіздкість.

Зображення відрізка з цілочисельними координатами кінців «-- попередня | наступна --» Малювання відрізка з нецілочисельне координатами кінців
загрузка...
© om.net.ua