https://web.archive.org/web/20230512162252/https://www.geeksforgeeks.org/bresenhams-line-generation-algorithm/ #GeeksforGeeks >> Feed GeeksforGeeks >> Comments Feed GeeksforGeeks >> Bresenham's Line Generation Algorithm Comments Feed alternate alternate IFRAME: https://archive.org/includes/donate.php?as_page=1&platform=wb&referer=h ttps%3A//web.archive.org/web/20230512162252/https%3A//www.geeksforgeeks .org/bresenhams-line-generation-algorithm/ Wayback Machine https://www.geeksfor Go 39 captures 18 Feb 2017 - 12 May 2023 Jan MAY Jun Previous capture 12 Next capture 2021 2023 2024 success fail About this capture COLLECTED BY Collection: mega002 TIMESTAMPS loading The Wayback Machine - https://web.archive.org/web/20230512162252/https://www.geeksforgeeks.or g/bresenhams-line-generation-algorithm/ Skip to content geeksforgeeks * Courses + Data Structures and Algorithms o DSA for Interview Preparation o DSA Live for Working Professionals o DSA Self-paced in C++/Java o DSA Self-paced in Python o DSA Self-paced in Javascript o DSA Self-paced in C + For Working Professionals o Data Structure & Algorithm Classes (Live) o System Design (Live) o DevOps(Live) o Data Structures & Algorithms in JavaScript o Explore More Live Courses + For Students o Interview Preparation Course o Data Science (Live) o GATE CS & IT 2024 o Data Structures & Algorithms in JavaScript o Data Structure & Algorithm-Self Paced(C++/JAVA) o Data Structures & Algorithms in Python o Explore More Self-Paced Courses + Programming Languages o C++ Programming - Beginner to Advanced o Java Programming - Beginner to Advanced o C Programming - Beginner to Advanced + Web Development o Full Stack Development with React & Node JS(Live) o Java Backend Development(Live) o Android App Development with Kotlin(Live) o Python Backend Development with Django(Live) + Machine Learning and Data Science o Complete Data Science Program(Live) o Mastering Data Analytics + New Courses o Python Backend Development with Django(Live) o Android App Development with Kotlin(Live) o DevOps Engineering - Planning to Production + School Courses o CBSE Class 12 Computer Science o School Guide + All Courses * Tutorials + DSA + Data Structures o Arrays o Linked List o Stack o Queue o Binary Tree o Binary Search Tree o Heap o Hashing o Graph o Advanced Data Structure o Matrix o Strings o All Data Structures + Algorithms o Analysis of Algorithms # Design and Analysis of Algorithms # Asymptotic Analysis # Worst, Average and Best Cases # Asymptotic Notations # Little o and little omega notations # Lower and Upper Bound Theory # Analysis of Loops # Solving Recurrences # Amortized Analysis # What does 'Space Complexity' mean ? # Pseudo-polynomial Algorithms # Polynomial Time Approximation Scheme # A Time Complexity Question o Searching Algorithms o Sorting Algorithms o Graph Algorithms o Pattern Searching o Geometric Algorithms o Mathematical o Bitwise Algorithms o Randomized Algorithms o Greedy Algorithms o Dynamic Programming o Divide and Conquer o Backtracking o Branch and Bound o All Algorithms + System Design o System Design Tutorial o Software Design Patterns + Interview Corner o Company Preparation o Top Topics o Practice Company Questions o Interview Experiences o Experienced Interviews o Internship Interviews o Competitive Programming o Multiple Choice Quizzes o Aptitude for Placements + Languages o C o C++ o Java o Python o JavaScript o PHP o C# o SQL o Scala o Perl o Go Language o Kotlin + Web Development o HTML o CSS o JavaScript o PHP o CSS Frameworks # Bootstrap # Tailwind CSS # Foundation CSS # Materialize CSS # Bulma # Pure CSS # Primer CSS # Blaze UI # Semantic UI o JavaScript Frameworks # AngularJS # Angular PrimeNG # Angular ngx Bootstrap # NodeJS # Express.js o JavaScript Libraries # jQuery # jQuery Mobile # jQuery UI # jQuery EasyUI # jQWidgets # ReactJS # React Bootstrap # React Rebass # React Desktop # React Suite # ReactJS Evergreen # ReactJS Reactstrap # Ant Design # BlueprintJS # p5.js # Lodash # TensorFlow.js # Moment.js # Collect.js o WordPress o JSON + School Learning o English Grammar o School Programming o Mathematics # Number System # Algebra # Trigonometry # Statistics # Probability # Geometry # Mensuration # Calculus o CBSE Syllabus # Class 8 Syllabus # Class 9 Syllabus # Class 10 Syllabus # Class 11 Syllabus # Class 12 Syllabus o Maths Notes (Class 8-12) # Class 8 Notes # Class 9 Notes # Class 10 Notes # Class 11 Notes # Class 12 Notes o Maths Formulas (Class 8 -11) # Class 8 Formulas # Class 9 Formulas # Class 10 Formulas # Class 11 Formulas o NCERT Solutions # Class 8 Maths Solution # Class 9 Maths Solution # Class 10 Maths Solution # Class 11 Maths Solution # Class 12 Maths Solution o RD Sharma Solutions # Class 8 Maths Solution # Class 9 Maths Solution # Class 10 Maths Solution # Class 11 Maths Solution # Class 12 Maths Solution o Science Notes # Class 8 Notes # Class 9 Notes # Class 10 Notes o Physics Notes (Class 8-12) # Class 8 Notes # Class 9 Notes # Class 10 Notes # Class 11 Notes # Class 12 Notes o Chemistry Notes (Class 8-12) # Class 8 Notes # Class 9 Notes # Class 10 Notes # Class 11 Notes # Class 12 Notes o Biology Notes # Class 8 # Class 9 # Class 10 # Class 11 o Social Science Syllabus # Class 7 SS Syllabus # Class 8 SS Syllabus # Class 9 SS Syllabus # Class 10 SS Syllabus o Social Science Notes # SS Notes (Class 7-12) @ Class 7 Notes @ Class 8 Notes @ Class 9 Notes @ Class 10 Notes # CBSE History Notes (Class 7-10) @ History Class 7 @ History Class 8 @ History Class 9 # CBSE Geography Notes (Class 7-10) @ Geo. Class 7 @ Geo. Class 8 @ Geo. Class 9 # CBSE Civics Notes (Class 7-10) @ Civics Class 7 @ Civics Class 8 o Commerce # Business Studies (Class 11th) # Microeconomics (Class 11th) # Statistics for Economics (Class 11th) # Business Studies (Class 12th) # Accountancy (Class 12th) # Macroeconomics (Class 12th) o CBSE Previous Year Papers # Maths # Physics # History # Georgraphy # Political Science # Economics + ML & Data Science o Machine Learning o Data Science + DevOps o GIT o AWS o Docker o Kubernetes o Microsoft Azure Tutorial o Google Cloud Platform + CS Subjects o Mathematics o Operating System o DBMS o Computer Networks o Computer Organization and Architecture o Theory of Computation o Compiler Design o Digital Logic o Software Engineering + GATE o GATE 2024 Live Course o GATE Computer Science Notes o Last Minute Notes o GATE CS Solved Papers o GATE CS Original Papers and Official Keys o GATE CS 2023 Syllabus o Important Topics for GATE CS o GATE 2023 Important Dates o Other CS Exams # ISRO @ ISRO CS Original Papers and Official Keys @ ISRO CS Solved Papers @ ISRO CS Syllabus for Scientist/Engineer Exam # UGC NET @ UGC NET CS Notes Paper II @ UGC NET CS Notes Paper III @ UGC NET CS Solved Papers + GFG Sheets o Web Dev Cheat Sheets # HTML Cheat Sheet # CSS Cheat Sheet # Bootstrap Cheat Sheet # JS Cheat Sheet # jQuery Cheat Sheet # Angular Cheat Sheet o Company-Wise SDE Sheets # Facebook SDE Sheet # Amazon SDE Sheet # Apple SDE Sheet # Netflix SDE Sheet # Google SDE Sheet # Wipro Coding Sheet # Infosys Coding Sheet # TCS Coding Sheet # Cognizant Coding Sheet # HCL Coding Sheet o DSA Sheets # SDE Sheet # FAANG Coding Sheet # Love Babbar Sheet # Mass Recruiter Sheet # Product-Based Coding Sheet # Company-Wise Preparation Sheet # Array Sheet # String Sheet # Tree Sheet # Graph Sheet # DP Sheet + UPSC o Geography Notes o History Notes o Science & Tech. Notes o Ethics Notes o Polity Notes o Economics Notes o UPSC Previous Year Papers + Student o Campus Ambassador Program o School Ambassador Program o Project o Geek of the Month o Campus Geek of the Month o Placement Course o Competitive Programming o Testimonials o Student Chapter o Geek on the Top o Internship o Careers + SSC CGL o SSC CGL Syllabus o General Studies o English o Reasoning o Subjectwise Practice Papers o Previous Year Papers + Banking Exams o SBI Clerk # SBI Clerk Syllabus # General Awareness # English # Quantitative Aptitude # Reasoning Ability # SBI Clerk Practice Papers o SBI PO # SBI PO Syllabus # General Awareness # English # Quantitative Aptitude # Reasoning Ability # Previous Year Papers # SBI PO Practice Papers o IBPS PO # IBPS PO 2022 Syllabus # English Notes # Reasoning Notes # Previous Year Papers # Mock Question Papers # General Awareness o IBPS Clerk # IBPS Clerk Syllabus # English Notes # Previous Year Papers * Jobs + Corporate Hiring Solutions + Apply through Jobathon + Apply for a Job * Practice + All DSA Problems + Problem of the Day + GFG SDE Sheet + Curated DSA Lists o Top 50 Array Problems o Top 50 String Problems o Top 50 Tree Problems o Top 50 Graph Problems o Top 50 DP Problems * Contests + GFG Weekly Coding Contest + Job-A-Thon: Hiring Challenge + BiWizard School Contest + All Contests and Events * ____________________ (BUTTON) * (BUTTON) * * * Home * Saved Videos * Courses * * GBlog * Puzzles * What's New ? (BUTTON) (BUTTON) Change Language (BUTTON) * DSA * Data Structures * Algorithms * Array * Strings * Linked List * Stack * Queue * Tree * Graph * Searching * Sorting * Recursion * Dynamic Programming * Binary Tree * Binary Search Tree * Heap * Hashing * Divide & Conquer * Mathematical * Geometric * Bitwise * Greedy * Backtracking * Branch and Bound * Matrix * Pattern Searching * Randomized (BUTTON) Related Articles (BUTTON) ^ Get the best out of our app geeksforgeeks GeeksforGeeks App Open App geeksforgeeks Browser Continue Related Articles * Write an Interview Experience * Computer Graphics Basics + Basic Graphic Programming in C++ + Vector vs Raster Graphics + Segments in Computer Graphics + Image Formats Output Primitives + DDA Line generation Algorithm in Computer Graphics + Bresenham's Line Generation Algorithm + Mid-Point Line Generation Algorithm + Program to find line passing through 2 Points + Bresenham's circle drawing algorithm + Anti-aliased Line | Xiaolin Wu's algorithm + Neighbors of a point on a circle using Bresenham's algorithm + Mid-Point Circle Drawing Algorithm + Boundary Fill Algorithm + Flood fill Algorithm - how to implement fill() in paint? + Flood fill algorithm using C graphics + Draw a line in C++ graphics + Draw Rectangle in C graphics + Draw circle in C graphics + Draw a circle without floating point arithmetic + Code to Generate the Map of India (With Explanation) 2-Dimensional Viewing + 2D Transformation in Computer Graphics | Set 1 (Scaling of Objects) + 2D Transformation | Rotation of objects + Point Clipping Algorithm in Computer Graphics + Line Clipping | Set 1 (Cohen-Sutherland Algorithm) + Polygon Clipping | Sutherland-Hodgman Algorithm + Implementation of a Falling Matrix Visible Surface Detection + A-Buffer Method + Z-Buffer or Depth-Buffer method + Back-Face Detection Method 3-Dimension Object Representation + Snowflakes Fractal using Python + Koch Curve or Koch Snowflake + Klee's Algorithm (Length Of Union Of Segments of a line) + Cubic Bezier Curve Implementation in C + Fractals in C/C++ Open GL + Scan-line Polygon filling using OPENGL in C + Rendering a Triangle using OpenGL(using Shaders) + Getting started with OpenGL + OpenGL program for Simple Ball Game + OpenGL program for simple Animation (Revolution) in C + Translation of objects in computer graphics Graphics function in C + pieslice() function in C + outtextxy() function in C + settextstyle function in C + outtext() function in C + setlinestyle() function in C + getx() function in C + sector() function in C + moveto() function in C + gety() function in C + getmaxx() function in C + lineto() function in C + arc function in C + bar3d() function in C graphics + moverel() function in C + cleardevice() function in C + closegraph() function in C + drawpoly() function in C + putpixel() function in C + getarcoords() function in C + getbkcolor() function in C + getmaxcolor() function in C + getpixel() function in C + setcolor function in C + imagesize() function in C + textheight() function in C + textwidth() function in C + grapherrormsg() function in C + fillpoly() function in C + fillellipse() function in C + bar() function in C graphics Misc + How to add "graphics.h" C/C++ library to gcc compiler in Linux + How to include graphics.h in CodeBlocks? + Computer Graphics |Cathode Ray Oscilloscope| Cathode ray tube (video display technology) + High Definition Multimedia Interface (HDMI) + Common Video Format + Audio Format * Write an Interview Experience * Computer Graphics Basics + Basic Graphic Programming in C++ + Vector vs Raster Graphics + Segments in Computer Graphics + Image Formats Output Primitives + DDA Line generation Algorithm in Computer Graphics + Bresenham's Line Generation Algorithm + Mid-Point Line Generation Algorithm + Program to find line passing through 2 Points + Bresenham's circle drawing algorithm + Anti-aliased Line | Xiaolin Wu's algorithm + Neighbors of a point on a circle using Bresenham's algorithm + Mid-Point Circle Drawing Algorithm + Boundary Fill Algorithm + Flood fill Algorithm - how to implement fill() in paint? + Flood fill algorithm using C graphics + Draw a line in C++ graphics + Draw Rectangle in C graphics + Draw circle in C graphics + Draw a circle without floating point arithmetic + Code to Generate the Map of India (With Explanation) 2-Dimensional Viewing + 2D Transformation in Computer Graphics | Set 1 (Scaling of Objects) + 2D Transformation | Rotation of objects + Point Clipping Algorithm in Computer Graphics + Line Clipping | Set 1 (Cohen-Sutherland Algorithm) + Polygon Clipping | Sutherland-Hodgman Algorithm + Implementation of a Falling Matrix Visible Surface Detection + A-Buffer Method + Z-Buffer or Depth-Buffer method + Back-Face Detection Method 3-Dimension Object Representation + Snowflakes Fractal using Python + Koch Curve or Koch Snowflake + Klee's Algorithm (Length Of Union Of Segments of a line) + Cubic Bezier Curve Implementation in C + Fractals in C/C++ Open GL + Scan-line Polygon filling using OPENGL in C + Rendering a Triangle using OpenGL(using Shaders) + Getting started with OpenGL + OpenGL program for Simple Ball Game + OpenGL program for simple Animation (Revolution) in C + Translation of objects in computer graphics Graphics function in C + pieslice() function in C + outtextxy() function in C + settextstyle function in C + outtext() function in C + setlinestyle() function in C + getx() function in C + sector() function in C + moveto() function in C + gety() function in C + getmaxx() function in C + lineto() function in C + arc function in C + bar3d() function in C graphics + moverel() function in C + cleardevice() function in C + closegraph() function in C + drawpoly() function in C + putpixel() function in C + getarcoords() function in C + getbkcolor() function in C + getmaxcolor() function in C + getpixel() function in C + setcolor function in C + imagesize() function in C + textheight() function in C + textwidth() function in C + grapherrormsg() function in C + fillpoly() function in C + fillellipse() function in C + bar() function in C graphics Misc + How to add "graphics.h" C/C++ library to gcc compiler in Linux + How to include graphics.h in CodeBlocks? + Computer Graphics |Cathode Ray Oscilloscope| Cathode ray tube (video display technology) + High Definition Multimedia Interface (HDMI) + Common Video Format + Audio Format Bresenham's Line Generation Algorithm Improve Article (BUTTON) Save Article (BUTTON) Like Article (BUTTON) Read Discuss Courses Practice Video Improve Article (BUTTON) Save Article (BUTTON) Like Article (BUTTON) Given the coordinate of two points A(x1, y1) and B(x2, y2). The task is to find all the intermediate points required for drawing line AB on the computer screen of pixels. Note that every pixel has integer coordinates. Examples: Input : A(0,0), B(4,4) Output : (0,0), (1,1), (2,2), (3,3), (4,4) Input : A(0,0), B(4,2) Output : (0,0), (1,0), (2,1), (3,1), (4,2) Below are some assumptions to keep the algorithm simple. 1. We draw lines 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. Naive Approach: C++ // A naive way of drawing line void naiveDrawLine(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); for (x = x1; x <= x2; x++) { // Assuming that the round function finds // closest integer to a given float. y = round(mx + c); print(x, y); } } Java /*package whatever //do not write package name here */ import java.io.*; class GFG { // A naive way of drawing line public static void naiveDrawLine(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); for (x = x1; x <= x2; x++) { // Assuming that the round function finds // closest integer to a given float. y = round(mx + c); print(x, y); } } public static void main(String[] args) {} } // This code is contributed by akashish__ Python3 # A naive way of drawing line def naiveDrawLine(x1, x2, y1, y2): m = (y2 - y1) / (x2 - x1) # for (x = x1; x <= x2; x++) { for x in range(x1, x2 + 1): # Assuming that the round function finds # closest integer to a given float. y = round(mx + c) print(x, y) # This code is contributed by akashish__ C# using System; public class GFG { // A naive way of drawing line public static void naiveDrawLine(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); for (x = x1; x <= x2; x++) { // Assuming that the round function finds // closest integer to a given float. y = round(mx + c); print(x, y); } } static public void Main() { // Code } } // This code is contributed by akashish__ Javascript // A naive way of drawing line function naiveDrawLine(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); for (x = x1; x <= x2; x++) { // Assuming that the round function finds // closest integer to a given float. y = Math.round(mx + c); print(x, y); } } // This code is contributed by garg28harsh. The above algorithm works, but it is slow. The idea of Bresenham's algorithm is to avoid floating point multiplication and addition to compute mx + c, and then compute the round value of (mx + c) in every step. In Bresenham's algorithm, we move across the x-axis in unit intervals. We always increase x by 1, and we choose about next y, whether we need to go to y+1 or remain on y. In other words, from any position (X[k], Y[k]) we need to choose between (X[k] + 1, Y[k]) and (X[k] + 1, Y[k] + 1). Bresenham's Line Generation Algorithm We would like to pick the y value (among Y[k] + 1 and Y[k]) corresponding to a point that is closer to the original line. We need a decision parameter to decide whether to pick Y[k] + 1 or Y[k] as the next point. The idea is to keep track of slope error from the previous increment to y. If the slope error becomes greater than 0.5, we know that the line has moved upwards one pixel and that we must increment our y coordinate and readjust the error to represent the distance from the top of the new pixel - which is done by subtracting one from the error. C++ // Modifying the naive way to use a parameter // to decide next y. void withDecisionParameter(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); slope_error = [Some Initial Value]; for (x = x1, y = y1; x = 0.5) { y++; slope_error -= 1.0; } } Java /*package whatever //do not write package name here */ import java.io.*; class GFG { // Modifying the naive way to use a parameter // to decide next y. public static void withDecisionParameter(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); slope_error = [Some Initial Value]; for (x = x1, y = y1; x = 0.5) { y++; slope_error -= 1.0; } } public static void main (String[] args) { } } // This code is contributed by akashish__ Python3 # Modifying the naive way to use a parameter # to decide next y. def withDecisionParameter(x1, x2, y1, y2): m = (y2 - y1) / (x2 - x1) slope_error = [Some Initial Value] for x in range(0.5,x1) and y in range(y1): y += 1 slope_error -= 1.0 # This code is contributed by akashish__ C# using System; public class GFG { // Modifying the naive way to use a parameter // to decide next y. public static void withDecisionParameter(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); slope_error = [ Some Initial Value ]; for (x = x1, y = y1; x = 0.5) { y++; slope_error -= 1.0; } } static public void Main() {} } // This code is contributed by akashish__ Javascript // Modifying the naive way to use a parameter // to decide next y. function withDecisionParameter(x1, x2, y1, y2) { m = (y2 - y1) / (x2 - x1); slope_error = [Some Initial Value]; for (x = x1, y = y1; x = 0.5) { y++; slope_error -= 1.0; } } // This code is contributed by akashish__ How to avoid floating point arithmetic The above algorithm still includes floating point arithmetic. To avoid floating point arithmetic, consider the value below value m. * m = (y2 - y1)/(x2 - x1) * We multiply both sides by (x2 - x1) * We also change slope_error to slope_error * (x2 - x1). To avoid comparison with 0.5, we further change it to slope_error * (x2 - x1) * 2. * Also, it is generally preferred to compare with 0 than 1. C++ // Modifying the above algorithm to avoid floating // point arithmetic and use comparison with 0. void bresenham(x1, x2, y1, y2) { m_new = 2 * (y2 - y1) slope_error_new = [Some Initial Value] for (x = x1, y = y1; x = 0) { y++; slope_error_new -= 2 * (x2 - x1); } } Java public static void bresenham(int x1, int x2, int y1, int y2) { int m_new = 2 * (y2 - y1); int slope_error_new = 0; for (int x = x1, y = y1; x = 0 { y++; slope_error_new -= 2 * (x2 - x1); } } // This code is contributed by ishankhandelwals. Python3 # Modifying the above algorithm to avoid floating # point arithmetic and use comparison with 0. def bresenham(x1, x2, y1, y2): m_new = 2 * (y2 - y1) slope_error_new = 0 y = y1 for x in range(x1, 0, -1) { y += 1 slope_error_new -= 2 * (x2 - x1) # This code is contributed by akashish__ C# using System; public class GFG{ // Modifying the above algorithm to avoid floating // point arithmetic and use comparison with 0. public static void bresenham(x1, x2, y1, y2) { m_new = 2 * (y2 - y1); slope_error_new = [Some Initial Value]; for (int x = x1,int y = y1; x = 0) { y++; slope_error_new -= 2 * (x2 - x1); } } static public void Main (){ // Code } } // This code is contributed by akashish__ Javascript // Modifying the above algorithm to avoid floating // point arithmetic and use comparison with 0. function bresenham(x1, x2, y1, y2) { let m_new = 2 * (y2 - y1); let slope_error_new = 0; for (let x = x1, let y = y1; x = 0) { y++; slope_error_new -= 2 * (x2 - x1); } } // This code is contributed by akashish__ The initial value of slope_error_new is 2*(y2 - y1) - (x2 - x1). Refer to this for proof of this value Below is the implementation of the 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 << ")\n"; // 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 int main() { int x1 = 3, y1 = 2, x2 = 15, y2 = 5; // Function call 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 + ")\n & quot;); // 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& gt; = 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; // Function call 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, ")\n") # 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 code if __name__ == '__main__': x1 = 3 y1 = 2 x2 = 15 y2 = 5 # Function call 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 + ")\n & quot;); // 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& gt; = 0) { y++; slope_error_new -= 2 * (x2 - x1); } } } // Driver code public static void Main() { int x1 = 3, y1 = 2, x2 = 15, y2 = 5; // Function call 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, ")\n"; // 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; // Function call bresenham($x1, $y1, $x2, $y2); // This code is contributed by nitin mittal. ?> Javascript // 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 Output (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) Time Complexity: O(x2 - x1) Auxiliary Space: O(1) The above explanation is to provide a rough idea behind the algorithm. For detailed explanation and proof, readers can refer below references. The above program only works if the slope of the line is less than 1. Here is a program implementation for any kind of slope. C++ // C++ program for Bresenhams Line Generation #include <bits/stdc++.h> using namespace std; void plotPixel(int x1, int y1, int x2, int y2, int dx, int dy, int decide) { // pk is initial decision making parameter // Note:x1&y1;,x2&y2;, dx&dy; values are interchanged // and passed in plotPixel function so // it can handle both cases when m>1 & m<1 int pk = 2 * dy - dx; for (int i = 0; i <= dx; i++) { cout << x1 << "," << y1 << endl; // checking either to decrement or increment the // value if we have to plot from (0,100) to (100,0) x1 < x2 ? x1++ : x1--; if (pk < 0) { // decision value will decide to plot // either x1 or y1 in x's position if (decide == 0) { // putpixel(x1, y1, RED); pk = pk + 2 * dy; } else { //(y1,x1) is passed in xt // putpixel(y1, x1, YELLOW); pk = pk + 2 * dy; } } else { y1 < y2 ? y1++ : y1--; if (decide == 0) { // putpixel(x1, y1, RED); } else { // putpixel(y1, x1, YELLOW); } pk = pk + 2 * dy - 2 * dx; } } } // Driver code int main() { int x1 = 100, y1 = 110, x2 = 125, y2 = 120, dx, dy, pk; dx = abs(x2 - x1); dy = abs(y2 - y1); // If slope is less than one if (dx > dy) { // passing argument as 0 to plot(x,y) plotPixel(x1, y1, x2, y2, dx, dy, 0); } // if slope is greater than or equal to 1 else { // passing argument as 1 to plot (y,x) plotPixel(y1, x1, y2, x2, dy, dx, 1); } } Java // Java program for Bresenhams Line Generation import java.io.*; import java.lang.Math; class GFG { public static void plotPixel(int x1, int y1, int x2, int y2, int dx, int dy, int decide) { // pk is initial decision making parameter // Note:x1&y1;,x2&y2;, dx&dy; values are interchanged // and passed in plotPixel function so // it can handle both cases when m>1 & m<1 int pk = 2 * dy - dx; for (int i = 0; i <= dx; i++) { System.out.println(x1 + "," + y1 + "\n"); // checking either to decrement or increment the // value if we have to plot from (0,100) to // (100,0) if (x1 < x2) x1++; else x1--; if (pk < 0) { // decision value will decide to plot // either x1 or y1 in x's position if (decide == 0) { pk = pk + 2 * dy; } else pk = pk + 2 * dy; } else { if (y1 < y2) y1++; else y1--; pk = pk + 2 * dy - 2 * dx; } } } // Driver code public static void main(String[] args) { int x1 = 100, y1 = 110, x2 = 125, y2 = 120, dx, dy, pk; dx = Math.abs(x2 - x1); dy = Math.abs(y2 - y1); // If slope is less than one if (dx > dy) { // passing argument as 0 to plot(x,y) plotPixel(x1, y1, x2, y2, dx, dy, 0); } // if slope is greater than or equal to 1 else { // passing argument as 1 to plot (y,x) plotPixel(y1, x1, y2, x2, dy, dx, 1); } } } // This code is contributed by kothavvsaakash Python3 # Python3 program for Bresenhams Line Generation def plotPixel(x1, y1, x2, y2, dx, dy, decide): # pk is initial decision making parameter # Note:x1&y1;,x2&y2;, dx&dy; values are interchanged # and passed in plotPixel function so # it can handle both cases when m>1 & m<1 pk = 2 * dy - dx # for (int i = 0; i <= dx; i++) { for i in range(0,dx+1): print(x1,",",y1) # checking either to decrement or increment the # value if we have to plot from (0,100) to (100,0) if(x1<x2): x1 = x1 + 1 else: x1 = x1 - 1 if (pk < 0): # decision value will decide to plot # either x1 or y1 in x's position if (decide == 0): # putpixel(x1, y1, RED); pk = pk + 2 * dy else: #(y1,x1) is passed in xt # putpixel(y1, x1, YELLOW); pk = pk + 2 * dy else: if(y1<y2): y1 = y1 + 1 else: y1 = y1 - 1 # if (decide == 0): # # putpixel(x1, y1, RED) # else: # # putpixel(y1, x1, YELLOW); pk = pk + 2 * dy - 2 * dx # Driver code x1 = 100 y1 = 110 x2 = 125 y2 = 120 dx = abs(x2 - x1) dy = abs(y2 - y1) # If slope is less than one if (dx > dy): # passing argument as 0 to plot(x,y) plotPixel(x1, y1, x2, y2, dx, dy, 0) # if slope is greater than or equal to 1 else: # passing argument as 1 to plot (y,x) plotPixel(y1, x1, y2, x2, dy, dx, 1) # This code is contributed by akashish__ C# // C# program for Bresenhams Line Generation using System; class GFG { static public void plotPixel(int x1, int y1, int x2, int y2, int dx, int dy, int decide) { // pk is initial decision making parameter // Note:x1&y1;,x2&y2;, dx&dy; values are interchanged // and passed in plotPixel function so // it can handle both cases when m>1 & m<1 int pk = 2 * dy - dx; for (int i = 0; i <= dx; i++) { Console.Write(x1 + "," + y1 + "\n"); // checking either to decrement or increment the // value if we have to plot from (0,100) to // (100,0) if (x1 < x2) x1++; else x1--; if (pk < 0) { // decision value will decide to plot // either x1 or y1 in x's position if (decide == 0) { pk = pk + 2 * dy; } else pk = pk + 2 * dy; } else { if (y1 < y2) y1++; else y1--; pk = pk + 2 * dy - 2 * dx; } } } // Driver code static public void Main() { int x1 = 100, y1 = 110, x2 = 125, y2 = 120, dx, dy; dx = Math.Abs(x2 - x1); dy = Math.Abs(y2 - y1); // If slope is less than one if (dx > dy) { // passing argument as 0 to plot(x,y) plotPixel(x1, y1, x2, y2, dx, dy, 0); } // if slope is greater than or equal to 1 else { // passing argument as 1 to plot (y,x) plotPixel(y1, x1, y2, x2, dy, dx, 1); } } } // This code is contributed by kothavvsaakash Javascript // Javascript program for Bresenhams Line Generation function plotPixel(x1, y1, x2, y2, dx, dy, decide) { // pk is initial decision making parameter // Note:x1&y1;,x2&y2;, dx&dy; values are interchanged // and passed in plotPixel function so // it can handle both cases when m>1 & m<1 let pk = 2 * dy - dx; for (let i = 0; i <= dx; i++) { console.log(x1 + "," + y1); // checking either to decrement or increment the // value if we have to plot from (0,100) to // (100,0) if (x1 < x2) x1++; else x1--; if (pk < 0) { // decision value will decide to plot // either x1 or y1 in x's position if (decide == 0) { pk = pk + 2 * dy; } else pk = pk + 2 * dy; } else { if (y1 < y2) y1++; else y1--; pk = pk + 2 * dy - 2 * dx; } } } // Driver code let x1 = 100, y1 = 110, x2 = 125, y2 = 120, dx, dy; dx = Math.abs(x2 - x1); dy = Math.abs(y2 - y1); // If slope is less than one if (dx > dy) { // passing argument as 0 to plot(x,y) plotPixel(x1, y1, x2, y2, dx, dy, 0); } // if slope is greater than or equal to 1 else { // passing argument as 1 to plot (y,x) plotPixel(y1, x1, y2, x2, dy, dx, 1); } // This code is contributed by akashish__ Output 100,110 101,110 102,111 103,111 104,112 105,112 106,112 107,113 108,113 109,114 110,114 111,114 112,115 113,115 114,116 115,116 116,116 117,117 118,117 119,118 120,118 121,118 122,119 123,119 124,120 125,120 Related Articles: 1. Mid-Point Line Generation Algorithm 2. DDA algorithm for line drawing This article is contributed by Shivam Pradhan (anuj_charm). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. Recommended Solve DSA problems on GfG Practice. Solve Problems My Personal Notes arrow_drop_up _______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________ (BUTTON) Save Last Updated : 20 Jan, 2023 Like Article (BUTTON) Save Article (BUTTON) Please Login to comment... Similar Reads 1. Comparisons between DDA and Bresenham Line Drawing algorithm 2. Illustration for tracing all the 8 octaves in Bresenham's line algorithm 3. Bresenham's Algorithm for 3-D Line Drawing 4. Bresenham's circle drawing algorithm 5. Neighbors of a point on a circle using Bresenham's algorithm 6. Mid-Point Line Generation Algorithm 7. DDA Line generation Algorithm in Computer Graphics 8. Draw circle using polar equation and Bresenham's equation 9. Scan conversion of Line and Line Drawing algorithms 10. Scan conversion methods of circle and circle generation algorithms Related Tutorials 1. Learn Data Structures with Javascript | DSA Tutorial 2. Introduction to Max-Heap - Data Structure and Algorithm Tutorials 3. Introduction to Set - Data Structure and Algorithm Tutorials 4. Introduction to Map - Data Structure and Algorithm Tutorials 5. What is Dijkstra's Algorithm? | Introduction to Dijkstra's Shortest Path Algorithm (BUTTON) Like Previous DDA Line generation Algorithm in Computer Graphics Next Mid-Point Line Generation Algorithm Article Contributed By : https://media.geeksforgeeks.org/auth/avatar.png GeeksforGeeks Vote for difficulty Current difficulty : Hard (BUTTON) Easy (BUTTON) Normal (BUTTON) Medium (BUTTON) Hard (BUTTON) Expert Improved By : * nitin mittal * ash264 * gurrrung * amit143katiyar * simmytarika5 * surinderdawra388 * pankajsharmagfg * kothavvsaakash * ishankhandelwals * ozonewagle998 * garg28harsh * akashish__ * janardansthox Article Tags : * computer-graphics * Algorithms * DSA Practice Tags : * Algorithms Report Issue Courses course-img 899k+ interested Geeks Data Structures and Algorithms - Self Paced Beginner to Advance course-img 798k+ interested Geeks Complete Interview Preparation - Self Paced Beginner to Advance course-img 42k+ interested Geeks GATE CS & IT 2024 Beginner to Advance Improve your Coding Skills with Practice (BUTTON) Try It! geeksforgeeks-footer-logo A-143, 9th Floor, Sovereign Corporate Tower, Sector-136, Noida, Uttar Pradesh - 201305 feedback@geeksforgeeks.org * Company * About Us * Careers * In Media * Contact Us * Terms and Conditions * Privacy Policy * Copyright Policy * Third-Party Copyright Notices * Advertise with us * Languages * Python * Java * C++ * GoLang * SQL * R Language * Android Tutorial * Data Structures * Array * String * Linked List * Stack * Queue * Tree * Graph * Algorithms * Sorting * Searching * Greedy * Dynamic Programming * Pattern Searching * Recursion * Backtracking * Web Development * HTML * CSS * JavaScript * Bootstrap * ReactJS * AngularJS * NodeJS * Write & Earn * Write an Article * Improve an Article * Pick Topics to Write * Write Interview Experience * Internships * Video Internship * Computer Science * GATE CS Notes * Operating Systems * Computer Network * Database Management System * Software Engineering * Digital Logic Design * Engineering Maths * Data Science & ML * Data Science With Python * Data Science For Beginner * Machine Learning Tutorial * Maths For Machine Learning * Pandas Tutorial * NumPy Tutorial * NLP Tutorial * Interview Corner * Company Preparation * Preparation for SDE * Company Interview Corner * Experienced Interview * Internship Interview * Competitive Programming * Aptitude * Python * Python Tutorial * Python Programming Examples * Django Tutorial * Python Projects * Python Tkinter * OpenCV Python Tutorial * GfG School * CBSE Notes for Class 8 * CBSE Notes for Class 9 * CBSE Notes for Class 10 * CBSE Notes for Class 11 * CBSE Notes for Class 12 * English Grammar * UPSC/SSC/ BANKING * SSC CGL Syllabus * SBI PO Syllabus * IBPS PO Syllabus * UPSC Ethics Notes * UPSC Economics Notes * UPSC History Notes @geeksforgeeks , Some rights reserved We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy (BUTTON) Got It ! Lightbox Improvement This article is being improved by another user right now. You can suggest the changes for now and it will be under the article's discussion tab. You will be notified via email once the article is available for improvement. Thank you for your valuable feedback! (BUTTON) Suggest changes Suggest Changes Suggestion [CharLimit:2000] _______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________ (BUTTON)