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 Cohen-Sutherland Để Xén Một
Tam Giác. Phân tích các trường hợp thuật toán sao cho kết quả là
các đoạn thẳng rời rạc.
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 19
Thành viên trong nhóm :
1. Hoàng Thị Nhài
2. Nguyễn Văn Trường
3. Nguyễn Văn Đinh
Hà Nội, tháng 02 năm 2013
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 trong những lĩnh vực lí thú nhất và phát triển nhanh nhất
của tin học. Ngay từ khi xuất hiện, đồ họa máy tính đã có sức lôi cuốn mãnh liệt, cuốn
hút rất nhiều người và được sử dụng ở nhiều lĩnh vực khác nhau như : khoa học, nghệ
thuật, kinh doanh, thương mại, công nghiệp, quản lí, giáo dục, giải trí, … Số lượng các
chương trình đồ họa ứng dụng thật khổng lồ và phát triển liên tục.
Với sự hứng thú về thuật toán Cohen-Sutheland nhóm chúng em quyết định chọn
đề tài “Cài đặt thuật toán Cohen-Sutheland để xén một tam giác. Phân tích các trường
hợp thuật toán này sao cho kết quả là các đoạn thẳng rời rạc” để có cơ hội tìm hiểu sâu
hơn về thuật toán và thư viện đồ họa của thuật toán này. Qua thời gian tìm hiểu, chúng
em đã tìm hiều được tổng quan về thuật toán Cohen-Sutheland và thấy rằng đây là một
thư viện rất thú vị.
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ẽ không tránh khỏi những sai sót, khuyết điểm. Vì vậy, nhóm thực hiện chúng em hy
vọng nhận được sự đánh giá và đóng góp nhiệt tình từ phía thầy cô và các bạn để bài của
nhóm chúng em được hoàn thiện hơn.

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 (//).
4
Bài Tập Lớn môn học Đồ Họa Máy Tính
Năm 1985, tác phẩm The C++ Programming Language được xuất bản lần đầu tiên, cung
cấp một tài liệu tham khảo quan trọng cho ngôn ngữ nhưng đó chưa là một tiêu chuẩn
chính thức.
Năm 1989 phiên bản C++ 2.0 phát hành. Các tính năng mới bao gồm đa kế thừa, lớp trừu
tượng, hàm tĩnh, hàm thành viên hằng, và thành viên bảo tồn.
Năm 1990, cuốn The Annotated C++ Reference Manual được xuất bản cung cấp nền
tảng cho tiêu chuẩn tương lai.
Phiên bản xuất bản sau đó có thêm các chức năng tiêu bản, ngoại lệ, không gian tên,
chuyển kiểu cho toán tử new, và kiểu Boolean.
Khi C++ hình thành, thì thư viện chuẩn hoàn thiện với nó. Thư viện C++ đầu tiên thêm
vào là iostream.h cung cấp cơ sở để thay thế các hàm C truyền thống như
là printf và scanf. Sàu này, trong những thư viện chuẩn quan trọng nhất được thêm vào
là Thư viện Tiêu bản Chuẩn.
Sau nhiều năm làm việc, có sự cộng tác giữa ANSI và hội đồng tiêu chuẩn hoá C++
của ISO để soạn thảo tiêu chuẩn ISO/IEC 14882:1998. Phiên bản tiêu chuẩn này được
phát hành năm 1989, hội đồng tiếp tục xử lí các báo cáo trục trặc, và ấn hành một phiên
bản sửa sai của chuẩn C++ trong năm 2003.
Không ai là chủ nhân của ngôn ngữ C++, nó hoàn toàn miễn phí khi dùng. Mặc dù vậy,
các văn bản tiêu chuẩn thì không miễn phí.

(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ị.
Ở đây chúng ta nên phân biệt khái niệm cửa sổ đƣợc dùng trong phần này với khái
niệm cửa sổ đƣợc dùng trong các chương trình ứng dụng trên các hệ điều hành như
Windows.
Thông thường cửa sổ và vùng quan sát có dạng hình chữ nhật, có các cạnh song song
với các trục tọa độ. Tuy nhiên chúng cũng còn có một số dạng khác như đa giác, hình
tròn, …
Quá trình ánh xạ một vùng định nghĩa trong hệ tọa độ thế giới thực vào một vùng
trong hệ tọa độ thiết bị được gọi là phép biến đổi hệ quan sát (viewing transformation).
6
Bài Tập Lớn môn học Đồ Họa Máy Tính
Phép biến đổi hệ quan sát với cửa sổ và vùng quan sát có dạng là các hình chữ nhật
Quy trình hiển thị các đối tượnng trong đồ họa hai chiều có thể được mô tả qua sơ
đồ sau :
Trước tiên, các đối tượng sẽ đƣợc mô tả bằng các đối tượng đồ họa cơ sở và các
thuộc tính của chúng trong từng hệ tọa độ cục bộ (modeling coordinates - MC) nhằm đơn
giản hóa và tận dụng các đặc trƣng riêng của từng loại. Sau đó, chúng ta sẽ dùng các
phép biến đổi hệ tọa độ để chuyển các mô tả từ các hệ tọa độ cục bộ này sang một hệ tọa
độ thế giới thực (world coordinates - WC) duy nhất chứa toàn bộ các đối tƣợng thành
phần. Phép chuyển đổi này đƣợc gọi là phép chuyển đổi mô hình (modeling coordinates
transformation).

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 độ.
Sau đó chúng ta sẽ sử dụng một vector V mô tả hướng quan sát để định hướng cho
trục tung y
v
của hệ tọa độ. Vector V được gọi là view-up vector.
Từ V chúng ta có thể tính đƣợc các vector đơn vị v = (v
x
v
y
) và u = (u

Bài Tập Lớn môn học Đồ Họa Máy Tí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ó.
1. Khái niệm mã vùng (area code)
Một con số 4 bit nhị phân gọi là mã vùng sẽ được gán cho mỗi vùng để mô tả vị trí
tương đối của vùng đó so với cửa sổ. Bằng cách đánh số từ 1 đến 4 theo thứ tự từ phải
qua trái, các bit của mã vùng được dùng theo quy ước sau để chỉ một trong bốn vị trí
tương đối của vùng so với cửa sổ bao gồm : trái, phải, trên, dưới.
Bit 1 : trái (LEFT)
Bit 2 : phải (RIGHT)
Bit 3 : trên (TOP)
Bit 4 : dưới (BOTTOM)
10
Bài Tập Lớn môn học Đồ Họa Máy Tính

Giá trị 1 tương ứng với vị trí bit nào trong mã vùng sẽ chỉ ra rằng điểm đó ở vị
trí tương ứng, ngược lại bit đó sẽ được đặt bằng 0. Ví dụ một vùng có mã là 1001, thì nó
sẽ nằm phía dưới (bit 4 bằng 1), bên trái (bit 1 bằng 1) so với cửa sổ, vùng có mã là 0000
chính là cửa sổ.
Các giá trị bit trong mã vùng đƣợc tính bằng cách xác định tọa độ của điểm (x, y)
thuộc vùng đó với các biên của cửa sổ.
Bit 1 được đặt là 1 nếu x < xmin, các bit khác được tính tương tự.
2.Thuật toán Cohen-Sutherland

toàn bộ.
Hình 4.8-Minh
hoa thuật toán Cohen-
Sutherland
Các điểm giao với các biên cửa sổ
của đoạn thẳng có thể được tính từ phương trình tham số như đã đề cập ở phần trên. Tung
độ y của điểm giao đoạn thẳng với biên đứng của cửa sổ có thể tính từ công thức
y=y1+m(x-x1), trong đó x có thể là Xmin hay Xmax. Tương tự, hoành độ x của điểm
giao đoạn thẳng với biên ngang của cửa sổ có thể tính công thức :x=x1+(y-y1)/m, trong
đó y có thể là Ymin hay Ymax.
Lưu đồ thuật toán Cohen-Sutherland dùng để xén một đoạn thẳng qua 2 điểm
(x1,y1) và (x2,y2) vào cửa sổ hình chữ nhật cho trước
12
Bài Tập Lớn môn học Đồ Họa Máy Tính

Cài đặt minh họa thuật toán Cohen-Sutherland:
#include<graphics.h>
#include<math.h>
13
Bài Tập Lớn môn học Đồ Họa Máy Tính
#include<dos.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void cohen(int x1,int y1,int x2,int y2,int xa, int ya, int xb,int yb)
{
int a[4],b[4],i,kthuc=0;
while(kthuc==0)
{
a[1]=a[2]=a[3]=a[4]=0;

if(a[1]==1)
{
ya=(yb-ya)*(x1-xa)/(xb-xa)+ya;
xa=x1; //cout<<xa<<" "<<ya<<endl;
}
if(a[2]==1)
15
Bài Tập Lớn môn học Đồ Họa Máy Tính
{
ya=(yb-ya)*(x2-xa)/(xb-xa)+ya;
xa=x2;
}
if(a[3]==1)
{
xa=(xb-xa)*(y1-ya)/(yb-ya)+xa;
ya=y1;
}
if(a[4]==1)
{
xa=(xb-xa)*(y2-ya)/(yb-ya)+xa;
ya=y2;
}
}
}
}
}
int main()
{
int md=0, dr=0;
initgraph(&md,&dr,"C:\\Dev-Cpp");

NewYork, 1990, 754 tr.
• James D.Foley, Andries Van Dam, Feiner, John Hughes. Introduction to
Computer Graphics. Addision Wesley, NewYork, 1995, 559 tr.
• James D.Foley, Andries Van Dam, Feiner, John Hughes. Computer Graphics -
Principle and Practice. Addision Wesley, NewYork, 1996, 1175 tr.
• Dương Anh Đức, Lê Đình Duy. Giáo trình Đồ họa máy tính. Khoa Công nghệ
thông tin, Trường Đại học Khoa học Tự nhiên (lưu hành nội bộ), 1996, 237 tr.
• Hoàng Kiếm, Dương Anh Đức, Lê Đình Duy, Vũ Hải Quân. Giáo trình Cơ sở
Đồ họa Máy Tính, NXB Giáo dục, 2000.
• Donald Hearn, M.Pauline Baker. Computer Graphics, C version. Prentice Hall
International Inc, Upper Saddle River, New Jersey, 1997, 652tr
• Slide bài giảng Đồ Họa Máy Tính - Ths. Vũ Minh Yến - Trường ĐH Công
Nghiệp Hà Nội.
• Giáo trình Kỹ Thuật Đồ Họa - Lâm Thị Ngọc Châu.
• Bài viết: “Xử lý các trường hợp đặc biệt trong bài toán tô màu đa giác bằng
thuật toán Scanline” tại: http://www.schoolnet.vn/modules.php?
name=News&file=article&sid=2489
• Và 1 số bài viết tại: http://msdn.microsoft.com/en-us/library/gg145023
19
Bài Tập Lớn môn học Đồ Họa Máy Tính
20