NỘI DUNG
1 Vẽ đường thẳng a Thuật toán Bressenham
Thuật toán Bresenham là phương pháp chọn điểm y ± + 1, dựa trên việc so sánh khoảng cách giữa điểm thực y với hai điểm lân cận Điểm nào gần với điểm thực hơn sẽ được chọn làm điểm vẽ tiếp theo.
Gọi y là giá trị thực (giá trị chính xác) của đường thẳng tại x ở bước thứ i +
Gọi d 1 là khoảng cách từ y đến y i
Gọi d 2 là khoảng cách từ y đến y i + 1
ĐỒ HỌA HAI CHIỀU
Vẽ đường thẳng
Thuật toán Bresenham xác định điểm vẽ tiếp theo bằng cách so sánh khoảng cách giữa điểm thực y và hai điểm kề cận Nếu một trong hai điểm gần hơn với điểm thực, điểm đó sẽ được chọn để vẽ.
Gọi y là giá trị thực (giá trị chính xác) của đường thẳng tại x ở bước thứ i +
Gọi d 1 là khoảng cách từ y đến y i
Gọi d 2 là khoảng cách từ y đến y i + 1
Dễ nhận thấy rằng tồn tại phép toán với số thực m = d1 - d2 Để đảm bảo thuật toán chỉ thực hiện các phép toán trên số nguyên, ta khử phân số bằng cách nhân cả hai vế với dx Do đó, ta có thể đặt Pi = dx(d1 - d2).
Thay m = vào phương trình trên ta được:
P i = 2dyx i - 2dxy i + c với c = 2dy + (2b - 1)dx
Mặt khác dx > 0 với mọi trường hợp
^ dấu của P i cùng dấu với d 1 - d 2
Ta lại có: P i + 1 = 2dyx i + 1 - 2dxy i + 1 + c
Giả sử khoảng cách từ điểm thực \( y_{i+1} \) đến \( y_i \) là \( p \) Khi xem xét việc chọn điểm gần hơn với điểm thực, mỗi khi \( x \) tăng thêm 1 đơn vị, khoảng cách \( p \) sẽ cộng thêm một giá trị \( c \) Tuy nhiên, khoảng cách \( p \) không tăng lên theo cách tuyến tính, do đó, chúng ta cần tìm công thức tổng quát cho các trường hợp, đó là \( P_{i+1} = ? P_i \).
#define DE LAY 10 int oolơr = 2;
The Bresenham line algorithm is implemented in the function `Vũìd Bresenhaiìi(int xl, int yl, int x2, int y2)`, which calculates the differences in x and y coordinates (Dx and Dy) It initializes the decision variable `p` and constants `cl` and `c2` to determine the pixel positions The algorithm uses a loop to plot pixels from the starting point `(xl, yl)` to the endpoint `(x2, y2)` by adjusting the decision variable based on the calculated differences, ensuring an efficient rendering of the line.
} int main(){ int xl J yl,x2 J y2; int gd.grn^VGÁẤlAX; gdECT; irìitgráph(&gd ,íigm, NULL);
Hình 1.6 Thuật toán Midpoint đưa ra cách chọn điểm Y i + 1 là y i hay y i + 1 bằng cách so sánh điểm thực Q(x i + 1Z y) với điểm Midpoint là trung điểm của S và P
Nếu điểm Q nằm dưới điểm Midpoint, ta chọn điểm S làm điểm vẽ tiếp theo Ngược lại, nếu điểm Q nằm trên điểm Midpoint, ta chọn điểm P Đây là dạng tổng quát của phương trình đường thẳng.
Vị trí tương đối của điểm Midpoint (x, y) với đường thẳng:
+ F(x, y) < 0 nếu (x, y) nằm phía trên đường thẳng
+ F(x, y) = 0 nếu (x, y) thuộc về đường thẳng
+ F(x, y) > 0 nếu (x, y) nằm phía dưới của đường thẳng
Lúc này việc chọn các điểm S, P ở trên được đưa về việc xét dấu của
P i + 1 = P i + 2Dy nếu P i < 0 do ta chọn y i + 1 = y i
P i + 1 = p i + 2Dy - 2Dx nếu p i >0 do ta chọn y i+ 1 = y i + 1
Ta tính giá trị P 1 ứng với điểm ban đầu (x 1z y 1 ) với nhận xét rằng điểm
(x 1z y 1 ) là điểm thuộc đường thẳng, tức là có Ax 1 + By 1 + C = 0
Ta thấy kết quả của thuật toán Midpoint tương tự thuật toán Bresenham như đã nói ở trên.
Giống của thuật toán Bresenham
#include using namespace std; void mỉdpoint(ỉnt xl.int yl,int X2, int y2,int color){
Trong trường hợp 0 < m < l và xí < x2 cùng với yl < y2, ta khởi tạo các biến a, b, pi, x, y, p Đầu tiên, tính toán a = y2 - yl và b = -(x2 - xl) Gán y = yl và x = xl, sau đó vẽ điểm pixel đầu tiên bằng hàm putpixel(x, y, color) Tiếp theo, tính giá trị p = 2*a + b để xác định vị trí tương đối của điểm midpoint so với đường thẳng Trong vòng lặp while(x < x2), nếu p < 0, ta giữ nguyên y; ngược lại, ta tăng y lên 1 Cập nhật giá trị p và tăng x lên 1, sau đó in ra tọa độ pixel midpoint và vẽ điểm pixel mới.
//khoi tao wỉndow có chieu rong x@0 và chieu cao y = 500 setwỉndowtitle("Thuat toan Line Hidpoint");
//thiet lap tieu de cho windows mỉdpoint(10,10,400,400,15); getch();
Vẽ đường tròn
Giả sử (x i , y i ) đã vẽ được, điểm kế tiếp là (x i + 1, y i ) hoặc (x i +1, y i -1)
Từ phương trình: X 2 + y 2 = R 2 ta tính được giá trị y thực ứng với X i + 1 là: y 2 = R 2 - (x i + 1) 2 Đặt: d i = y i 2 - y 2 = y i 2 - R 2 + (X i + 1) 2 d 2 = y 2 - (y i - 1) 2 = R 2 - (X i + 1) 2 - (y i - 1) 2
Nếu P i > 0: chọn y i + 1 = y i - 1 (4) ^ P i + 1 = P i + 4(X i - y ± ) + 10 Ta chọn điểm đầu tiên cần vẽ (0, R), theo (2) ta có: P 1 = 3 -
Tóm lại: Ta có thuật toán vẽ đường tròn:
• Bước 1: Chọn điểm đầu tiên cần vẽ (x 1z y 1 ) = (0, R)
• Bước 2: Tính P đầu tiên: P 1 = 3 - 2R Nếu P < 0: chọn điểm kế tiếp là
Ngược lại: p i + 1 = p i + 4(x i - y i ) + 10 Khi đó: Nếu p i + 1 < 0: chọn điểm kế tiếp là(x i + 1 , y i + 1 ) Ngược lại chọn điểm (x i + 1 , y i + 1 -1)
• Bước 4: Lặp lại bước 3 cho đến khi x = y.
#include voỉd drawCircle(ỉnt Xj ỉnt y_> ỉnt xCj ỉnt yc); voỉd main()
To initialize a graphics program in C++, set up the graphics driver and mode using `initgraph(&gd, &gm, "C:\\TC\\BGI");` Prompt the user to enter the center coordinates of the circle by using `cout` to display a message, and read the input with `cin` Next, request the radius of the circle, again utilizing `cout` for the prompt and `cin` for input Calculate the initial decision parameter for the circle using the formula `pk = 3 - 2 * r;`.
I { pk = pk + (4*x) + 6; drawCircle(++x 4 yjXC 4 yc);
I { pk = pk + (4*(x-y)) + 10; drawCircle(++x 4 y^xc^yc);
The `drawCircle` function utilizes the midpoint circle algorithm to render a circle on a graphical interface It takes three integer parameters: `y`, `xc`, and `yc`, which represent the circle's radius and center coordinates, respectively The function employs the `putpixel` method to plot points in the first, second, third, and fourth quadrants of the circle, ensuring that all points are rendered in the color green By calculating the necessary pixel positions using the circle's equation, it effectively creates a visually coherent representation of the circle on the screen.
• Thuật toán Đường tròn có tâm O(xc, yc) = (0, 0), bán kinh r có phương trình: x 2 + y 2 = r 2 => x 2 + y 2 - r 2 = 0 Đặt f(x, y) = x 2 + y 2 - r 2
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
Đường tròn có tính đối xứng qua các cung 1/8, cho phép xác định tọa độ của bảy điểm còn lại tương ứng với một điểm có tọa độ (x, y) thuộc một cung nào đó bằng cách sử dụng tính đối xứng.
Để vẽ một đường tròn, chúng ta chỉ cần vẽ 1/8 đường tròn và sau đó sử dụng phép đối xứng để hoàn thiện hình Điểm khởi đầu để vẽ là tại tọa độ (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.
Ta có hình như sau:
Hình 1.15 Tính F i Đặt Fi = F(X, Y - 1/2), ta hình có công thức:
F(Xi + l,ri - ỉ) = (Xi + l) 2 + (ri - ỉ) 2 - lì 2
Fi = XÍ 2 - 2Xi — Yi~ — Yi —— B 2
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
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 = 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) = (Xí + l) 2 + (ri - - lĩ 2
Fi = Xi 1 - 2Xi -YÍ 2 - Yi - 7 - ỉĩ 2
Thay Xi = 0 và Yi = R trong công thức trên ta có được: F = 5/4 - R
Lisĩng namespace std; void drawcircle(iirt xGj int ya, int radius)
{ ' ĩrrt X = radĩus; ĩn± y = B; ĩr¥t err = e; whĩle (x >= y)
The code snippet demonstrates the use of the `putpixel` function to draw pixels in a graphical interface by specifying their coordinates and color It highlights various pixel placements based on calculated positions involving variables `x`, `y`, `Xj`, and `ye`, while using the color RED for specific points The conditional statement checks for an error condition, ensuring that the drawing operations proceed only if the error is less than or equal to a defined threshold.
{ ĩ.rrt gdrĩverECĩj gmode; error, Xj y, r; ĩnĩtgraphtSgdrĩver, Sgmode., ■c:\xturiằc3\\liđĩ"};
CMitô*Enter radius ơf ũrcle: ■; cũiằr; coutô"Enter co-ordinates of center(x and y}: ■; cĩriằj>>y; draucĩrcleíx, yj r); returiì e;
Thuật Toán Tô Màu Tràn
Thuật toán Đường biên trong tô loang xác định bằng tập hợp các đỉnh của đa giác, với đường biên được biểu diễn bằng màu sắc của các điểm thuộc về nó Quá trình bắt đầu từ một điểm trong vùng tô, kiểm tra các điểm lân cận để xác định xem chúng đã được tô màu hay là điểm biên Nếu không phải là điểm đã tô hoặc điểm biên, điểm đó sẽ được tô màu Quá trình này tiếp tục cho đến khi không còn điểm nào có thể tô thêm.
Hình 1.19 -Bước 1: Kẻ vùng biên cần tô.
-Bước 2: Xác định một điểm (x,y) bên trong vùng cần tô.
-Bước 3: Tô điểm (x,y) sau đó tô loang những điểm lân cận.
#include using namespace stdj voĩd fl.oodFill (int Xj.int y>int oldcolor , int neưcol ỉf(getpĩxel== ữldcolor)
{ - putpÌKel(x J y J newcolor) j floodFi11(x+1,y,oldcolorỊneưcolũr)j floodFi11(Xfy+1Ịoldcolorfneưcolũr)j floodFill(x-l í y í oldcolor,newcolor)j f loo d F i 11 (X , y -1, ol d colo r f n eưcolũ r) 5 Ẹ } int main()
To create a circle in a graphical program, first, declare integer variables for the radius and the x and y positions Prompt the user to input the x and y coordinates for the circle's center, and then ask for the radius Initialize the graphics system with the appropriate path, and use the circle function to draw the circle at the specified coordinates with the given radius Fill the circle with color, delay the display for a moment, and finally close the graphics window before returning from the program.
Thuật toán tô màu theo đường quét
Để xác định phần giao của đa giác với dòng quét, ta cần tìm giao điểm giữa dòng quét và các cạnh của đa giác Sau khi xác định các giao điểm, chúng sẽ được sắp xếp theo thứ tự tăng dần của hoành độ Các đoạn giao được hình thành từ những cặp giao điểm này sẽ được tô màu, tạo thành các đoạn thẳng giới hạn.
Để tìm ymin và ymax, ta xác định giá trị nhỏ nhất và lớn nhất trong tập hợp các tung độ của các đỉnh của đa giác đã cho Với mỗi giá trị y = k, trong khoảng từ ymin đến ymax, ta thực hiện lặp lại các bước cần thiết.
+ Tìm tất cả các hoành độ giao điểm của dòng quét y = k với các cạnh của đa giác.
+ Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x 0 ,x 1 , , x n ,
+ Tô màu các đoạn thẳng trên đường thẳng y = k lần lượt được giới hạn bởi các cặp (x 0 , x 1 ), ( x 1 ,x 2 ), , x 2k , x 2k+1 ).
Nhưng nếu chỉ dừng ở mức này và chuyển sang cài đặt thì chúng ta sẽ gặp phải một số vấn đề như sau:
Để tối ưu hóa tốc độ quét, cần hạn chế số lượng cạnh của đa giác mà ta phải kiểm tra giao điểm cho mỗi dòng quét, vì không phải tất cả các cạnh đều cắt qua dòng quét.
Việc xác định giao điểm giữa các cạnh của đa giác và các dòng quét thường yêu cầu thực hiện các phép toán phức tạp như nhân và chia trên số thực Nếu áp dụng phương pháp giải hệ phương trình để tìm giao điểm, điều này có thể làm giảm tốc độ của thuật toán.
Nếu số giao điểm giữa các cạnh của đa giác và dòng quét là lẻ, việc nhóm các cặp giao điểm liên tiếp để tạo thành các đoạn tô có thể không chính xác Tình huống này xảy ra khi dòng quét đi ngang qua các đỉnh của đa giác.
Việc xác định giao điểm của dòng quét với các cạnh ngang là một trường hợp đặc biệt cần xử lý phù hợp Để giảm số lượng cạnh cần tìm giao điểm, ta áp dụng công thức hệ số góc: X k+1 = X k + 1/m, trong đó m là hệ số góc của cạnh, và Xk+1, Xk là hoành độ giao điểm với dòng quét y=k và y=k+1 Đối với trường hợp giao điểm đi qua đỉnh đơn điệu, ta tính số giao điểm là 1, còn với đỉnh cực trị, số giao điểm được tính là 0 hoặc 2.
Phát Triển Ứng dụng Đồ Họa 2D
Phát biểu bài toán
Dựa trên kiến thức về Đồ Họa 2 chiều, nhóm chúng tôi đã phát triển một ứng dụng mô phỏng bàn cờ 2D sử dụng thư viện đồ họa Graphics Chúng tôi áp dụng thuật toán Bressenham để vẽ các đường thẳng, tạo nên hình ảnh bàn cờ một cách chính xác và hiệu quả.