TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
Đề Tài:
Cài Đặt Thuật Toán Xén Một Đa Giác Vào Một Vùng Hình
Chữ Nhật
Giảng viên hướng dẫn: Nguyễn Thị Cẩm Ngoan
Lớp: Khoa Học Máy Tính 1-k5
Nhóm thực hiện : Nhóm 16
Thành viên trong nhóm :
1. Bùi Mạnh Toàn
Hà Nội, tháng 02 năm 2013
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
LỜI NÓI ĐẦU
Đồ Họa Máy Tính là một lĩnh vực của Công Nghệ Thông Tin, ở đó nghiên cứu, xây
dựng và tập hợp các công cụ (mô hình lý thuyết và phần mềm) khác nhau để kiến tạo,
xây dựng, lưu trữ và xử lý các mô hình và hình ảnh của các đối tượng, sự vật, hiện tượng
trong cuộc sống, sản xuất, nghiên cứu.
Đồ Họa Máy Tính góp phần quan trọng làm cho giao tiếp giữa con người và máy tính
trở nên thân thiện hơn. Trong lĩnh vực kỹ thuật máy tính, Đồ Họa Máy Tính càng ngày
càng phát triển mạng mẽ. Từ đồ họa trên máy tính chúng ta có nhiều lĩnh vực có ứng
dụng rất quan trọng của Đồ Họa Máy Tính trong thực tế như: tạo mô hình, hoạt cảnh
(game, giải trí,…), hỗ trợ thiết kế đồ họa, mô phỏng hình ảnh, chuẩn đoán hình ảnh
(trong Y tế), huấn luyện đào tạo ảnh (quân sự, hàng không,…), …
Trong Đồ Họa Máy Tính có nhiều thuật toán khác nhau. Xong mỗi thuật toán lại tỏ ra
có những ưu việt và hạn chế riêng đối với từng bài toán cụ thể. Và để phục vụ cho việc
tìm hiểu thêm về các thuật toán trong Đồ Họa Máy Tính, Nhóm 16 chúng em với sự
hướng dẫn của Giảng viên – Th.s Nguyễn Thị Cẩm Ngoan – Khoa CNTT – Trường
ĐH Công Nghiệp Hà Nội đã thực hiện đề tài: “Cài đặt thuật toán xén một đa giác vào
một vùng hình chữ nhật”.
Chúng em xin gửi lời cảm ơn chân thành tới cô giáo: “Nguyễn Thị Cẩm Ngoan” đã
tận tâm chỉ bảo và giúp đỡ chúng em hoàn thành đề tài này. Trong quá trình làm đề tài sẽ

