Алгоритм DDA-линии


Алгоритм DDA-линии

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

Содержание

Алгоритм

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

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

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

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

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

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++;
 }
/* -------------------------------*/
}

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

       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;
       }

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

Примечания

  1. Вообще говоря, если вещественные координаты концов отрезка заданы в некоторой логической системе координат, то соответствующие им растровые координаты определяются на основании правил пересчёта, установленных для конкретной пары систем координат: логической и экранной.

См. также

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Алгоритм DDA-линии" в других словарях:

  • Алгоритм Брезенхэма — Иллюстрация результата работы алгоритма Алгоритм Брезенхема (англ. Bresenham s line algorithm)  это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближ …   Википедия

  • Алгоритм Ву — Распределение интенсивности пикселя в зависимости от расстояния до идеальной линии Алгоритм Ву  это алгоритм разложения отрезка в растр со сглаживанием. Был предложен У Сяолинем (Xiaolin Wu, отсюда устоявшееся в русском языке название… …   Википедия

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

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Алгоритмы построения отрезка — Идеальная линия и результат разложения в растр Алгоритмы построения отрезка  графические алгоритмы аппроксимации отрезка на дискретном графическом устройстве (растеризации), например, мониторе или принтере. Стандартными требованиями к… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.