Алгоритм генерации линии DDA в компьютерной графике

Опубликовано: 20 Января, 2022

В любой двумерной плоскости, если мы соединим две точки (x0, y0) и (x1, y1), мы получим отрезок прямой. Но в случае компьютерной графики мы не можем напрямую соединить любые две координатные точки, для этого мы должны вычислить координаты промежуточных точек и поставить пиксель для каждой промежуточной точки желаемого цвета с помощью таких функций, как putpixel (x, y , K) в C, где (x, y) наша координата, а K обозначает некоторый цвет.
Примеры:

 Ввод: для сегмента линии между (2, 2) и (6, 6):
нам нужны (3, 3) (4, 4) и (5, 5) в качестве промежуточных
точки.

Ввод: для сегмента линии между (0, 2) и (0, 6):
нам нужны (0, 3) (0, 4) и (0, 5) в качестве промежуточных
точки.

Для использования графических функций экран вывода нашей системы рассматривается как система координат, в которой координата верхнего левого угла равна (0, 0), и по мере движения вниз наша ордината y увеличивается, а при движении вправо наша ордината x увеличивается. для любой точки (x, y).
Теперь для генерации любого отрезка линии нам нужны промежуточные точки, и для их вычисления мы можем использовать базовый алгоритм, называемый алгоритмом генерации линии DDA (цифровой дифференциальный анализатор).

Алгоритм DDA:
Рассмотрим одну точку прямой как (X0, Y0), а вторую точку прямой как (X1, Y1).

 // вычисляем dx, dy
dx = X1 - X0;
dy = Y1 - Y0;

// В зависимости от абсолютного значения dx & dy
// выбираем количество шагов, чтобы поместить пиксель как
// шаги = abs (dx)> abs (dy)? абс (дх): абс (ду)
шаги = abs (dx)> abs (dy)? абс (dx): абс (dy);

// вычисляем приращение по x и y для каждого шага
Xinc = dx / (float) шаги;
Yinc = dy / (float) шаги;

// Ставим пиксель для каждого шага
Х = Х0;
Y = Y0;
для (int i = 0; i <= шаги; i ++)
{
    putpixel (круглый (X), круглый (Y), БЕЛЫЙ);
    X + = Xinc;
    Y + = Инь;
}

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Выход:

Преимущества :

  • Это простой и легкий в реализации алгоритм.
  • Это позволяет избежать использования нескольких операций, которые требуют больших временных затрат.
  • Это быстрее, чем прямое использование линейного уравнения, потому что оно не использует умножение с плавающей запятой и вычисляет точки на линии.

Недостатки:

  • Он имеет дело с операциями округления и арифметикой с плавающей запятой, поэтому имеет высокую временную сложность.
  • Поскольку он зависит от ориентации, он имеет низкую точность конечной точки.
  • Из-за ограниченной точности представления с плавающей запятой возникает кумулятивная ошибка.

Алгоритм генерации линий Брезенхема
Эта статья предоставлена Шивамом Прадханом (anuj_charm). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.