Sự hoàn hảo trong thiết kế đạt được không phải khi không có gì cần phải thêm vào, mà là không có gì cần phải bỏ bớt. Antoine de Saint-Exupéry
STDIO Với thuật toán Bresenham, ta có thể xác định được điểm cần tìm dựa vào khoảng cách giữa đường thẳng thực tế với các điểm nằm trong vùng lựa chọn. Bài viết giới thiệu bạn đọc sử dụng một trong những thuật toán phổ biết để vẽ đường thẳng - thuật toán Bresenham
Nội dung bài viết

Giới thiệu

Như bài viết Thuật Toán Vẽ Đường Thẳng Midpoint đã đề cập, để vẽ được đường thẳng trên màn hình máy tính ta cần xác định được điểm ảnh vẽ tiếp theo trên màn hình. Với thuật toán Bresenham, ta có thể xác định được điểm cần tìm dựa vào khoảng cách giữa đường thẳng thực tế với các điểm nằm trong vùng lựa chọn.

Tiền đề bài viết

Bài viết nằm trong chuỗi bài viết về thuật toán vẽ đường thẳng.

Đối tượng hướng đến

Dành cho những lập trình viên mới bước chân vào con đường tìm hiểu Đồ họa máy tính (Computer Graphics) và có kiến thức lập trình căn bản C/C++. Các đối tượng khác vui lòng xem bài viết như là một tài liệu để tham khảo.

Mô tả thuật toán

ss_1

Xét trường hợp: 0 < m < 1

ss_2

Nhìn vào hình bên ta thấy:

ss_3

ss_4

ss_5

ss_6

ss_7

Mà:

ss_8

Nên dấu của pi phụ thuộc vào d2 – d1.

  • Nếu pi < 0 ->ta chọn P để vẽ.
  • Nếu pi > 0 ->ta chọn Q để vẽ.

Mặt khác, ta có:

ss_9

ss_10

ss_11

Tìm pi+1

Trường hợp 1: Chọn P

Khi đó ta có: 

ss_12

ss_13

Trường hợp 2: Chọn Q

Khi đó, ta có:

ss_14

ss_15

Tìm p0

Thay tọa độ ss_16 vào (1) ta được:

ss_17

Thuật giải

Input: ss_18

Output: Tập hợp điểm có tọa độ nguyên.

Các bước thực hiện chính:

BƯỚC 1

dx = x2 - x1, dy = y2 - y1;
d = 2dy - dx;
x = x1, y = y1;
//Vẽ điểm (x,y)

BƯỚC 2

while (x <= x2)
{
    Nếu p > 0 thì:
     	x = x +1;
        y = y;
    	d = d + 2 * dy;
	Nếu p < 0 thì:
        x = x + 1;
        y = y + 1;
    	d = d + 2*(dy – dx);

	// Vẽ điểm (x,y)
}

Hiện thực

void BresenhamLine(int x1, int y1, int x2, int y2)
{
	
	int Dx = x2 - x1;
	int Dy = y2 - y1;
	int x = x1;
	int y = y1;
	putpixel(x1, y1, BLUE);
	int D = (Dy << 1) - Dx; // ~ int D = 2*Dy - Dx;
	while(x <= x2)
	{
		x++;
		if (D < 0)
		{
			D = D + (Dy << 1); // ~ D = D + 2*Dy;
		}
		else 
		{
			D = D + ((Dy - Dx) << 1); // D = D + 2*(Dy - Dx);
			y++;
		}
		putpixel(x, y, BLUE);
	}
}

Bạn cần hỗ trợ các dự án kết nối không dây?

Quí doanh nghiệp, cá nhân cần hỗ trợ, hợp tác các dự án IoT, kết nối không dây. Vui lòng liên hệ, hoặc gọi trực tiếp 0942.111912.

  • TỪ KHÓA
  • Arduino
  • ESP32
  • ESP8266
  • Wifi
  • Bluetooth
  • Zigbee
  • Raspberry Pi
THẢO LUẬN
ĐÓNG