Просмотр кода страницы Алгоритм DDA-линии

'''Алгоритм DDA-линии''' [[Алгоритмы построения отрезка|растеризует отрезок прямой между двумя заданными точками]], используя вычисления с [[вещественное число|вещественными числами]]. Аббревиатура DDA в названии этого алгоритма [[машинная графика|машинной графики]] происходит от {{lang-en|Digital Differential Analyzer}} (цифровой дифференциальный анализатор) — вычислительное устройство, применявшееся ранее для генерации векторов.

== Алгоритм ==

Пусть отрезок задан вещественными координатами концов
<math>(x_1, y_1)</math>;
<math>(x_2, y_2)</math>.
Растровыми ([[целое число|целочисленными]]) координатами концевых точек становятся округлённые значения исходных координат:
<math>xstart=round(x_1)</math>, <math>ystart=round(y_1)</math>; <math>xend=round(x_2)</math>, <math>yend=round(y_2)</math><ref>Вообще говоря, если вещественные координаты концов отрезка заданы в некоторой логической системе координат, то соответствующие им растровые координаты определяются на основании правил пересчёта, установленных для конкретной пары систем координат: логической и экранной.</ref>.

Большее из двух чисел — <math>(xend-xstart)</math> или <math>(yend-ystart)</math> — по абсолютной величине принимается за количество шагов <math>L</math> цикла растеризации, увеличенное на 1.

В начале цикла вспомогательным вещественным переменным <math>x</math> и <math>y</math> присваиваются исходные координаты начала отрезка:
<math>x = x_1</math>;
<math>y = y_1</math>.
На каждом шаге цикла эти ''вещественные'' переменные получают приращения
<math>(xend-xstart)</math>''&nbsp;/&nbsp;L'';
<math>(yend-ystart)</math>''&nbsp;/&nbsp;L''.
''Растровые'' же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений <math>x</math> и <math>y</math>.

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

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

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

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

<code>
        int l,dx,dy;
        int xr=Math.abs(tx-sx);
        int yr=Math.abs(ty-sy);
        if(xr>yr){l=xr;}else{l=yr;}
        int px=(sx<<12)+(1<<11);     //  1<<11 аналогично 0.5 у float
        int py=(sy<<12)+(1<<11);
        int ex=(tx<<12)+(1<<11);
        int ey=(ty<<12)+(1<<11);
        if(l!=0){
            dx = (ex-px) / l;
            dy = (ey-py) / l;
        } else {
            dx = 0;
            dy = 0;
        }
        for(int i=0;i<=l;i++){
            drawpoint(px>>12, py>>12);
            px+=dx;
            py+=dy;
        }
</code>

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

== Примечания ==
<div class="references-small"><references/></div>

== Ссылки ==

* [http://www.ict.edu.ru/ft/001715//chirikov.pdf Чириков С. В. Алгоритмы компьютерной графики (Методы растрирования кривых). Учебное пособие – СПб: СПбГИТМО(ТУ), 2001. – 120 с.]
* [http://www.compgraphics.info/2D/DDA_line.php Растеризация отрезка. Алгоритм DDA-линии.]
* McCrea P. G., Baker P. W. On DDA circle generation for computer graphics. IEEE Trans. on Computers. - 1975. - V. C-24. - P. 1109-1110

[[Категория:Геометрические алгоритмы]]

[[fr:Analyseur différentiel numérique]]
[[it:Algoritmo DDA]]