Implement the Bresenham’s algorithm to draw the line. Generalize it for co-ordinates in C language

 

Bresenham’s Line Drawing Algorithm and Implementation in C Language

The Bresenham’s Line Drawing Algorithm is an efficient method to draw a straight line between two given points on a pixel-based screen. Unlike the Digital Differential Analyzer (DDA) algorithm, which uses floating-point arithmetic, Bresenham’s algorithm uses only integer arithmetic, making it faster and more suitable for real-time applications.

---

Concept Behind Bresenham's Algorithm

Given two points $(x_1,y_1)$and $(x_2,y_2)$, the task is to draw a line between these points by determining which pixels on a screen should be illuminated.

To achieve this, Bresenham’s algorithm uses a decision parameter that helps decide which pixel to plot at each step while incrementally traversing from the starting point to the endpoint.

---

How Bresenham’s Algorithm Works

1. Calculate dx and dy:

   • $dx=x_2-x_1$

   • $dy=y_2-y_1$
     These values represent the differences between the x and y coordinates.

2. Set up the initial decision parameter:

   • Let the initial decision parameter $p=2dy-dx$. This parameter will help decide which pixel to plot next.

3. Determine pixel selection at each step:

   • Start from the point $(x_1,y_1)$

   • For each x-coordinate from $x_1$ to $x_2$, check the value of the decision parameter $p$:

     • If $p<0$, the next point to plot is $(x+1,y)$, and update $p$ as:

       $$p=p+2dy$$

     • If $p\ge 0$, the next point to plot is $(x+1,y+1)$, and update $p$ as:

       $$p=p+2dy-2dx$$

   • Repeat this process until you reach $(x_2,y_2)$.

---

Step-by-Step Process for Bresenham's Line Drawing Algorithm

Given two points $(x_1,y_1)$ and $(x_2,y_2)$:

1. Calculate dx and dy:

   • $dx=x_2-x_1$

   • $dy=y_2-y_1$

2. Initialize the decision parameter $p$:

   • $p=2dy-dx$

3. Initialize starting point:

   • Set $x=x_1$, $y=y_1$

4. Iterate and Plot the Line:

   • For each x from $x_1$ to $x_2$, check the decision parameter $p$:

     • If $p<0$, plot $(x+1,y)$, and update $p$ as $p=p+2dy$.

     • If $p\ge 0$, plot $(x+1,y+1)$, and update $p$ as $p=p+2dy-2dx$

---

Implementation of Bresenham's Algorithm in C

#include <stdio.h>
#include <stdlib.h>

void bresenhamLine(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int p = 2 * dy - dx; // Decision parameter
    int twoDy = 2 * dy;
    int twoDyDx = 2 * (dy - dx);

    int x, y, xEnd;

    // Determine which point to start with
    if (x1 > x2) {
        x = x2;
        y = y2;
        xEnd = x1;
    } else {
        x = x1;
        y = y1;
        xEnd = x2;
    }

    printf("The points on the line are:\n");
    printf("(%d, %d)\n", x, y); // Plot the first point

    // Iterate and plot the line
    while (x < xEnd) {
        x++; // Increment x

        if (p < 0) {
            // If decision parameter is negative, only x changes
            p += twoDy;
        } else {
            // If decision parameter is positive, both x and y change
            y++;
            p += twoDyDx;
        }

        printf("(%d, %d)\n", x, y); // Plot the calculated point
    }
}

int main() {
    int x1, y1, x2, y2;

    // Input coordinates
    printf("Enter coordinates (x1, y1): ");
    scanf("%d %d", &x1, &y1);
    printf("Enter coordinates (x2, y2): ");
    scanf("%d %d", &x2, &y2);

    // Draw line using Bresenham's algorithm
    bresenhamLine(x1, y1, x2, y2);

    return 0;
}

---

Explanation of Code:

1. Calculate dx, dy, and Initial Decision Parameter $p$

   • dx = abs(x2 - x1) and dy = abs(y2 - y1)

   • Initial decision parameter p is set to 2dy - dx.

2. Decide the Starting and Ending Points:

   • If $x_1>x_2$, start plotting from $(x_2,y_2)$. Otherwise, start from $(x_1,y_1)$.

3. Loop to Plot the Line:

   • The algorithm iterates through the x-coordinates and plots the appropriate y-coordinate based on the decision parameter $p$.

   • The decision parameter is updated at each step depending on whether it is positive or negative.

4. Output the Plotted Points:

   • Each plotted point $(x,y)$ is printed to the console.

---

Advantages of Bresenham’s Algorithm:

1. Efficient and Fast:

   • It uses only integer calculations (no floating-point arithmetic), making it computationally efficient.

2. Better Accuracy:

   • It produces a more accurate approximation of a straight line on pixel-based displays.

3. Handles Different Slopes:

   • The algorithm can handle lines with different slopes and directions (both positive and negative slopes).

---

Disadvantages of Bresenham’s Algorithm:

1. Limited to Lines:

   • This algorithm is specifically designed for line drawing and cannot be easily generalized for drawing curves or circles.

2. Requires More Conditions for Steep Slopes:

• Additional modifications are needed to handle steep slopes correctly (i.e., when $dy > dx$).

Implementation of Bresenham's Algorithm in C

#include <stdio.h>
#include <stdlib.h>

void bresenhamLine(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int p = 2 * dy - dx; // Decision parameter
    int twoDy = 2 * dy;
    int twoDyDx = 2 * (dy - dx);

    int x, y, xEnd;

    // Determine which point to start with
    if (x1 > x2) {
        x = x2;
        y = y2;
        xEnd = x1;
    } else {
        x = x1;
        y = y1;
        xEnd = x2;
    }

    printf("The points on the line are:\n");
    printf("(%d, %d)\n", x, y); // Plot the first point

    // Iterate and plot the line
    while (x < xEnd) {
        x++; // Increment x

        if (p < 0) {
            // If decision parameter is negative, only x changes
            p += twoDy;
        } else {
            // If decision parameter is positive, both x and y change
            y++;
            p += twoDyDx;
        }

        printf("(%d, %d)\n", x, y); // Plot the calculated point
    }
}

int main() {
    int x1, y1, x2, y2;

    // Input coordinates
    printf("Enter coordinates (x1, y1): ");
    scanf("%d %d", &x1, &y1);
    printf("Enter coordinates (x2, y2): ");
    scanf("%d %d", &x2, &y2);

    // Draw line using Bresenham's algorithm
    bresenhamLine(x1, y1, x2, y2);

    return 0;
}