C++ implementation of midpoint line generation algorithm

A line connects two points. It is a basic element in graphics. To draw a line you need two points and you draw a line between these two points on the screen, in terms of graphics we call these points pixels and each pixel is associated with an integer coordinate. We give integer coordinates in the form (x1, y1) and (x2, y2) where x1

Three different algorithms are being used with For performing line generation on the screen, these are-

• DDA Algorithm

• Bresenham Line Generation

• Midpoint Algorithm

Midpoint Algorithm

The steps to draw a line using the midpoint The point-line algorithm is-

• Use The current positioning point calculates the middle point, that is, east (Xp 1, Yp) and northeast (Xp 1, Yp) 1) is the middle point (Xp 1, Yp 1/2).

• Now the midpoint will determine the location of the next coordinate on the screen i.e. p>

  • If the midpoint is above the line then the next coordinate will be east.

  • If the midpoint is below the line, then the next coordinate will be in the northeast.

Let us look at various input and output scenarios this-

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

output

output

Explanation− The coordinates we give are x_1 = 3, x_2 = 10, y_1 = 3, y_2 = 8. So the steps first calculate dx = x_2 - x_1 as 10 - 3 = 7 and dy as y_2 - y_1 8 - 3 = 5 and Then check if dy is less than dx. Now calculate d as 5 - (7 / 2) = 2. The first points are x_1 and y_1. Print them. Now, when x_1

Input: int x_1 = 2, int y_1 = 2, int x_2 = 3, int y_2 = 4

Output: Generated from line segments The midpoint obtained by the algorithm is: 2,2 3,3 3,4

Explanation: The given coordinates are x_1 = 2, x_2 = 2, y_1 = 3, y_2 = 4. By applying the midpoint segment generation algorithm, we will calculate all midpoint pixels as output.

The method used in the following program is as follows:

• The input integer points are int x_1, int y_1, int x_2, int y_2. Call the function Mid_Point(x_1, y_1, x_2, y_2) to generate a line segment.

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

  • Calculate dx as x_2 - x_1, dy as y_2 - y_1

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

  • Print first_pt and second_pt.

  • Start the while loop, when first_pt is less than x_2, increase first_pt 1, and check IF d is less than 0, then set d to d dy, otherwise set d to d (dy - dx) and increase second_pt by 1. Print first_pt and second_pt.

  • Otherwise, if dx is less than dy, set d to dx - (dy/2), set first_pt to x_1, set second_pt to y_1, and print first_pt and second_pt.

  • Start the while loop. When second_pt is less than y_2, increment second_pt inside the loop. second_pt is incremented by 1. Check IF d is less than 0 and set d to d dx. Otherwise, set d to d (dx - dy) and increase first_pt by 1.

  • Print 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

The above is the detailed content of C++ implementation of midpoint line generation algorithm. For more information, please follow other related articles on the PHP Chinese website!