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 DDA - Digital Differential Analyzer

    Thuật toán DDA - Digital Differential Analyzer được dùng để xác định các điểm ảnh được vẽ của đường thẳng trên màn hình.
    01/06/2017
    06/09/2020
    3 phút đọc
    Thuật Toán Vẽ Đường Thẳng DDA - Digital Differential Analyzer

    Để thể hiện một đường thẳng trên màn hình, sử dụng các điểm ảnh pixel để tạo ra một đường thẳng. Các điểm ảnh phải có tọa độ (x, y) là số nguyên nên việc lựa chọn điểm ảnh pixel không đúng sẽ xảy ra vấn đề tạo ra đường gấp khúc khi nhìn vào đường thẳng được tạo ra. Thuật toán DDA - Digital Differential Analyzer là 1 trong các thuật toán hỗ trợ lựa chọn điểm ảnh để vẽ các đường trên màn hình.

    Mô tả thuật toán

    Lý thuyết cơ sở

    Thuật toán DDA - Digital Differential Analyzer (bộ phân tích vi sai) có thể tóm tắt qua các bước một cách tổng quan:

    1. Giả sử tọa độ của hai điểm A(xA, yA), B(xB, yB) không trùng nhau với điều kiện là xA, yA, xB, yB đều là số nguyên.
    2. Tính số điểm ảnh của đường thẳng được vẽ thêm trên màn hình.
      • So sánh trị tuyệt đối của dx = xB - xA, dy = yB - yA và lấy trị tuyệt đối lớn nhất vì xác định càng nhiều số giao điểm thì đường thẳng càng rõ và mịn.
      • Gọi là steps là số điểm ảnh được vẽ thêm, khi đó steps = max(|dx|, |dy|).
      • Ví dụ: với A(2, 3)B(6, 6)
        • Thì dx = 3, dy = 4, |dy| > |dx| vậy steps = 4. Các ô gạch màu xanh thể hiện các giao điểm bị cắt qua.
    thuat-toan-dda-digital-differential-analyzer-1
    1. Sau khi xác định được số giao điểm steps sẽ xác định được giá trị cộng vào cho xy bắt đầu từ tọa độ A(xA, yA) cho tới tọa độ điểm B(xB, yB). Các giá trị này sẽ được tính như sau: x_inc = d/ steps, y_inc = d/ steps, giá trị là số thực.
      • Ví dụ: với A(2, 3)B(6, 6)
      • Thì dx = 3, dy = 4, steps = 4, x_inc = 0.75, y_inc = 1.
    1. Sau khi có tất cả các thông số cần thiết bao gồm A(xA, yA), B(xB, yB), steps, x_inc, y_inc, tiến hành bước cuối cùng là tìm các tọa độ cần vẽ. Chỉ cần cộng xA, yA với x_inc, y_inc theo công thức xi+1 = xi + x_inc, yi+1 = yi +y_inc. Sau đó làm tròn kết quả về số nguyên để ra các tọa độ tiếp theo.
      • Ví dụ: với A(2, 3)B(6, 6), dx = 3, dy = 4, steps = 4, x_inc = 0.75, y_inc = 1.
      • Lần lượt có các giá trị sau khi thêm x_inc, y_inc: (3, 2), (3.75, 3.0), (4.5, 4.0), (5.25, 5.0), (6.0, 6.0).
      • Kết quả sau khi làm tròn: (3, 2), (4, 3), (5, 4), (5, 5), (6, 6).
    thuat-toan-dda-digital-differential-analyzer-2

    Lưu đồ thuật toán

    luu-do-thuat-toan-dda-digital-differential-analyzer

    Code mẫu thuật toán DDA bằng C++

    void drawLineDDA(int xA, int yA, int xB, int yB)
    {
        int  dX = xB - xA, dY = yB – yA, color = 4;
    
        float steps = max(abs(dX), abs(dY));
        float x_inc = dX / steps;
        float y_inc = dY / steps;
    
        float x = xA, y = yA;
    
        putpixel(x, y, color);
        int k = 0;
    
        while (k < steps)
    	{
            k++;
            x += x_inc;
            y += y_inc;
    
            putpixel(Round(x), Round(y), color);
        }
    }
    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 Bresenham
    Với thuật toán Bresenham vẽ đường thẳng có thể xác định được điểm cần ...
    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 ...

    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