STDIO
Tìm kiếm gần đây
    Mục lục
    Thảo luận
    0
    Liên kết
    QR Code

    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 thước gần đúng với các điểm trên thực tế. Để thu được đường thẳng tốt nhất thì ta cần lựa chọn được các điểm ảnh gần đúng với đường thẳng thực tế nhất. Đó là vấn đề có thể giải quyết được bằng thuật toán Midpoint.

    Amy

    08/07/2015
    20/08/2020
    4 phút đọc
    Thuật Toán Vẽ Đường Thẳng Midpoint

    Trong toán học, khái niệm đường thẳng là 1 đường kéo dài vô cùng mỏng, thẳng tuyệt đối; qua hai điểm bất kì chỉ có một đường thẳng đi qua nó.

    Trên một màn hình máy tính lại bao gồm nhiều điểm ảnh với các kích thước cụ thể khác nhau. Vì vậy, khái niệm đường thẳng ở đây lại là một tập hợp các điểm có kích thước xấp xỉ gần đúng với các điểm trên thực tế.

    Để thu được đường thẳng tốt nhất thì cần lựa chọn được các điểm ảnh gần đúng với đường thẳng thực tế nhất. Do đó, các thuật toán vẽ đường thẳng ra đời nhằm giải quyết bài toán trên.

    Để vẽ được đường thẳng nối từ hai điểm (x1, y1), (x2, y2), cần tính toán được điểm vẽ tiếp theo sau khi vẽ điểm đầu tiên (x0, y0).

    Với thuật toán Midpoint, có thể tìm được điểm cần tìm dựa vào vị trí trung điểm của các đối tượng đang nằm trong vùng lựa chọn so với đường thẳng đang được vẽ.

    Mô tả thuật toán

    Đối với việc lựa chọn điểm vẽ tiếp theo sau A, có hai lựa chọn đó là điểm PQ với M là trung điểm giữa chúng. Việc quyết định chọn điểm nào để vẽ tiếp theo phụ thuộc vào vị trí của M so với đường thẳng đang vẽ. Nếu M nằm phía dưới đường thẳng, chọn điểm Q. Ngược lại, nếu M nằm phía trên đường thẳng ta chọn điểm P.

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

    Thuật toán Midpoint

    Phương trình đường thẳng là:

    y = m * x + b, m = dy / dx
    ⇔ y = dx / dx * x + b
    ⇔ dy * x + (-dx * y) + b * dx = 0 (1)

    Mà:

    F(x, y) = a * x + b * y + c = 0 (2)
    (1), (2) ⇒ a = dy, b = -dx, c = b * dx

    Tìm d

    F(M) = F(xi + 1, yi + 1 / 2)
    = F(xi, yi) + a + b / 2 = 0 + dy + dx / 2 = dy + dx / 2

    Tìm dmax

    Đặt d = F(M)

    • Nếu d > 0, chọn điểm Q để vẽ.
    • Nếu d < 0, chọn điểm P để vẽ.

    Trường hợp 1 - chọn Q

    Mnew * (xi + 2, yi + 1 / 2) ⇒ dnew = F(xi + 2, yi + 1 / 2)
    (Δd)Q = dnew - dold
    = F(xi + 1, yi + 1 / 2) - F(xi + 2, yi + 1 / 2) = a
    = dy
    ⇒ dnew = dold + dy

    Trường hợp 2 - chọn P

    Mnew * (xi + 2, yi + 3 / 2) ⇒ dnew = F(xi + 2, yi + 3 / 2)
    (Δd)P = dnew - dold
    = F(xi + 1, yi + 1 / 2) - F(xi + 2, yi + 3 / 2) = a + b
    = dy - dx
    ⇒ dnew = dold + dy - dx

    Thuật giải

    Thuật giải dưới đây chỉ nêu và hiện thực thuật toán trong trường hợp 0 < m < 1, các trường hợp còn lại có thể suy luận tương tự như trên.

    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 = dy – dx/2;
    x = x1, y = y1;
    // Vẽ điểm (x, y)
    

    Bước 2

    while (x <= x2)
    {
        Nếu d > 0 thì:
            x = x + 1;
            y = y;
            d = d + dy;
        Nếu d < 0 thì:
            x = x + 1;
            y = y + 1;
            d = d + dy – dx;
        // Vẽ điểm (x, y)
    }

    Hiện thực

    void midpointLine(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, MAGENTA);
    	float D = Dy - (Dx >> 1); // ~ float D = Dy - Dx/2;
    	while(x <= x2)
    	{
    		x++;
    		if (D < 0 )
    		{
    			D = D + Dy;
    		}
    		else 
    		{
    			D = D + (Dy - Dx);
    			y++;
    		}
    		putpixel(x, y, MAGENTA);
    	}
    }
    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

    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 ...

    Giải Thuật Lập TrìnhĐồ họa máy tính

    15/07/2015

    Thuật Toán Vẽ Đường Thẳng DDA - Digital Differential Analyzer

    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 ...

    Giải Thuật Lập TrìnhĐồ họa máy tính

    01/06/2017

    Khám phá thêm

    Thuật Toán Midpoint Vẽ Đường Tròn

    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 ...

    Giải Thuật Lập TrìnhĐồ họa máy tính

    10/10/2015

    Thuật Toán PID trong Điều Khiển Tự Động

    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 ...

    Điện Tử Ứng DụngĐào tạo & nâng cao

    03/06/2016

    Thuật Toán Nén Dữ Liệu RLE

    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à ...

    Giải Thuật Lập TrìnhKiến thức

    05/12/2016

    Kỹ Thuật Grayscale và Nhị Phân Hoá Ảnh (Adaptive Threshold)

    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ố ...

    Computer VisionOpenCV

    23/01/2015

    Xử Lý Ảnh Với OpenCV: Các Phép Toán Hình Thái Học

    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 ...

    Computer VisionOpenCV

    23/01/2015

    Giải Thuật Là Gì?

    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 ...

    Giải Thuật Lập TrìnhKiến thức

    25/08/2015

    Thuật toán Depth First Search

    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 ...

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

    19/09/2015

    MD5

    MD5

    MD5 (MD5 Message-Digest Algorithm) là một thuật toán tóm tắt thông điệp, ...

    Cyber SecurityCơ bản

    13/08/2018

    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