PHẦN II
16 CÂU, CHỌN 1 TRONG 16 CÂU, MỖI CÂU 5
ĐIỂM
Câu 1:
Xây dựng và cài đặt thuật toán tô màu theo đường biên không đệ qui.
Đáp án:
Thuật toán như sau:
Cho trước điểm s nằm bên trong đường cong bất kỳ khép kín.
Loang sang phải và lưu hoành độ bên nhất vào stack.
Lặp cho đến khi stack rỗng
Lấy trong stack ra
Tô sang trái và gọi hoành độ bên trái là
min
x
Đi lên và loang sang phải, sang trái để tìm các hoành độ bên phải và lưu vào stack
Đi xuống và loang sang phải, sang trái để tìm các hoành độ bên phải và lưu vào stack
Quay về đầu vòng lặp.
#define MAXSIZE 100
typedef struct tagSTACK {
int top;
POINT a[MAXSIZE];
} STACK;
bool IsFull(STACK stack)
{
if (stack.top == MAXSIZE)
return true;
else
return false;
}
bool IsEmpty(STACK stack)
{

x ;
}
}
void TimCacXBenPhaiNhat(HDC hdc, STACK &stack, int x, int y, int xmin,
COLORREF FC, COLORREF BC)
{
int m;
m = x;
POINT p;
// Ben phai
while (GetPixel(hdc,x,y) != BC && GetPixel(hdc,x,y) != FC) {
if (GetPixel(hdc,x+1,y) == BC || GetPixel(hdc,x+1,y) == FC) {
p.x = x;
p.y = y;
Push(stack,p);
break;
}
x++;
}
// Ben trai
m = x;
while (m > xmin) {
if (GetPixel(hdc,m,y) == FC || GetPixel(hdc,m,y) == BC)
if (GetPixel(hdc,m-1,y) != FC && GetPixel(hdc,m-1,y) != BC)
if (!IsFull(stack)) {
p.x = m-1;
p.y = y;
Push(stack,p);
}
m ;

}
Câu 2:
Xây dựng và cài đặt thuật toán tô màu đa giác theo dòng quét.
Đáp án:
Thuật toán như sau:
Cho các đỉnh của đa giác.
Xây dựng danh sách các cạnh, loại bỏ các cạnh nằm ngang.
Xác định đỉnh được tính là một điểm giao hay hai điểm giao
Với mỗi dòng quét k chạy từ
bottom
y
lên
top
y
Tìm hoành độ giao điểm của dòng quét k với mỗi cạnh, trong đó số lượng giao điểm
là chẳn.
Sắp xếp các hoành độ giao điểm theo thứ tự từ nhỏ đến lớn.
Nối từng cặp, ví dụ
),(
21
xx
,
),(
43
xx

#define MAXEDGE 50
#define MAXVERT 50
typedef struct tagVERT {
int NumVert;

Vert.NumVert = 11;
Vert.P[0].x = 500; Vert.P[0].y = 500;
Vert.P[1].x = 500; Vert.P[1].y = 100;
Vert.P[2].x = 450; Vert.P[2].y = 450;
Vert.P[3].x = 450; Vert.P[3].y = 350;
Vert.P[4].x = 400; Vert.P[4].y = 300;
Vert.P[5].x = 350; Vert.P[5].y = 300;
Vert.P[6].x = 200; Vert.P[6].y = 100;
Vert.P[7].x = 150; Vert.P[7].y = 150;
Vert.P[8].x = 100; Vert.P[8].y = 125;
Vert.P[9].x = 10; Vert.P[9].y = 200;
Vert.P[10].x = 10; Vert.P[10].y = 500;
// Them dinh cuoi cung bang dinh dau tien de de lap trinh
Vert.P[11] = Vert.P[0];
Polygon(hdc,Vert.P,Vert.NumVert);
SelectObject(hdc,hPenOld);
ReleaseDC(hWnd,hdc);
return;
}
void ToMauTheoDongQuet(HWND hWnd)
{
HDC hdc;
HPEN hPen, hPenOld;
hPen = CreatePen(PS_SOLID,1,RGB(0,0,255));
hdc = GetDC(hWnd);
hPenOld = (HPEN)SelectObject(hdc,hPen);
// Tao danh sach cac canh - loai bo canh nam ngang
EDGELIST edgelist;
int n;
edgelist.NumEdge = 0;

edgelist.Edge[n].ymax = edgelist.Edge[n].y1;
edgelist.Edge[n].x = edgelist.Edge[n].x1;
edgelist.Edge[n].a = (1.0*edgelist.Edge[n].x2-
edgelist.Edge[n].x1)/(edgelist.Edge[n].y2-edgelist.Edge[n].y1);
}
// Them canh cuoi cung bang canh dau tien de de lap trinh
edgelist.Edge[edgelist.NumEdge] = edgelist.Edge[0];
// Tim y top va y bottom
int ybottom, ytop;
ytop = edgelist.Edge[0].ymin;
ybottom = edgelist.Edge[0].ymax;
for (n=1; n<edgelist.NumEdge; n++) {
if (edgelist.Edge[n].ymin < ytop)
ytop = edgelist.Edge[n].ymin;
if (edgelist.Edge[n].ymax > ybottom)
ybottom = edgelist.Edge[n].ymax;
}
int k;
int diemgiao[50];
int sldiemgiao, x;
for (k=ybottom-1; k>=ytop+1; k ) {
//Tim giao cua dong quet k voi tung canh
sldiemgiao = 0;
for (n=0; n<edgelist.NumEdge; n++)
if (k>=edgelist.Edge[n].ymin && k<=edgelist.Edge[n].ymax) {
x = (int)edgelist.Edge[n].x;
edgelist.Edge[n].x = edgelist.Edge[n].x -
edgelist.Edge[n].a;
diemgiao[sldiemgiao] = x;
sldiemgiao++;









=










1100
10
01
1
'
'
y
x
tr
tr
y







1100
0cossin
0sincos
1
'
'
y
x
y
x
θθ
θθ
Phép tỷ lệ:












y
x
y
x
Phép biến dạng:
Phép biến dạng theo hướng x




















=












=










1100
01
001
1
'
'
y
x
gy
x
Phép biến dạng theo hai hướng


1100
01
01
1
'
'
y
x
g
h
y
x

typedef struct tagPOINTH {
double x;
double y;
double h;
} POINTH;
POINTH A = {0,0,1};
POINTH B = {200,0,1};
POINTH C = {200,150,1};
POINTH D = {0,150,1};
POINTH A1,B1,C1,D1;
void Transform(POINTH P, double M[3][3], POINTH &Q)
{
Q.x = P.x*M[0][0] + P.y*M[0][1] + P.h*M[0][2];
Q.y = P.x*M[1][0] + P.y*M[1][1] + P.h*M[1][2];
Q.h = P.x*M[2][0] + P.y*M[2][1] + P.h*M[2][2];
return;

Transform(B,M,B1);
Transform(C,M,C1);
Transform(D,M,D1);
VeHinhChuNhat(hWnd);
return;
}
void Rotation(HWND hWnd)
{
double pi = 4.0*atan(1.0);
double theta = 30*pi/180;
double M[3][3] = {cos(theta),-sin(theta),0,
sin(theta), cos(theta),0,
0 , 0 ,1};
Transform(A,M,A1);
Transform(B,M,B1);
Transform(C,M,C1);
Transform(D,M,D1);
VeHinhChuNhat(hWnd);
return;
}
void Scaling(HWND hWnd)
{
double sx = -1.5, sy = -1.2;
double M[3][3] = {sx,0,0,
0,sy,0,
0,0,1};
Transform(A,M,A1);
Transform(B,M,B1);
Transform(C,M,C1);
Transform(D,M,D1);




−=
100
10
001
1
bM
Ma trận quay


















++
−

−=
100
010
001
3
M
Ma trận quay ngược


















++
+
−
+
=

10
001
5
bM
Ma trận
12345
MMMMMM =
















++
−
+
+
−
++
−

m
m
M
double m = 0.6, b = 100;
POINTH A = {100,40,1};
POINTH B = {200,40,1};
POINTH C = {200,100,1};
POINTH D = {100,100,1};
POINTH A1, B1, C1, D1;
void VeHinhChuNhat(HDC hdc, POINTH A, POINTH B, POINTH C, POINTH D, int
xc, int yc, COLORREF color)
{
HPEN hPen, hPenOld;
hPen = CreatePen(PS_SOLID,3,color);
hPenOld = (HPEN)SelectObject(hdc,hPen);
MoveToEx(hdc,xc+(int)A.x,yc-(int)A.y,NULL);
LineTo(hdc,xc+(int)B.x,yc-(int)B.y);
LineTo(hdc,xc+(int)C.x,yc-(int)C.y);
LineTo(hdc,xc+(int)D.x,yc-(int)D.y);
LineTo(hdc,xc+(int)A.x,yc-(int)A.y);
SelectObject(hdc,hPenOld);
DeleteObject(hPen);
return;
}
void MMatrix(double C[3][3], double A[3][3], double B[3][3])
{
int m, n, p;
for (m=0; m<3; m++)
for (p=0; p<3; p++) {
C[m][p] = 0;

double M4[3][3] = {1/sqrt(m*m+1),-m/sqrt(m*m+1),0,
m/sqrt(m*m+1), 1/sqrt(m*m+1),0,
0 , 0 , 1};
double M5[3][3] = {1,0,0,
0,1,b,
0,0,1};
double M[3][3],T1[3][3], T2[3][3], T3[3][3];
MMatrix(T1,M5,M4);
MMatrix(T2,T1,M3);
MMatrix(T3,T2,M2);
MMatrix(M,T3,M1);
Transform(A,M,A1);
Transform(B,M,B1);
Transform(C,M,C1);
Transform(D,M,D1);
VeHinhChuNhat(hdc, A1, B1, C1, D1, xc, yc, RGB(255,0,0));
ReleaseDC(hWnd,hdc);
return;
}
void Symmetric(HWND hWnd)
{
HDC hdc;
int xc, yc;
RECT rt;
hdc = GetDC(hWnd);
GetClientRect(hWnd,&rt);
xc = rt.right/2;
yc = rt.bottom/2;
double M[3][3] = {-(m*m-1)/(m*m+1), 2*m/(m*m+1) , -2*b*m/(m*m+1),
2*m/(m*m+1) ,(m*m-1)/(m*m+1), 2*b/(m*m+1),

p2 = p;
c = c1;
c1 = c2;
c2 = c;
}
return;
}
int Round(double a)
{
return (int)(a+0.5);
}
int CohenSutherland(POINT &p1, POINT &p2)
{
HSC c1, c2;
POINT p;
while (TRUE) {
Encode(p1,c1);
Encode(p2,c2);
if ((c1.l && c2.l) || (c1.t && c2.t) || (c1.r && c2.r) || (c1.b &&
c2.b))
return 0;
else if (c1.l+c1.t+c1.r+c1.b+c2.l+c2.t+c2.r+c2.b==0)
return 1;
else {
swap(p1,c1,p2,c2);
if (c1.l) {
p.x = xmin;
p.y = Round(1.0*(p2.y-p1.y)/(p2.x-p1.x)*(p.x-p1.x)+p1.y);
}
else if (c1.t) {

}
Câu 6:
Xây dựng và cài đặt thuật toán xén đa giác của Sutherland-Hodgeman.
Đáp án:
Xét từng cạnh cửa sổ xén LEFT, TOP, RIGHT và BOTTOM.
Ta có 4 trường hợp sau:
Trường hợp 1: Đỉnh S và P nằm hoàn toàn ở miền trong của cạnh cửa sổ xén đang xét,
đỉnh P được thêm vào danh sách.
Trường hợp 2: Đỉnh S ở miền trong, còn đỉnh P nằm ở miền ngoài của cạnh cửa sổ xén
đang xét, giao điểm I được thêm vào danh sách.
Trường hợp 3: Đỉnh S và P nằm ở miền ngoài của cạnh cửa sổ xén đang xét, ta không
thêm gì vào danh sách.
Trường hợp 4: Đỉnh S nằm ở miền ngoài, còn đỉnh P nằm ở miền trong của cạnh cửa sổ
xén đang xét, giao điểm I và P được thêm vào danh sách.
int xmin = 200, ymin = 200;
int xmax = 600, ymax = 500;
void VeCuaSoXen(HWND hWnd)
{
HDC hdc;
hdc = GetDC(hWnd);
Rectangle(hdc,xmin,ymin,xmax,ymax);
ReleaseDC(hWnd,hdc);
return;
}
void XenCanhLeft(POLYGON &P, POLYGON &Q)
{
Q.NumVert = 0;
double y;
for (int n=0; n<P.NumVert; n++) {
/***************************************************/

Q.Vert[Q.NumVert].y = Round(y);
Q.NumVert++;
Q.Vert[Q.NumVert] = P.Vert[n+1];
Q.NumVert++;
}
}
return;
}
void XenCanhTop(POLYGON &P, POLYGON &Q)
{
Q.NumVert = 0;
double x;
for (int n=0; n<P.NumVert; n++) {
/***************************************************/
/* Truong hop 1: S va P nam hoan toan o mien trong */
/* Dinh P duoc them vao danh sach */
/***************************************************/
if (P.Vert[n].y>=ymin && P.Vert[n+1].y>=ymin) {
Q.Vert[Q.NumVert] = P.Vert[n+1];
Q.NumVert++;
}
/****************************************************/
/* Truong hop 2: S o mien trong va P o mien ngoai */
/* Giao diem I duoc them vao danh sach*/
/****************************************************/
else if (P.Vert[n].y>=ymin && P.Vert[n+1].y<ymin) {
x = 1.0*(P.Vert[n+1].x - P.Vert[n].x)*(ymin-P.Vert[n].y)/
(P.Vert[n+1].y - P.Vert[n].y) + P.Vert[n].x;
Q.Vert[Q.NumVert].x = Round(x);
Q.Vert[Q.NumVert].y = ymin;

/***************************************************/
if (P.Vert[n].x<=xmax && P.Vert[n+1].x<=xmax) {
Q.Vert[Q.NumVert] = P.Vert[n+1];
Q.NumVert++;
}
/****************************************************/
/* Truong hop 2: S o mien trong va P o mien ngoai */
/* Giao diem I duoc them vao danh sach*/
/****************************************************/
else if (P.Vert[n].x<=xmax && P.Vert[n+1].x>xmax) {
y = 1.0*(P.Vert[n+1].y - P.Vert[n].y)*(xmax-P.Vert[n].x)/
(P.Vert[n+1].x - P.Vert[n].x) + P.Vert[n].y;
Q.Vert[Q.NumVert].x = xmax;
Q.Vert[Q.NumVert].y = Round(y);
Q.NumVert++;
}
/****************************************************/
/* Truong hop 3: S va P deu nam o mien ngoai */
/* Ta khong them gi ca */
/****************************************************/
/****************************************************/
/* Truong hop 4: S nam ngoai, P nam o mien trong */
/* Giao diem I va P duoc them vao ds */
/****************************************************/
else if (P.Vert[n].x>xmax && P.Vert[n+1].x<=xmax) {
y = 1.0*(P.Vert[n+1].y - P.Vert[n].y)*(xmax-P.Vert[n].x)/
(P.Vert[n+1].x - P.Vert[n].x) + P.Vert[n].y;
Q.Vert[Q.NumVert].x = xmax;
Q.Vert[Q.NumVert].y = Round(y);
Q.NumVert++;

/****************************************************/
/* Truong hop 3: S va P deu nam o mien ngoai */
/* Ta khong them gi ca */
/****************************************************/
/****************************************************/
/* Truong hop 4: S nam ngoai, P nam o mien trong */
/* Giao diem I va P duoc them vao ds */
/****************************************************/
else if (P.Vert[n].y>ymax && P.Vert[n+1].y<=ymax) {
x = 1.0*(P.Vert[n+1].x - P.Vert[n].x)*(ymax-P.Vert[n].y)/
(P.Vert[n+1].y - P.Vert[n].y) + P.Vert[n].x;
Q.Vert[Q.NumVert].x = Round(x);
Q.Vert[Q.NumVert].y = ymax;
Q.NumVert++;
Q.Vert[Q.NumVert] = P.Vert[n+1];
Q.NumVert++;
}
}
return;
}
void XenDaGiac(HWND hWnd, POLYGON &P)
{
HDC hdc;
hdc = GetDC(hWnd);
HPEN hPen, hPenOld;
POLYGON Q;
P.Vert[P.NumVert] = P.Vert[0];
XenCanhLeft(P,Q);
hPen = CreatePen(PS_SOLID,1,RGB(255,0,0));
hPenOld = (HPEN)SelectObject(hdc,hPen);

LineTo(hdc,Q.Vert[0].x,Q.Vert[0].y);
Q.Vert[Q.NumVert] = Q.Vert[0];
P = Q;
SelectObject(hdc,hPenOld);
DeleteObject(hPen);
ReleaseDC(hWnd,hdc);
return;
}
Câu 7:
Xây dựng và cài đặt thuật toán vẽ ngôi nhà đơn giản dùng mô hình khung dây như hình
vẽ.
Đáp án:
typedef struct tagPOINT3D {
double x, y, z;
} POINT3D;
typedef struct tagPOINT2D {
double x, y;
} POINT2D;
#define MAXVERT 50
#define MAXEDGE 100
typedef struct tagWIREFRAME {
int NumVert;
int NumEdge;
POINT3D Vert[MAXVERT];
int Edge[MAXEDGE][2];
} WIREFRAME;
void PhepChieuSongSongTrucGiao(POINT3D p, POINT2D &q)
{
q.x = p.x;
q.y = p.y;

wf.Vert[2].x = 0; wf.Vert[2].y = 1; wf.Vert[2].z = 1;
wf.Vert[3].x = 0; wf.Vert[3].y = 0.5; wf.Vert[3].z = 1.5;
wf.Vert[4].x = 0; wf.Vert[4].y = 0; wf.Vert[4].z = 1;
wf.Vert[5].x = 1; wf.Vert[5].y = 0; wf.Vert[5].z = 0;
wf.Vert[6].x = 1; wf.Vert[6].y = 1; wf.Vert[6].z = 0;
wf.Vert[7].x = 1; wf.Vert[7].y = 1; wf.Vert[7].z = 1;
wf.Vert[8].x = 1; wf.Vert[8].y = 0.5; wf.Vert[8].z = 1.5;
wf.Vert[9].x = 1; wf.Vert[9].y = 0; wf.Vert[9].z = 1;
wf.Edge[0][0] = 0; wf.Edge[0][1] = 1;
wf.Edge[1][0] = 1; wf.Edge[1][1] = 2;
wf.Edge[2][0] = 2; wf.Edge[2][1] = 3;
wf.Edge[3][0] = 3; wf.Edge[3][1] = 4;
wf.Edge[4][0] = 4; wf.Edge[4][1] = 0;
wf.Edge[5][0] = 5; wf.Edge[5][1] = 6;
wf.Edge[6][0] = 6; wf.Edge[6][1] = 7;
wf.Edge[7][0] = 7; wf.Edge[7][1] = 8;
wf.Edge[8][0] = 8; wf.Edge[8][1] = 9;
wf.Edge[9][0] = 9; wf.Edge[9][1] = 5;
wf.Edge[10][0] = 6; wf.Edge[10][1] = 1;
wf.Edge[11][0] = 7; wf.Edge[11][1] = 2;
wf.Edge[12][0] = 8; wf.Edge[12][1] = 3;
wf.Edge[13][0] = 9; wf.Edge[13][1] = 4;
wf.Edge[14][0] = 5; wf.Edge[14][1] = 0;
wf.Edge[15][0] = 0; wf.Edge[15][1] = 2;
wf.Edge[16][0] = 1; wf.Edge[16][1] = 4;
// Nhan voi he so ty le de ve ra man hinh
int n, scale = 200;
for (n=0; n<wf.NumVert; n++) {
wf.Vert[n].x = scale*wf.Vert[n].x;
wf.Vert[n].y = scale*wf.Vert[n].y;

hPenOld = (HPEN)SelectObject(hdc,hPen);
MoveToEx(hdc,xc+(int)q1.x,yc+(int)q1.y,NULL);
LineTo(hdc,xc+(int)q2.x,yc+(int)q2.y);
SelectObject(hdc,hPenOld);
DeleteObject(hPen);
}
else {
MoveToEx(hdc,xc+(int)q1.x,yc+(int)q1.y,NULL);
LineTo(hdc,xc+(int)q2.x,yc+(int)q2.y);
}
}
ReleaseDC(hWnd,hdc);
return;
}
Câu 8:
Xây dựng và cài đặt thuật toán vẽ mặt trụ đứng có bán kính R và chiều cao A như hình
vẽ.
Đáp án:
Ta có phương trình tham số của mặt trụ là
),sin,cos(),( AvuRuRvup =
với
π
2 0
=
u

và
1 0=v
typedef struct tagPOINT3D {
double x, y, z;

for (n=0; n<=N; n++) {
v = n*dv;
for (m=0; m<M; m++) {
u = m*du;
p.x = R*cos(u);
p.y = R*sin(u);
p.z = A*v;
QuayQuanhOx(p,q,-theta);
// chuyen thanh he toa do cua man hinh
temp = q;
q.x = temp.x;
q.y = -temp.z;
q.z = -temp.y;
// Dung phep chieu song song truc giao
// Bo z di;
SetPixel(hdc,xc+(int)q.x,yc+(int)q.y,RGB(255,0,0));
//Sleep(10);
}
}
ReleaseDC(hWnd,hdc);
return;
}
Câu 9:
Xây dựng và cài đặt thuật toán vẽ mặt nón có bán kính R và chiều cao A như hình vẽ.
Đáp án:
Ta có phương trình tham số của mặt nón là
),sin)1(,cos)1((),( AvuRvuRvvup −−=
với
π
2 0=u

int R = 100, A = 150;
POINT3D p, q, temp;
double theta = 15*pi/180;
hdc = GetDC(hWnd);
for (n=0; n<=N; n++) {
v = n*dv;
for (m=0; m<M; m++) {
u = m*du;
p.x = (1-v)*R*cos(u);
p.y = (1-v)*R*sin(u);
p.z = A*v;
QuayQuanhOx(p,q,-theta);
// chuyen thanh he toa do cua man hinh
temp = q;
q.x = temp.x;
q.y = -temp.z;
q.z = -temp.y;
// Dung phep chieu song song truc giao
// Bo z di;
SetPixel(hdc,xc+(int)q.x,yc+(int)q.y,RGB(255,0,0));
Sleep(10);
}
}
ReleaseDC(hWnd,hdc);
return;
}
Câu 10:
Xây dựng và cài đặt thuật toán vẽ mặt nón cụt có bán kính mặt dưới là R, bán kính mặt
trên là r và chiều cao A như hình vẽ.