STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

    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.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo 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 - 2021