---------------------------------------------------------------------------------------
.
---------------------------------------------------------------------------------------
#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)
---------------------------------------------------------------------------------------