Алгоритм DDA-линии (Glikjnmb DDA-lnunn)

Алгоритм DDA-линии^[1] растеризует отрезок прямой между двумя заданными точками, используя вычисления в числах с плавающей запятой или целых числах.

Алгоритм[править | править код]

Пусть отрезок задан вещественными координатами концов $(x_{1},y_{1})$ ; $(x_{2},y_{2})$ . Растровыми (целочисленными) координатами концевых точек становятся округлённые значения исходных координат: $x_{\mathrm {start} }=\operatorname {round} (x_{1})$ , $y_{\mathrm {start} }=\operatorname {round} (y_{1})$ ; $x_{\mathrm {end} }=\operatorname {round} (x_{2})$ , $y_{\mathrm {end} }=\operatorname {round} (y_{2})$ ^[2].

Большее по абсолютной величине число, $(x_{\mathrm {end} }-x_{\mathrm {start} })$ или $(y_{\mathrm {end} }-y_{\mathrm {start} })$ , увеличенное на 1 принимается за количество шагов $L$ цикла растеризации.

В начале цикла вспомогательным вещественным переменным $x$ и $y$ присваиваются исходные координаты начала отрезка: $x=x_{1}$ ; $y=y_{1}$ . На каждом шаге цикла эти вещественные переменные получают приращения $(x_{\mathrm {end} }-x_{\mathrm {start} })/L$ ; $(y_{\mathrm {end} }-y_{\mathrm {start} })/L$ . Растровые же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений $x$ и $y$ .

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

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

Примечания[править | править код]

↑ Аббревиатура DDA в названии этого алгоритма машинной графики происходит от англ. digital differential analyzer — цифровой дифференциальный анализатор.
↑ Вообще говоря, если вещественные координаты концов отрезка заданы в некоторой логической системе координат, то соответствующие им растровые координаты определяются на основании правил пересчёта, установленных для конкретной пары систем координат: логической и экранной.