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

    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 bằng ngôn ngữ C++.
    10/10/2015
    20/09/2020
    3 phút đọc
    Thuật Toán Midpoint Vẽ Đường Tròn

    Tìm hiểu thuật toán Midpoint

    Đường tròn có tâm O(xc, yc) = (0, 0), bán kính r có phương trình:

    x2 + y2 = r2 => x2 + y2 - r2 = 0

    Đặt f(x, y) = x2 + y2 - r2

    Với mọi điểm P(x, y) nằm trong hệ tọa độ Oxy:

    • P(x, y) nằm trên đường tròn O nếu f(x, y) = 0
    • P(x, y) nằm ngoài đường tròn O nếu f(x, y) > 0
    • P(x, y) nằm trong đường tròn O nếu f(x, y) < 0
    ss_1

    Do đường tròn có tính đối xứng qua các cung 1/8, nghĩa là ứng với một điểm có tọa độ (x, y) thuộc 1 cung bất kỳ, có thể hoàn toàn xác định được tọa độ 7 điểm còn lại bằng cách lấy đối xứng qua các cung.

    Từ tính chất đó nên chỉnh cần vẽ 1/8 đường tròn là đủ, sau đó sẽ lấy đối xứng để được đường tròn hoàn chỉnh.

    Điểm đầu tiên vẽ là điểm (x = 0, y = R)

    Trong cung 1/8 thứ nhất do khoảng biến thiên của x lớn hơn khoảng biến thiên của y, nên xi+1 = xi + 1.

    Giả sử đã vẽ được (Xi, Yi) ở bước thứ i, cần xác định (Xi+1, Yi+1) ở bước thứ i + 1.

    Xi+1 = Xi+1
    Yi+1 ∈ {Yi, Yi - 1}
    ss_3

    Tính Fi

    Đặt Fi =  F(X, Y - 1/2):

    F(Xi + 1, Yi - 1/2) = (Xi + 1)2 + (Yi - 1/2)2 - R2
    Fi = Xi2 + 2Xi + Yi2 - Yi + 5/4 - R2

    Nếu Fi < 0 ⇔ (Xi+1, Y) gần với Yi ⇒ Yi+1 = Yi

    Nếu Fi ≥ 0 ⇔ (Xi+1, Y) gần với Yi -1 ⇒ Yi+1 = Yi-1

    Tính Fi +1 theo Fi

    Fi+1 - Fi = 2Xi + 3 + (Yi + 12 - Yi2)+ (Yi+1 - Yi)  (*)

    Nếu Fi < 0 thì Fi+1 = Fi + 2Xi + 3, do thay thế Yi+1 = Yi  vào (*)

    Nếu Fi ≥ 0 thì Fi+1 = Fi + 2(Xi - Yi) + 5, do thay thế Yi+1 = Yi-1 vào (*)

    Tính giá trị F đầu tiên

    F(Xi + 1, Yi - 1/2) = (Xi + 1)2 + (Yi - 1/2)2 - R2
    Fi = Xi2 + 2Xi + Yi2 - Yi + 5/4 - R2

    Thay Xi = 0 và Yi = R trong công thức trên:

    F = 5/4 - R 

    Hiện thực thuật toán Midpoint

    Hàm vẽ 8 điểm đối xứng nhau

    void put8pixel(int xc, int yc, int x, int y, int color)
    {
        putpixel(x + xc, y + yc, color);
        putpixel(-x + xc, y + yc, color);
        putpixel(x + xc, -y + yc, color);
        putpixel(-x + xc, -y + yc, color);
        putpixel( y + xc, x + yc, color);
        putpixel(-y + xc, x + yc, color);
        putpixel(y + xc, -x + yc, color);
        putpixel(-y + xc, -x + yc, color);
    }
    

    Hàm vẽ đường tròn

    void drawCircleMidpoint(int xc, int yc, int r, int color)
    {
        int x = 0, y = r;
        int f = 1 - r;
        put8pixel(xc, yc, x, y, color);
        while (x < y)     {         if (f < 0) f += (x << 1) + 3;         else         {             y--;             f += ((x - y) << 1) + 5;         }         x++;         put8pixel(xc, yc, x, y, color);     } }

    Chương trình chính

    int main()
    {
    int gd = DETECT, gm; initgraph(&gd, &gm, "c:\\tc\\bgi");
    drawCircleMidpoint(200, 200, 100, colors::BLUE);
    Sleep(3000);
    closegraph(); return 0; }
    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 Bresenham
    Với thuật toán Bresenham vẽ đường thẳng có thể xác định được điểm cần ...

    Khám phá

    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 ...
    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 ...
    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 ...
    Cơ Bản Vẽ Trên <canvas> 2D Với HTML5
    Giới thiệu HTML5 canvas, tạo đối tượng vẽ, các đường nét, hình chữ nhật, ...
    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à 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