STDIO
Tìm kiếm gần đây
    • Nội dung
    • QR Code
    • 0
    • 0
    • Sao chép

    Thuật Toán Vẽ Đường Thẳng Bresenham

    Với thuật toán Bresenham vẽ đường thẳng 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.

    Amy

    15/07/2015
    19/08/2020
    3 phút đọc
    Thuật Toán Vẽ Đường Thẳng Bresenham

    Để vẽ được đường thẳng trên màn hình máy tính cần xác định được điểm ảnh vẽ tiếp theo trên màn hình. Khác với thuật toán Midpoint, thuật toán Bresenham 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.

    Mô tả thuật toán vẽ đường thẳng Bresenham

    Thuật toán vẽ đường thẳng Bresenham

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

    y = m * x + b
    m = Δy / Δx

    Nhìn vào hình trên có:

    d1 = yi + 1 - y = yi + 1 - m * (xi + 1) - b
    d2 = y - yi = m * (xi + 1) + b - yi

    ⇒ d2 - d1
    = m * (xi + 1) + b - yi - (yi + 1 - m * (xi + 1) - b)
    = 2 * m * (xi + 1) - 2 * yi + 2 * b - 1
    = 2 * (Δy / Δx) * (xi + 1) - 2 * yi + 2 * b - 1

    ⇔ Δx(d2 - d1) = 2 * Δy * xi - 2 * Δx * yi + c = pi, c = -2 * yi + 2 * b - 1 (1)

    Mà:

    0 < m < 1 ⇒ Δx > 0

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

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

    Mặt khác:

    pi+1 = 2 * Δy * xi+1 - 2 * Δx * yi+1 + c
    ⇒ pi+1 - pi = 2 * Δy * (xi+1 - xi) - 2 * Δx * (yi+1 - yi)
    ⇒ pi+1 = pi + 2 * Δy * (xi+1 - xi) - 2 * Δx * (yi+1 - yi)

    Tìm pi+1

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

    Khi đó:

    xi+1 = xi + 1, xy+1 = yi
    ⇒ pi+1 = pi + 2 * Δy

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

    Khi đó:

    xi+1 = xi + 1, xy+1 = yi + 1
    ⇒ pi+1 = pi + 2 * (Δy - Δx)

    Tìm p0

    Thay tọa độ (x1, y1) vào (1) được:

    p0 = 2 * Δy - Δx

    Thuật giải

    Input: (x1, y1), (x2, y2)

    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); } }
    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Đề xuất

    Thuật Toán Vẽ Đường Thẳng Midpoint
    Đường thẳng trên một màn hình máy tính là một tập hợp các điểm có kích ...
    Thuật Toán Vẽ Đường Thẳng DDA - Digital Differential Analyzer
    Thuật toán DDA - Digital Differential Analyzer được dùng để xác định các ...

    Khám phá

    Thuật Toán Midpoint Vẽ Đường Tròn
    Giới thiệu thuật toán Midpoint để vẽ đường tròn và hướng dẫn hiện thực ...
    Thuật Toán PID trong Điều Khiển Tự Động
    Chi tiết về thuật toán PID, các ví dụ thực tế và hướng đưa thuật toán ...
    Thuật Toán Nén Dữ Liệu RLE
    Trong quá trình lưu trữ cũng như truyền dữ liệu, việc nén dữ liệu là ...
    Kỹ Thuật Grayscale và Nhị Phân Hoá Ảnh (Adaptive Threshold)
    Giới thiệu và chi tiết các thuật toán Grayscale, ảnh nhị phân và một số ...
    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học
    Giới thiệu những thuật toán cơ sở trong xử lý hình thái học, những thuật ...
    Giải Thuật Là Gì?
    Giải thuật - thuật toán là một tập hợp hữu hạn các thao tác được thực ...
    Thuật toán Depth First Search
    Giới thiệu, khái quát, trình bày và cung cấp code mẫu về thuật toán ...
    MD5
    MD5 (MD5 Message-Digest Algorithm) là một thuật toán tóm tắt thông điệp, ...
    Khi bạn nhấn vào liên kết sản phẩm do STDIO đề xuất và mua hàng, STDIO có thể nhận được hoa hồng. Điều này hỗ trợ STDIO tạo thêm nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO
    Trang chính
    Công ty TNHH STDIO

    30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
    +84 28.36205514 - +84 942.111912
    developer@stdio.vn

    383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
    Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012

    ©STDIO, 2013 - 2020