Program to Draw Line Using Dda Algorithm in C++

Mid-Point Line Generation Algorithm in C++

---

A line connects two points. It is a basic element in graphics. To draw a line, you need two points between which you can draw a line on a screen and in terms of graphics we refer to the points as pixels and every pixel is associated with integer coordinates. We are given integer coordinates in the form of (x1, y1) and (x2, y2) where, x1 < x2 and y1 < y2. The task is to calculate all the mid-points between point 1 i.e. (x1, y1) and point 2 i.e. (x2, y2) using the Midpoint Line Generation Algorithm.

There are three different algorithms which are being used to perform Line generation on a screen and those are −

• DDA Algorithm

• Bresenham's Line Generation

• Mid-Point Algorithm

Mid-Point Algorithm

Steps to draw line using Mid-Point Line Algorithm are-

• Calculate the middle point using the current located points i.e. East(Xp+1, Yp) and North East(Xp+1, Yp+1) is Middle point(Xp+1, Yp+1/2).

• Now, Middle point will decide the location for the next coordinate on the screen i.e.

  • IF the middle point is above the line, then the next coordinate will be at the EAST.

  • IF the middle point is below the line, then the next coordinate will be at the NORTH EAST.

Let us see various input output scenarios for this -

In− int x_1 = 3, int y_1 = 3, int x_2 = 10, int y_2 = 8

Out− Mid-Points through Line Generation Algorithm are: 3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8

Explanation− we are given with coordinates as x_1 = 3, x_2 = 10, y_1 = 3, y_2 = 8. So, the steps will be firstly to calculate dx = x_2 - x_1 as 10 - 3 = 7 and dy as y_2 - y_1 as 8 - 3 = 5 and then check if the dy is less than dx. Now calculate the d as 5 - (7 / 2) = 2. The first point will be x_1 and y_1. Print them. Now, while x_1 < x_2 then keep increasing the x_1 by 1 and check if d less than 0 then set d as d + dy ELSE, set d as d + (dy - dx) and increase the x_2 by 1.

In− int x_1 = 2, int y_1 = 2, int x_2 = 3, int y_2 = 4

Out− Mid-Points through Line Generation Algorithm are: 2,2 3,3 3,4

Explanation− we are given with coordinates as x_1 = 2, x_2 = 2, y_1 = 3, y_2 = 4. So, by applying the mid-point line generation algorithm we will calculate all the mid-points pixels as an output.

Approach used in the below program is as follows

• Input integer points as int x_1, int y_1, int x_2, int y_2. Call the function as Mid_Point(x_1, y_1, x_2, y_2) to generate the line.

• Inside the function Mid_Point(x_1, y_1, x_2, y_2)

  • Calculate the dx as x_2 - x_1 and dy as y_2 - y_1

  • Check IF dy is less than or equals to dx then set d as dy - (dx / 2) and set first_pt to x_1 and second_pt to y_1

  • Print the first_pt and second_pt.

  • Start while first_pt less than x_2 then increment the first_pt by 1 and check IF d less than 0 then set d to d + dy ELSE, set d to d + (dy - dx) and increment the second_pt by 1. Print the first_pt and second_pt.

  • Else If dx less than dy then set d to dx - (dy/2) and set first_pt to x_1 and second_pt to y_1 and print the first_pt and second_pt.

  • Start WHILE second_pt less than y_2. Inside the WHILE, increment the second_pt by 1. Check IF d less than 0 then set d to d + dx. ELSE, d to d + (dx - dy) and increment the first_pt by 1.

  • Print the first_pt and second_pt.

Example

#include<bits/stdc++.h> using namespace std;  void Mid_Point(int x_1, int y_1, int x_2, int y_2){    int dx = x_2 - x_1;    int dy = y_2 - y_1;     if(dy <= dx){       int d = dy - (dx / 2);       int first_pt = x_1;       int second_pt = y_1;        cout<< first_pt << "," << second_pt << "\n";       while(first_pt < x_2){          first_pt++;          if(d < 0){             d = d + dy;          }          else{             d = d + (dy - dx);             second_pt++;          }             cout << first_pt << "," << second_pt << "\n";       }    }    else if(dx < dy){       int d = dx - (dy/2);       int first_pt = x_1;       int second_pt = y_1;       cout << first_pt << "," << second_pt << "\n";       while(second_pt < y_2){          second_pt++;          if(d < 0){             d = d + dx;          }          else{             d += (dx - dy);             first_pt++;          }          cout << first_pt << "," << second_pt << "\n";       }    } } int main(){    int x_1 = 3;    int y_1 = 3;    int x_2 = 10;    int y_2 = 8;    cout<<"Mid-Points through Line Generation Algorithm are: ";    Mid_Point(x_1, y_1, x_2, y_2);    return 0; }

Output

If we run the above code it will generate the following Output

Mid-Points through Line Generation Algorithm are: 3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8

Published on 22-Oct-2021 07:49:54

• Related Questions & Answers
• Program to find the mid-point of a line in C++
• Point Clipping Algorithm in Computer Graphics in C++
• C++ Program to Implement Park-Miller Random Number Generation Algorithm
• Mid-Square hashing in C++.
• Random number generation in C++
• Gaussian Filter Generation in C++
• Write a one line C function to round floating point numbers
• C++ Program to Show the Duality Transformation of Line and Point
• Python program to find angle between mid-point and base of a right angled triangle
• Difference Between DDA and Bresenham Line Drawing algorithm
• Find Corners of Rectangle using mid points in C++
• Klee's Algorithm (Length Of Union Of Segments of a line) in C++
• Find foot of perpendicular from a point in 2D plane to a Line in C++
• Rotation of a point about another point in C++
• Z algorithm (Linear time pattern searching Algorithm) in C++

Program to Draw Line Using Dda Algorithm in C++

Source: https://www.tutorialspoint.com/mid-point-line-generation-algorithm-in-cplusplus

Share this post