Nội dung bài viết
Nguyễn Nghĩa Nếu bạn đã sử dụng hàm circle trong thư viện graphics.h hay DrawEllipse để vẽ đường tròn, có bao giờ bạn hỏi là bên dưới những hàm đó được hiện thực như thế nào, sữ dụng thuật toán nào để hiện thực được nó. Trong bài viết này tôi sẽ phần tích và hướng dẫn một trong những thuật toán dùng để vẽ đường tròn, đó chính là thuật toán Midpoint.

Giới thiệu

Nếu bạn đã sử dụng hàm circle trong thư viện graphics.h hay DrawEllipse để vẽ đường tròn, có bao giờ bạn hỏi là bên dưới những hàm đó được hiện thực như thế nào, sữ dụng thuật toán nào để hiện thực được nó. Trong bài viết này tôi sẽ phần tích và hướng dẫn một trong những thuật toán dùng để vẽ đường tròn, đó chính là thuật toán Midpoint

Tiền đề bài viết

Tiếp nối những bài viết về đồ họa máy tính (Computer Graphics) của tác giả Amy Le

Đối tượng hướng đến

Những lập trình viên muốn tìm hiểu về thuật toán về các đường cơ bản trong đồ họa máy tính.

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

Đường tròn có tâm O(xc, yc) = (0, 0), bán kinh 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, ta có:

  • 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 cũng 1/8, nghĩa là ứng với một điểm có tọa độ (x, y) thuộc 1 cung nào đó, ta 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úng ta 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 ta 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ử ta đã vẽ được (Xi, Yi) ở bước thứ i, ta cần xác định (Xi+1, Yi+1) ở bước thứ i + 1.

Như vậy ta có:

ss_2

Ta có hình như sau:

ss_3

Tính Fi

Đặt Fi =  F(X, Y - 1/2), ta hình có công thức:

ss_4

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 ta thay thế Yi+1 = Yi  vào (*)

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

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

Ta có: 

ss_4

Thay Xi = 0 và Yi = R trong công thức trên ta có được:
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; int 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;
}

Download Demo

STDIO_Midpoint_VS2013.zip

 

 

THẢO LUẬN
ĐÓNG