Алгоритм генерации линии DDA в компьютерной графике
В любой двумерной плоскости, если мы соединим две точки (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 + = Инь; }
Выход:
Преимущества :
- Это простой и легкий в реализации алгоритм.
- Это позволяет избежать использования нескольких операций, которые требуют больших временных затрат.
- Это быстрее, чем прямое использование линейного уравнения, потому что оно не использует умножение с плавающей запятой и вычисляет точки на линии.
Недостатки:
- Он имеет дело с операциями округления и арифметикой с плавающей запятой, поэтому имеет высокую временную сложность.
- Поскольку он зависит от ориентации, он имеет низкую точность конечной точки.
- Из-за ограниченной точности представления с плавающей запятой возникает кумулятивная ошибка.
Алгоритм генерации линий Брезенхема
Эта статья предоставлена Шивамом Прадханом (anuj_charm). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.