TÀI LIỆU THAM KHẢO………………………………………….…………………42
Trang 4
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
PHẦN 1: GIỚI THIỆU CHUNG VỀ ĐỀ TÀI
I. Giới Thiệu Đề Tài.
Cùng với sự phát triển của nền kinh tế hiện nay là sự phát triển mạnh mẽ của ngành
công nghệ thông tin. Các ứng dụng của công nghệ thông tin ngày càng nhiều và có mặt
trong hầu hết các lĩnh vực của cuộc sống.
Với đề tài: “Cài đặt thuật toán xén một đa giác vào một vùng hình chữ nhật”,
nhóm 16 – lớp KHMT1K5 sẽ trình bày về thuật toán về xén hình Sutherland -
Hodgeman. Ý nghĩa của thuật toán xén hình trong công nghệ thông tin là không hề nhỏ,
đặc biệt là đối với màn hình máy tính thì nó có ý nghĩa vô cùng quan trọng.
Qua đề tài này nhóm 16 mong sẽ giúp ích được cho mọi người hiểu thêm phần nào về
thuật toán xén hình.
II. Giới Thiệu Ngôn Ngữ Lập Trình Được Sử Dụng Trong Đề Tài
Stroustrup đã bắt đầu làm việc với khái niệm lớp trong 1979. Ý tưởng tạo ra một ngôn
ngữ mới bắt nguồn từ kinh nghiệm lập trình khi mà ông viết luận án tiến sĩ. Stroustrup
nhận ra rằng Simulacó nhiều tính năng hữu dụng cho việc phát triển một phần mềm lớn
nhưng nó đã quá chậm trong ứng dụng thực tế, trong khi đó, BCPL lại nhanh nhưng ở
cấp quá thấp và không tiện cho việc phát triển phần mềm lớn. Đến khi làm việc ở Bell
Labs, thì ông gặp phải vấn đề trong việc phân tích nhân Unix với việc tính toán phân tán.
Dùng lại kinh nghiệm lúc làm luận án tiến sĩ, Stroustrup cài thêm các tính năng giống
như Simula vào trong C để nâng cao. C được chọn là vì đó là ngôn ngữ tổng quát, nhanh
và năng động. Lần đầu tiên, các chức năng như là lớp, lớp dẫn xuất, kiểm tra kiểu mạnh,
nội tuyến (inline), và đối số mặc định đã được thêm vào trong C. Lần xuất bản đầu tiên
vào thị trường xảy ra trong tháng 11/1985.
Năm 1983, thì tên C với các lớp được đổi thành C++. các chức năng mới được thêm vào
bao gồm hàm ảo, quá tải hàm và toán tử, tham chiếu, hằng, khả năng kiểm soát bộ nhớ
của lưu trữ tự do, nâng cao việc kiểm soát kiểu, và lệnh chú giải kiểu (//).
Năm 1985, tác phẩm The C++ Programming Language được xuất bản lần đầu tiên, cung

IV. Cách sử dụng thư viện đồ họa trong Dev-C++.
Đầu tiên bạn tải file đính kèm về máy mình, giải nén ra sẽ được 2 file là graphics.h và
libbgi.a
+ File graphics.h để ở thư mục C:\Dev-Cpp\include
+ File libbgi.a để ở thư mục C:\Dev-Cpp\lib
(Nếu bạn cài mặc đinh Dev C++ ở ổ C)
Tiếp theo bạn khởi động Dev C++ lên, vào File >New > Project >Empty
Project (Nhớ chọn C++ Project) >OK
Trang 6
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
Đặt tên cho Project của mình!
Nhấn chuột phải lên cái project của bạn >New File
Nhấn Alt + P >Chọn thẻ Parameters > Copy và paste vào ô Linker những dìng dưới
đây:
-lbgi
-lgdi32
-lcomdlg32
-luuid
-loleaut32
-lole32
(Bao gồm cả dấu "-")
>OK
Phần 2: Ý tưởng xây dựng chương trình và cài đặt thuật toán
I. Qui định hiển thị đối tượng 2 chiều
1.1. Một số khái niệm
Cửa sổ (window) là một vùng được chọn để hiển thị trong hệ tọa độ thế giới thực.
Vùng quan sát (viewport) là vùng đƣợc chọn trên thiết bị hiển thị để các đối tượng ở
trong cửa sổ ánh xạ vào.
Cửa sổ xác định cái gì được thấy trên thiết bị hiển thị, còn vùng quan sát xác định
nơi nào nó sẽ được hiển thị.

Sau khi thực hiện phép ánh xạ từ cửa sổ sang vùng quan sát, tất cả các phần của
đối tượng nằm ngoài vùng quan sát sẽ bị xén (clip) và toàn bộ những gì nằm trong vùng
quan sát sẽ được ánh xạ sang hệ tọa độ thiết bị (device coordinates - DC). Việc đưa ra hệ
tọa độ thiết bị chuẩn nhằm giúp cho việc tƣơng thích dễ dàng với nhiều loại thiết bị hiển
thị khác nhau.Bằng cách thay đổi vị trí của vùng quan sát chúng ta có thể quan sát các đối
tượng tại các vị trí khác nhau trên màn hình hiển thị, đồng thời, bằng cách thay đổi kích
thƣớc của vùng quan sát, chúng ta có thể thay đổi kích thước và tính cân xứng của các
đối tượng được hiển thị. Chúng ta có thể thực hiện các hiệu ứng thu phóng bằng cách ánh
xạ các cửa sổ có kích thước khác nhau vào vùng quan sát có kích thước cố định. Khi các
cửa sổ đƣợc thu nhỏ, phần nằm trong cửa sổ sẽ được phóng to giúp chúng ta dễ dàng
quan sát các chi tiết mà không thể thấy được trong các cửa sổ lớn hơn.
1.2. Hệ tọa độ quan sát và hệ tọa độ thiết bị chuẩn
1.2.1. Hệ tọa độ quan sát
Để thiết lập hệ tọa độ quan sát, trƣớc tiên ta sẽ chọn một điểm P
0
(x
0
, y
0
) trong hệ tọa
độ thế giới thực làm gốc tọa độ.
Trang 9
Chuyển đổi từ
hệ tọa độ cục
bộ sang hệ
tọa độ thế
giới thực
Chuyển đổi từ
hệ thế giới
thực sang hệ

quan sát là tích của hai ma trận của các phép biến đổi : phép tịnh tiến gốc tọa độ hệ quan
sát về gốc tọa độ hệ tọa độ thế giới thực, phép quay đưa các trục của hệ tọa
độ quan sát trùng với các trục của hệ tọa độ thế giới thực. M
WC,VC
=M
T
M
R
1.2.2. Hệ tọa độ thiết bị chuẩn
Do cách định nghĩa của các hệ tọa độ thiết bị khác nhau nên một hình ảnh hiển thị
được trên thiết bị này chưa chắc hiển thị chính xác trên thiết bị kia. Chính vì vậy cần phải
xây dựng hệ tọa độ thiết bị chuẩn đại diện chung cho các thiết bị để có thể mô tả các hình
ảnh của thế giới thực mà không phụ thuộc vào bất cứ thiết bị nào.
Trong hệ tọa độ này, các tọa độ x, y sẽ đƣợc gán các giá trị trong khoảng từ 0 đến 1.
Như vậy, vùng không gian của hệ tọa độ thiết bị chuẩn chính là hình vuông đơn vị có góc
trái dưới là (0,0) và góc phải trên (1,1).
Trang 10
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính

Hệ tọa độ thiết bị chuẩn
1.3. Các thuật toán xén hình
Thao tác loại bỏ các phần hình ảnh nằm ngoài một vùng cho trƣớc đƣợc gọi là xén
hình. Vùng được dùng để xén hình gọi là cửa sổ xén (clip window).
Tùy thuộc vào từng ứng dụng cụ thể mà cửa sổ xén có thể có dạng là đa giác hay là
đường cong khép kín. Để đơn giản, trong các thuật toán xén hình, cửa sổ xén được gọi là
cửa sổ.
II. Thuật toán Cohen-Sutherland
Đây là một trong những thuật toán ra đời sớm nhất và thông dụng nhất.
Bằng cách kéo dài các biên của cửa sổ, người ta chia mặt phẳng thành chín vùng gồm cửa
sổ và tám vùng xung quanh nó.

Thuật toán này sẽ tiến hành xén đa giác lần lƣợt với các biên cửa sổ. Đầu tiên, đa
giác sẽ được xén dọc theo biên trái của cửa sổ, kết quả sau bƣớc này sẽ được dùng để xén
tiếp biên phải, rồi cứ tƣơng tự nhƣ vậy cho các biên trên, dưới. Sau khi xén hết với bốn
biên của cửa sổ, ta đƣợc kết quả cuối cùng.
Với mỗi lần xén đa giác dọc theo một biên nào đó của cửa sổ, nếu gọi V
i
,V
i+1
là hai đỉnh
kề cạnh V
i
V
i+1
, ta có 4 trường hợp có thể xảy ra khi xét từng cặp đỉnh của đa giác ban đầu
với biên của cửa sổ như sau:
i) Nếu V
i
nằm ngoài, V
i+1
nằm trong, ta lưu giao điểm I của V
i
V
i+1
với biên của cửa sổ
và V
i+1
ii) Nếu cả V
i
, V
i+1

