Меню Главная Случайная статья Настройки Алгоритм DDA-линии Материал из https://ru.wikipedia.org Алгоритм DDA-линии[1] растеризует отрезок прямой между двумя заданными точками, используя вычисления в числах с плавающей запятой или целых числах. Содержание 1 Алгоритм 2 Примечания 3 См. также 4 Литература 5 Ссылки Алгоритм Пусть отрезок задан вещественными координатами концов ${\displaystyle (x_{1},y_{1})}$; ${\displaystyle (x_{2},y_{2})}$. Растровыми (целочисленными) координатами концевых точек становятся округлённые значения исходных координат: ${\displaystyle x_{\mathrm {start} }=\operatorname {round} (x_{1})}$, ${\displaystyle y_{\mathrm {start} }=\operatorname {round} (y_{1})}$; ${\displaystyle x_{\mathrm {end} }=\operatorname {round} (x_{2})}$, ${\displaystyle y_{\mathrm {end} }=\operatorname {round} (y_{2})}$[2]. Большее по абсолютной величине число, ${\displaystyle (x_{\mathrm {end} }-x_{\mathrm {start} })}$ или ${\displaystyle (y_{\mathrm {end} }-y_{\mathrm {start} })}$, увеличенное на 1 принимается за количество шагов ${\displaystyle L}$ цикла растеризации. В начале цикла вспомогательным вещественным переменным ${\displaystyle x}$ и ${\displaystyle y}$ присваиваются исходные координаты начала отрезка: ${\displaystyle x=x_{1}}$; ${\displaystyle y=y_{1}}$. На каждом шаге цикла эти вещественные переменные получают приращения ${\displaystyle (x_{\mathrm {end} }-x_{\mathrm {start} })/L}$; ${\displaystyle (y_{\mathrm {end} }-y_{\mathrm {start} })/L}$. Растровые же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений ${\displaystyle x}$ и ${\displaystyle y}$. Применение вычислений с вещественными числами и лишь однократное использование округления для окончательного получения значения растровой координаты обусловливают высокую точность и низкое быстродействие алгоритма. Модифицированный алгоритм DDA-линии применяется для растеризации окружностей. Примечания Аббревиатура DDA в названии этого алгоритма машинной графики происходит от англ. digital differential analyzer — цифровой дифференциальный анализатор. Вообще говоря, если вещественные координаты концов отрезка заданы в некоторой логической системе координат, то соответствующие им растровые координаты определяются на основании правил пересчёта, установленных для конкретной пары систем координат: логической и экранной. См. также Алгоритмы построения отрезка Алгоритм Брезенхэма Алгоритм Ву Литература Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. — С. 50-54. — ISBN 5-03-000476-9. Ссылки Чириков С. В. Алгоритмы компьютерной графики (Методы растрирования кривых). Учебное пособие — СПб: СПбГИТМО(ТУ), 2001. — 120 с. Растеризация отрезка. Алгоритм 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