Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм DDA-линии

Алгоритм DDA-линии растеризует отрезок прямой между двумя заданными точками, используя вычисления с вещественными числами. Аббревиатура DDA в названии этого алгоритма машинной графики происходит от англ. Digital Differential Analyzer — вычислительное устройство, применявшееся ранее для генерации векторов...

Алгоритм

Пусть отрезок задан вещественными координатами концов ; . Растровыми координатами концевых точек становятся округлённые значения исходных координат: xstart = round, ystart = round; xend = round, yend = round.

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

В начале цикла вспомогательным вещественным переменным x и y присваиваются исходные координаты начала отрезка: x = x₁; y = y₁. На каждом шаге цикла эти вещественные переменные получают приращения  / L;  / L. Растровые же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений x и y.

Применение вычислений с вещественными числами и лишь однократное использование округления для окончательного получения значения растровой координаты обусловливают высокую точность и низкое быстродействие алгоритма.

Далее представлен программный код реализации алгоритма DDA-линии. Значения вспомогательных переменных x и y здесь сохраняются в виде массивов.

void dda_line
{
 int i, L, xstart, ystart, xend, yend;
 float dX, dY, x, y;    
 xstart = roundf;
 ystart = roundf;
 xend = roundf;
 yend = roundf;
 L = max, abs);
 dX = / L;
 dY = / L;
 i = 0;
 x = x1;
 y = y1;
 i++;
 while
 {
  x = x + dX;
  y = y + dY;
  i++;
 }
 x = x2;
 y = y2;
/* Output: -----------------------*/
 i = 0;
 while
 {
  plot, roundf); /* Draws a point. */
  i++;
 }
/* -------------------------------*/
}

оптимизированный алгоритм, вместо деления использует побитовое смещение. sx,sy - начало линии tx,ty - конец линии. Применяется в случае если использование переменных с плавающей запятой невозможно в виду каких либо ограничений.

       int l,dx,dy;
       int xr=Math.abs;
       int yr=Math.abs;
       if{l=xr;}else{l=yr;}
       int px=+;     //  1<<11 аналогично 0.5 у float
       int py=+;
       int ex=+;
       int ey=+;
       if{
           dx = / l;
           dy = / l;
       } else {
           dx = 0;
           dy = 0;
       }
       for{
           drawpoint;
           px+=dx;
           py+=dy;
       }

Модифицированный алгоритм DDA-линии применяется для растеризации окружностей.