อัลกอริทึมการสร้างเส้นกึ่งกลางใน C++

เส้นเชื่อมต่อสองจุด เป็นองค์ประกอบพื้นฐานในกราฟิก ในการวาดเส้น คุณต้องมีจุดสองจุดระหว่างนั้นคุณสามารถวาดเส้นบนหน้าจอและในแง่ของกราฟิก เราเรียกจุดนั้นว่าเป็นพิกเซล และทุกพิกเซลเชื่อมโยงกับพิกัดจำนวนเต็ม เราได้รับพิกัดจำนวนเต็มในรูปแบบของ (x1, y1) และ (x2, y2) โดยที่ x1

มีสามอัลกอริธึมที่แตกต่างกันซึ่งถูกใช้เพื่อสร้างเส้นบนหน้าจอและอัลกอริธึมเหล่านี้คือ −

• อัลกอริธึม DDA

• การสร้างไลน์ของ Bresenham

• อัลกอริทึมจุดกึ่งกลาง

อัลกอริทึมจุดกึ่งกลาง

ขั้นตอนในการวาดเส้นโดยใช้ Mid-Point Line Algorithm are-

• คำนวณจุดกึ่งกลางโดยใช้จุดที่อยู่ปัจจุบัน เช่น East(Xp+1, Yp) และ North East(Xp+1, Yp+1) คือจุดกลาง(Xp+1, Yp+1/2)

• ตอนนี้ จุดกึ่งกลางจะกำหนดตำแหน่งสำหรับพิกัดถัดไปบนหน้าจอ เช่น

  • หากจุดกึ่งกลางอยู่เหนือเส้น พิกัดถัดไปจะอยู่ที่ทิศตะวันออก

  • หากจุดกึ่งกลางอยู่ใต้เส้น พิกัดถัดไปจะอยู่ที่ทิศตะวันออกเฉียงเหนือ

ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -

ใน − int x_1 =3, int y_1 =3, int x_2 =10, int y_2 =8

ออก − จุดกึ่งกลางผ่านอัลกอริธึมการสร้างไลน์คือ:3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8

คำอธิบาย − เราได้รับพิกัดเป็น x_1 =3, x_2 =10, y_1 =3, y_2 =8 ดังนั้น ขั้นตอนแรกในการคำนวณ dx =x_2 - x_1 เป็น 10 - 3 =7 และ dy เป็น y_2 - y_1 เป็น 8 - 3 =5 แล้วตรวจสอบว่า dy น้อยกว่า dx หรือไม่ ตอนนี้คำนวณ d เป็น 5 - (7 / 2) =2 จุดแรกจะเป็น x_1 และ y_1 พิมพ์พวกเขา ตอนนี้ในขณะที่ x_1

ใน − int x_1 =2, int y_1 =2, int x_2 =3, int y_2 =4

ออก − จุดกึ่งกลางผ่านอัลกอริธึมการสร้างไลน์คือ:2,2 3,3 3,4

คำอธิบาย − เราได้รับพิกัดเป็น x_1 =2, x_2 =2, y_1 =3, y_2 =4 ดังนั้น เมื่อใช้อัลกอริธึมการสร้างเส้นจุดกึ่งกลาง เราจะคำนวณพิกเซลจุดกึ่งกลางทั้งหมดเป็นผลลัพธ์

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนจุดจำนวนเต็มเป็น int x_1, int y_1, int x_2, int y_2 เรียกใช้ฟังก์ชันเป็น Mid_Point(x_1, y_1, x_2, y_2) เพื่อสร้างเส้น

• ภายในฟังก์ชัน Mid_Point(x_1, y_1, x_2, y_2)

  • คำนวณ dx เป็น x_2 - x_1 และ dy เป็น y_2 - y_1

  • ตรวจสอบว่า dy น้อยกว่าหรือเท่ากับ dx แล้วตั้งค่า d เป็น dy - (dx / 2) และตั้งค่า first_pt เป็น x_1 และ second_pt เป็น y_1

  • พิมพ์ first_pt และ second_pt.

  • เริ่มในขณะที่ first_pt น้อยกว่า x_2 จากนั้นเพิ่ม first_pt เป็น 1 และตรวจสอบว่า IF d น้อยกว่า 0 จากนั้นตั้งค่า d เป็น d + dy ELSE ตั้งค่า d เป็น d + (dy - dx) และเพิ่ม second_pt โดย 1 พิมพ์ first_pt และ second_pt .

  • อื่น ถ้า dx น้อยกว่า dy ให้ตั้งค่า d เป็น dx - (dy/2) และตั้งค่า first_pt เป็น x_1 และ second_pt เป็น y_1 แล้วพิมพ์ first_pt และ second_pt

  • เริ่มในขณะที่วินาที _pt น้อยกว่า y_2 ภายใน WHILE ให้เพิ่ม thesecond_pt ขึ้น 1 ตรวจสอบว่า IF d น้อยกว่า 0 แล้วตั้งค่า d เป็น d + dx ELSE, d ถึง d + (dx - dy) และเพิ่ม first_pt ทีละ 1

  • พิมพ์ first_pt และ second_pt.

ตัวอย่าง

#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;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

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