Алгоритм генерации линий Брезенхема
Даны координаты двух точек A (x1, y1) и B (x2, y2). Задача найти все промежуточные точки, необходимые для рисования линии AB на экране пикселей компьютера. Обратите внимание, что каждый пиксель имеет целочисленные координаты.
Примеры:
Ввод: A (0,0), B (4,4) Выход: (0,0), (1,1), (2,2), (3,3), (4,4) Ввод: A (0,0), B (4,2) Выход: (0,0), (1,0), (2,1), (3,1), (4,2)
Ниже приведены некоторые предположения для упрощения алгоритма.
- Проводим линию слева направо.
- x1 <x2 и y1 <y2
- Наклон линии составляет от 0 до 1. Проводим линию снизу слева направо.
Давайте разберемся в этом процессе, рассмотрев сначала наивный путь.
// Наивный способ рисования линии void naiveDrawLine (x1, x2, y1, y2) { т = (у2 - у1) / (х2 - х1) для (x = x1; x <= x2; x ++) { // Предполагая, что функция раунда находит // ближайшее целое число к заданному числу с плавающей запятой. y = круглый (mx + c); печать (х, у); } }
Вышеупомянутый алгоритм работает, но он медленный. Идея алгоритма Брезенхема состоит в том, чтобы избежать умножения и сложения с плавающей запятой для вычисления mx + c, а затем вычисления округленного значения (mx + c) на каждом шаге. В алгоритме Брезенхема мы перемещаемся по оси x с единичными интервалами.
- Мы всегда увеличиваем x на 1 и выбираем следующий y, нужно ли нам перейти к y + 1 или остаться на y. Другими словами, из любой позиции (X k , Y k ) нам нужно выбирать между (X k + 1, Y k ) и (X k + 1, Y k + 1).
- Мы хотели бы выбрать значение y (среди Y k + 1 и Y k ), соответствующее точке, которая находится ближе к исходной линии.
Нам нужен параметр решения, чтобы решить, выбрать ли Y k + 1 или Y k в качестве следующей точки. Идея состоит в том, чтобы отслеживать ошибку наклона от предыдущего приращения до y. Если ошибка наклона становится больше 0,5, мы знаем, что линия переместилась вверх на один пиксель, и что мы должны увеличить нашу координату y и скорректировать ошибку, чтобы представить расстояние от вершины нового пикселя - что делается путем вычитания единицы. от ошибки.
// Изменение наивного способа использования параметра // решить следующий y . void withDecisionParameter (x1, x2, y1, y2) { т = (у2 - у1) / (х2 - х1) slope_error = [Некоторое начальное значение] для (x = x1, y = y1; x = 0,5) { y ++; slope_error - = 1.0; } }
Как избежать арифметики с плавающей запятой
Вышеупомянутый алгоритм по-прежнему включает арифметику с плавающей запятой. Чтобы избежать арифметики с плавающей запятой, учитывайте значение ниже значения m.
т = (у2 - у1) / (х2 - х1)
Умножаем обе части на (x2 - x1)
Мы также меняем slope_error на slope_error * (x2 - x1). Чтобы избежать сравнения с 0.5, мы изменим его на slope_error * (x2 - x1) * 2.
Кроме того, обычно предпочтительнее сравнивать с 0, чем с 1.
// Модификация вышеуказанного алгоритма, чтобы избежать плавающих // точечная арифметика и сравнение с 0. пустота брезенхема (x1, x2, y1, y2) { m_new = 2 * (y2 - y1) slope_error_new = [Некоторое начальное значение] для (x = x1, y = y1; x = 0) { y ++; slope_error_new - = 2 * (x2 - x1); } }
The initial value of slope_error_new is 2*(y2 – y1) – (x2 – x1). Refer this for proof of this value
Below is the implementation of above algorithm.
C++
// C++ program for Bresenham’s Line Generation // Assumptions : // 1) Line is drawn from left to right. // 2) x1 < x2 and y1 < y2 // 3) Slope of the line is between 0 and 1. // We draw a line from lower left to upper // right. #include<bits/stdc++.h> using namespace std; // function for line generation void bresenham( int x1, int y1, int x2, int y2) { int m_new = 2 * (y2 - y1); int slope_error_new = m_new - (x2 - x1); for ( int x = x1, y = y1; x <= x2; x++) { cout << "(" << x << "," << y << ")
"; // Add slope to increment angle formed slope_error_new += m_new; // Slope error reached limit, time to // increment y and update slope error. if (slope_error_new >= 0) { y++; slope_error_new -= 2 * (x2 - x1); } } } // driver function int main() { int x1 = 3, y1 = 2, x2 = 15, y2 = 5; bresenham(x1, y1, x2, y2); return 0; } |
Java
// Java program for Bresenhams Line Generation // Assumptions : // 1) Line is drawn from left to right. // 2) x1 < x2 and y1 < y2 // 3) Slope of the line is between 0 and 1. // We draw a line from lower left to upper // right. class GFG { // function for line generation static void bresenham( int x1, int y1, int x2, int y2) { int m_new = 2 * (y2 - y1); int slope_error_new = m_new - (x2 - x1); for ( int x = x1, y = y1; x <= x2; x++) { System.out.print("(" +x + "," + y + ")
"); // Add slope to increment angle formed slope_error_new += m_new; // Slope error reached limit, time to // increment y and update slope error. if (slope_error_new >= 0 ) { y++; slope_error_new -= 2 * (x2 - x1); } } } // Driver code public static void main (String[] args) { int x1 = 3 , y1 = 2 , x2 = 15 , y2 = 5 ; bresenham(x1, y1, x2, y2); } } // This code is contributed by Anant Agarwal. |
Python3
# Python 3 program for Bresenham’s Line Generation # Assumptions : # 1) Line is drawn from left to right. # 2) x1 < x2 and y1 < y2 # 3) Slope of the line is between 0 and 1. # We draw a line from lower left to upper # right. # function for line generation def bresenham(x1,y1,x2, y2): m_new = 2 * (y2 - y1) slope_error_new = m_new - (x2 - x1) y = y1 for x in range (x1,x2 + 1 ): print ( "(" ,x , "," ,y , ")
" ) # Add slope to increment angle formed slope_error_new = slope_error_new + m_new # Slope error reached limit, time to # increment y and update slope error. if (slope_error_new > = 0 ): y = y + 1 slope_error_new = slope_error_new - 2 * (x2 - x1) # driver function if __name__ = = "__main__" : x1 = 3 y1 = 2 x2 = 15 y2 = 5 bresenham(x1, y1, x2, y2) #This code is contributed by ash264 |
C#
// C# program for Bresenhams Line Generation // Assumptions : // 1) Line is drawn from left to right. // 2) x1 < x2 and y1< y2 // 3) Slope of the line is between 0 and 1. // We draw a line from lower left to upper // right. using System; class GFG { // function for line generation static void bresenham( int x1, int y1, int x2, int y2) { int m_new = 2 * (y2 - y1); int slope_error_new = m_new - (x2 - x1); for ( int x = x1, y = y1; x <= x2; x++) { Console.Write("(" + x + "," + y + ")
"); // Add slope to increment angle formed slope_error_new += m_new; // Slope error reached limit, time to // increment y and update slope error. if (slope_error_new >= 0) { y++; slope_error_new -= 2 * (x2 - x1); } } } // Driver code public static void Main () { int x1 = 3, y1 = 2, x2 = 15, y2 = 5; bresenham(x1, y1, x2, y2); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program for Bresenham’s // Line Generation Assumptions : // 1) Line is drawn from // left to right. // 2) x1 < x2 and y1 < y2 // 3) Slope of the line is // between 0 and 1. // We draw a line from lower // left to upper right. // function for line generation function bresenham( $x1 , $y1 , $x2 , $y2 ) { $m_new = 2 * ( $y2 - $y1 ); $slope_error_new = $m_new - ( $x2 - $x1 ); for ( $x = $x1 , $y = $y1 ; $x <= $x2 ; $x ++) { echo "(" , $x , "," , $y , ")
" ; // Add slope to increment // angle formed $slope_error_new += $m_new ; // Slope error reached limit, // time to increment y and // update slope error. if ( $slope_error_new >= 0) { $y ++; $slope_error_new -= 2 * ( $x2 - $x1 ); } } } // Driver Code $x1 = 3; $y1 = 2; $x2 = 15; $y2 = 5; bresenham( $x1 , $y1 , $x2 , $y2 ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // javascript program for Bresenhams Line Generation // Assumptions : // 1) Line is drawn from left to right. // 2) x1 < x2 and y1 < y2 // 3) Slope of the line is between 0 and 1. // We draw a line from lower left to upper // right. // function for line generation function bresenham(x1 , y1 , x2,y2) { var m_new = 2 * (y2 - y1); var slope_error_new = m_new - (x2 - x1); for (x = x1, y = y1; x <= x2; x++) { document.write( "(" +x + "," + y + ")<br>" ); // Add slope to increment angle formed slope_error_new += m_new; // Slope error reached limit, time to // increment y and update slope error. if (slope_error_new >= 0) { y++; slope_error_new -= 2 * (x2 - x1); } } } // Driver code var x1 = 3, y1 = 2, x2 = 15, y2 = 5; bresenham(x1, y1, x2, y2); // This code is contributed by Amit Katiyar </script> |
Выход :
(3,2) (4,3) (5,3) (6,3) (7,3) (8,4) (9,4) (10,4) (11,4) (12,5) (13,5) (14,5) (15,5)
Приведенное выше объяснение дает приблизительное представление об алгоритме. Для подробного объяснения и доказательства читатели могут обратиться к приведенным ниже ссылкам.
Статьи по Теме:
- Алгоритм создания линии средней точки
- Алгоритм DDA для рисования линий
Ссылка :
https://csustan.csustan.edu/~tom/Lecture-Notes/Graphics/Bresenham-Line/Bresenham-Line.pdf
https://en.wikipedia.org/wiki/Bresenham's_line_algorithm
http://graphics.idav.ucdavis.edu/education/GraphicsNotes/Bresenhams-Algorithm.pdf
Эта статья предоставлена Шивамом Прадханом (anuj_charm). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.