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

Материал из Википедии — свободной энциклопедии
Это текущая версия страницы, сохранённая InternetArchiveBot (обсуждение | вклад) в 00:04, 25 января 2021 (Добавьте 1 книгу для Википедия:Проверяемость (20210123)) #IABot (v2.0.8) (GreenC bot). Вы просматриваете постоянную ссылку на эту версию.
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Пусть отрезок задан вещественными координатами концов ; . Растровыми (целочисленными) координатами концевых точек становятся округлённые значения исходных координат: , ; , [2].

Большее по абсолютной величине число, или , увеличенное на 1 принимается за количество шагов цикла растеризации.

В начале цикла вспомогательным вещественным переменным и присваиваются исходные координаты начала отрезка: ; . На каждом шаге цикла эти вещественные переменные получают приращения ; . Растровые же координаты, продуцируемые на каждом шаге, являются результатом округления соответствующих вещественных значений и .

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

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

Примечания

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

Литература

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