อัลกอริทึม Mid-Point Line Generation ใน C++

เส้นเชื่อม 2 จุด พิกเซลบนหน้าจอ มีพิกัดจำนวนเต็ม กำหนดจุด (x1,y1) และ (x2,y2) โดย x1 < x2, y1 < y2 หาจุดกลางทั้งหมดระหว่าง 2 จุดด้วย Mid-Point Line Generation Algorithm

อัลกอริทึม 3 แบบ

• DDA Algorithm
• Bresenham's Line Generation
• Mid-Point Algorithm (นี่คือที่นำเสนอ)

Mid-Point Algorithm ขั้นตอน

1. คำนวณจุดกลางระหว่าง East (x+1,y) และ North-East (x+1,y+1) คือ Mid (x+1, y+0.5)
2. ตัดสินใจพิกัดถัดไป:
   • Mid อยู่เหนือเส้น → เลือก East
   • Mid อยู่ใต้เส้น → เลือก North-East

ตัวอย่าง

Input: x1=3, y1=3, x2=10, y2=8

Output: Mid-Points: 3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8

คำอธิบาย: dx=7, dy=5, d = dy - dx/2 = 2 เริ่ม (3,3) while x

Input: x1=2, y1=2, x2=3, y2=4

Output: Mid-Points: 2,2 3,3 3,4

อัลกอริทึม

• คำนวณ dx = x2-x1, dy = y2-y1
• ถ้า dy ≤ dx: d = dy - dx/2, เริ่ม (x1,y1) while x < x2: x++, ถ้า d<0 d+=dy else d+=dy-dx, y++
• ถ้า dx < dy: d = dx - dy/2, เริ่ม (x1,y1) while y < y2: y++, ถ้า d<0 d+=dx else d+=dx-dy, x++
• พิมพ์พิกัดทุกขั้น

ตัวอย่างโค้ด C++

#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, second_pt = y_1;
        cout << first_pt << "," << second_pt << "\n";
        while (first_pt < x_2) {
            first_pt++;
            if (d < 0) d += dy;
            else { 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, second_pt = y_1;
        cout << first_pt << "," << second_pt << "\n";
        while (second_pt < y_2) {
            second_pt++;
            if (d < 0) d += dx;
            else { d += (dx - dy); first_pt++; }
            cout << first_pt << "," << second_pt << "\n";
        }
    }
}

int main() {
    int x_1 = 3, y_1 = 3, x_2 = 10, 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