public:
float x;
float y;
PointCoordinates( )
{
x=0;
y=0;
}
};
Trang 14
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
class LineCoordinates
{
public:
float x_1;
float y_1;
float x_2;
float y_2;
LineCoordinates( )
{
x_1=0;
y_1=0;
x_2=0;
y_2=0;
}
LineCoordinates(const float x1,const float y1,const float x2,const float y2)
{
x_1=x1;
y_1=y1;
x_2=x2;

Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
void Polygon(const int,const int []);
void Rectangle(const int,const int,const int,const int);
void Line(const int,const int,const int,const int);
void Dashed_line(const int,const int,const int,const int,const int=0);
int main( )
{
int driver=VGA;
int mode=VGAHI;
initgraph(&driver,&mode,"");
show_screen( );
setcolor(15);
Line(90,150,90,390);
Line(50,350,320,350);
Line(400,150,400,390);
Line(360,350,580,350);
RectangularCoordinates WC(130,180,290,300);
RectangularCoordinates VC(440,230,550,300);
setcolor(15);
Line(90,180,95,180);
Line(90,300,95,300);
Line(130,345,130,350);
Line(290,345,290,350);
Line(400,230,405,230);
Trang 17
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
Line(400,300,405,300);
Line(440,345,440,350);
Line(550,345,550,350);
setcolor(15);

outtextxy(437,360,"min");
outtextxy(547,360,"max");
char Key=NULL;
do
{
Key=getch( );
}
while(Key!='T' && Key!='t');
settextstyle(0,0,1);
setcolor(0);
outtextxy(90,450," XIN CHAN THANH CAM ON ");
setcolor(15);
outtextxy(85,450," ");
setcolor(12);
Trang 19
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
outtextxy(213,450," ");
for(int count=0;count<n;count++)
apply_window_to_viewport_coordinate_transformation(WC,VC,polygon_verti
ces[(count*2)],polygon_vertices[((count*2)+1)]);
clip_polygon(VC,n,polygon_vertices);
getch( );
return 0;
}
void apply_window_to_viewport_coordinate_transformation(const
RectangularCoordinates wc,const RectangularCoordinates vc,int &x,int &y)
{
float Sx=((vc.x_max-vc.x_min)/(wc.x_max-wc.x_min));
float Sy=((vc.y_max-vc.y_min)/(wc.y_max-wc.y_min));
float Tx=vc.x_min;

window_line.x_1=wc.x_max;
window_line.y_1=wc.y_max;
window_line.x_2=wc.x_max;
window_line.y_2=wc.y_min;
Trang 21
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
}
else if(count_2==3)
{
window_line.x_1=wc.x_max;
window_line.y_1=wc.y_min;
window_line.x_2=wc.x_min;
window_line.y_2=wc.y_min;
}
else if(count_2==4)
{
window_line.x_1=wc.x_min;
window_line.y_1=wc.y_min;
window_line.x_2=wc.x_min;
window_line.y_2=wc.y_max;
}
int rule_no;
PointCoordinates point;
for(int count_4=1;count_4<number_of_edges;count_4++)
{
LineCoordinates line(edges[((count_4*2)-2)],edges[((count_4*2)-
1)],edges[(count_4*2)],edges[((count_4*2)+1)]);
rule_no=check_line(window_line,line);
switch(rule_no)
Trang 22

edges[count_6]=clipped_edges[count_6];
}
setcolor(10);
Polygon(number_of_edges,edges);
delete edges;
delete clipped_edges;
}
const int check_line(const LineCoordinates line,const LineCoordinates edge)
{
int rule_number=0;
int point_1=check_point(line,edge.x_1,edge.y_1);
int point_2=check_point(line,edge.x_2,edge.y_2);
if(point_1==1 && point_2==1)
rule_number=1;
else if(point_1!=1 && point_2!=1)
rule_number=2;
else if(point_1==1 && point_2!=1)
rule_number=3;
else if(point_1!=1 && point_2==1)
Trang 24
Báo cáo Bài Tập Lớn môn học Đồ Họa Máy Tính
rule_number=4;
return rule_number;
}
const int check_point(const LineCoordinates lc,const float x,const float y)
{
float c=(((lc.x_2-lc.x_1)*(y-lc.y_1))-((lc.y_2-lc.y_1)*(x-lc.x_1)));
if(c<=0)
return 1;
else