Thuật toán Mid-Point vẽ đường thẳng (Mid-Point Line Generation) trong C++

Vẽ đường thẳng giữa 2 điểm (x1,y1) và (x2,y2) trên màn hình raster. Thuật toán Mid-Point quyết định pixel tiếp theo dựa trên điểm giữa 2 ứng viên: East (x+1,y) và North-East (x+1,y+1).

Quy tắc

• Tính điểm giữa M = (x+1, y+0.5).
• Nếu M nằm trên đường thẳng (d < 0) → chọn East.
• Nếu M nằm dưới đường thẳng (d ≥ 0) → chọn North-East.
• Cập nhật tham số quyết định d.

Ví dụ

Đầu vào: (3,3) → (10,8)

Đầu ra: (3,3) (4,4) (5,5) (6,5) (7,6) (8,7) (9,7) (10,8)

Đầu vào: (2,2) → (3,4)

Đầu ra: (2,2) (3,3) (3,4)

Phương pháp

• Tính dx = x2-x1, dy = y2-y1.
• Nếu dy <= dx (góc ≤ 45°): d = dy - dx/2. Lặp x từ x1 đến x2: in (x,y); x++; nếu d<0: d+=dy; else: d+=dy-dx; y++.
• Nếu dx < dy (gốc > 45°): d = dx - dy/2. Lặp y từ y1 đến y2: in (x,y); y++; nếu d<0: d+=dx; else: d+=dx-dy; x++.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

void Mid_Point(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1;
    if (dy <= dx) {
        int d = dy - dx/2;
        int x = x1, y = y1;
        cout << x << "," << y << "\n";
        while (x < x2) {
            x++;
            if (d < 0) d += dy;
            else { d += dy - dx; y++; }
            cout << x << "," << y << "\n";
        }
    } else {
        int d = dx - dy/2;
        int x = x1, y = y1;
        cout << x << "," << y << "\n";
        while (y < y2) {
            y++;
            if (d < 0) d += dx;
            else { d += dx - dy; x++; }
            cout << x << "," << y << "\n";
        }
    }
}

int main() {
    int x1=3, y1=3, x2=10, y2=8;
    cout << "Mid-Points: ";
    Mid_Point(x1, y1, x2, y2);
    return 0;
}

Đầu ra chương trình

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