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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм 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}}) — по абсолютной величине принимается за количество шагов L цикла растеризации, увеличенное на 1.

В начале цикла вспомогательным вещественным переменным 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-линии применяется для растеризации окружностей.

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

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. — С. 50-54. — ISBN 5-03-000476-9.

Ссылки[править | править вики-текст]