Алгоритм DDA-линииАббревиатура DDA в названии этого алгоритма машинной графики происходит от — цифровой дифференциальный анализатор. растеризует отрезок прямой между двумя заданными точками, используя вычисления в числах с плавающей запятой или целых числах.
Алгоритм Пусть отрезок задан вещественными координатами концов ; . Растровыми (целочисленными) координатами концевых точек становятся округлённые значения исходных координат: , ; , Вообще говоря, если вещественные координаты концов отрезка заданы в некоторой логической системе координат, то соответствующие им растровые координаты определяются на основании правил пересчёта, установленных для конкретной пары систем координат: логической и экранной..
Большее по абсолютной величине число, или , увеличенное на 1 принимается за количество шагов цикла растеризации.
В начале цикла вспомогательным вещественным переменным и присваиваются исходные координаты начала отрезка: ; . На каждом шаге цикла эти вещественные переменные получают приращения ; . Растровые же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений и .
Применение вычислений с вещественными числами и лишь однократное использование округления для окончательного получения значения растровой координаты обусловливают высокую точность и низкое быстродействие алгоритма.
Модифицированный алгоритм DDA-линии применяется для растеризации окружностей.
Примечания
См. также
Алгоритмы построения отрезка Алгоритм Брезенхэма Алгоритм Ву
Литература
Ссылки Чириков С. В. Алгоритмы компьютерной графики (Методы растрирования кривых). Учебное пособие — СПб: СПбГИТМО(ТУ), 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
Категория:Геометрические алгоритмы