ĐẠI HỌC THÁI NGUYÊN
NGUYỄN THANH HOA
MỘT SỐ THUẬT TOÁN LIÊN QUAN ĐẾN
NỘI DUNG HÌNH HỌC
Chuyên ngành: Tin học
LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC

Người hướng dẫn khoa học:
Thạc sĩ: Nguyễn Văn An
THÁI NGUYÊN - 2010
2
MỤC LỤC
Trang
Trang bìa phụ 1
Mục lục 2
Mở đầu 4
1. Lý do chọn đề tài 4
2. Mục đích - yêu cầu và phạm vi nghiên cứu 5
3. Phương pháp nghiên cứu 5
4. Cấu trúc của luận văn 5
Chương 1. Cơ sở lý thuyết 7
1.1. Một số đối tượng hình học 7
1.1.1. Điểm 7
1.1.2. Đường thẳng 7
1.1.3. Đoạn thẳng 8
1.1.4. Đa giác 8
1.2. Phương trình tương quan giữa điểm và đường thẳng, đoạn thẳng 9
1.2.1. Tương quan giữa điểm và đường thẳng 9
1.2.2. Tương quan giữa điểm và đoạn thẳng 10
1.3. Giao giữa đường thẳng, đoạn thẳng 10
1.3.1. Đường thẳng cắt đường thẳng 10

3.5. Một số bộ test 46
3.6. Đánh giá thuật toán 50
3.7. Mở rộng 50
Kết luận 51
Tài liệu tham khảo 52
Phụ lục 53

4
MỞ ĐẦU
1. Lý do chọn đề tài
Như chúng ta đã biết Toán học có ảnh hưởng rất lớn đến mọi lĩnh vực
của cuộc sống. Các bài toán trong tin học nếu có thuật toán giải dựa trên cơ sở
lý thuyết toán học vững chắc thì sẽ đem lại kết quả tốt. Điều đó được khẳng
định rõ trong các bài toán liên quan đến nội dung về hình học. Những bài toán
dạng này đòi hỏi người lập trình không những phải nắm vững các kiến thức
về toán học mà còn phải có tư duy thuật toán tốt.
Đa số các thuật toán đều tập trung vào dữ liệu kiểu văn bản và kiểu số,
chúng được thiết kế và xử lý sẵn trong phần lớn các môi trường lập trình. Đối
với các bài toán hình học thì tình huống khác hẳn, ngay cả các phép toán sơ
cấp trên các đối tượng là điểm và đoạn thẳng cũng có thể là một thách thức về
tính toán và lập trình. Những bài toán hình học thường trực quan và cũng
không quá khó về mặt giải thuật nhưng lại rườm rà về mặt chương trình.
Chính vì thế mà chỉ cần một sai sót nhỏ cũng dẫn đến việc khó có thể chỉnh
sửa chương trình trong thời gian cho phép. Bên cạnh đó, trên thực tế nhiều bài
toán hình học có thể giải quyết được ngay lập tức bằng cách nhìn vào hình vẽ
nhưng lại đòi hỏi những chương trình không đơn giản, ví dụ như kiểm tra một
điểm có nằm trong đa giác hay không?. Có thể vì những lý do như trên mà
nhiều nguời còn e ngại khi lập trình các bài toán liên quan đến nội dung hình
học mặc dù họ không hề phủ nhận đó là những bài toán rất hay.
Xuất phát từ nhận thức trên, được sự đồng ý của Hội đồng khoa học

6
Tôi xin cảm ơn các bạn sinh viên lớp sư phạm Tin Học K37 đã cổ vũ
động viên tôi trong quá trình thực hiện khóa luận!
Dù đã có nhiều cố gắng nhưng luận văn không tránh khỏi những thiếu
sót, tác giả rất mong nhận được sự đóng góp ý kiến của các Thầy, Cô và các
bạn để khóa luận được hoàn thiện.
7
Chương 1. CƠ SỞ LÝ THUYẾT
Chương này giới thiệu những cơ sở lý thuyết cơ bản nhất về các đối
tượng hình học, qua đó giúp đọc giả có thể hiểu rõ hơn về các đối tượng hình
học và mối tương quan giữa chúng.
1.1. Một số đối tượng hình học
1.1.1. Điểm
Điểm thường được xét bằng một cặp số thực là tọa độ của điểm đó
trong hệ trục tọa độ Descarter thường dùng [4].
Trong hầu hết các bài toán hình học chúng ta sẽ dùng kiểu lưu trữ đơn
giản, dễ hiểu như sau:
typedef struct
{
float x, y;
}xy;
Chính vì vậy khi xét tới tọa độ của P(x, y) thì ta xét tới P.x, P.y.
Chúng ta có thể tính được khoảng cách giữa hai điểm A(x1, y2), B(x2,
y2) trong mặt phẳng tọa độ như sau:
float khoangcach (xy A, xy B)
{float T;
T = sqrt ((A.x - B.x)* (A.x- B.x) +(A.y - B.y)*(A.y- B.y));
return T;
}
1.1.2. Đường thẳng

y1); B(x2, y2); C(x3, y3); D(x4, y4). Nhưng có một điều đặc biệt là chúng ta
chỉ cần xác định tọa độ đỉnh của hai đỉnh đối nhau thì xác định được một hình
chữ nhật duy nhất. Chính vì thế thông thường chúng ta gọi tọa độ của điểm
dưới trái và điểm trên phải là hai điểm đặc trưng cho hình chữ nhật đó [4].
1.1.4.3. Đa giác
Đa giác là một dãy các điểm với hai điểm liên tiếp được nối bởi một
đoạn thẳng, và điểm đầu nối với điểm cuối tạo thành một hình gấp khúc khép
kín.
9
Đa giác được gọi là đa giác lồi khi mọi điểm còn lại của đa giác nằm
cùng phía với nhau so với một cạnh nào đó [4].
Để tính diện tích đa giác (lồi hoặc lõm và không tự cắt) gồm n đỉnh A[1],
A[2], , A[n] ta làm như sau:
Chia đa giác thành n - 2 tam giác rồi tính tổng diện tích của các tam
giác ấy. Tuy nhiên phương pháp này dài dòng, ta làm cách khác như sau:
Chia đa giác thành các hình thang bằng cách chiếu các cạnh xuống trục
hoành (hình vẽ). Hình thang được xác lập bởi cạnh A[i]A[i+1] có diện tích là
Abs (S) với:
Sau khi gán đỉnh A[n+1] = A[1] ta tính diện tích
toàn phần của đa giác như sau:
S = 0;
For (i: = 1; i< = n; i++)
S = (1/2) * Abs (S);
Chú ý:
a. Hoàn toàn tương tự ta có thể tìm diện tích của đa giác bằng cách
chiếu các cạnh xuống trục tung.
b. Nếu thay bước gán S = (1/2) * abs (S) bởi S = S/2 thì dấu của S là
dương hay âm sẽ cho ta biết chiều đánh số của các đỉnh theo thứ tự từ 1, 2, ,
n là ngược hay xuôi chiều kim đồng hồ.
c. Thông thường ta dùng mảng một chiều để biểu diễn một đa giác.

a
), B(x
b
, y
b
)
có dạng: F(x, y) = (x- x
a
) * (y
b
- y
a
) - (y - y
a
) * (x
b
- x
a
) = 0.
Vậy phương trình tương quan giữa điểm M(x
m
, y
m
) với đường thẳng đi
qua hai điểm A, B phân biệt là:
F(x
m
, y
m
) = (x

Chúng ta biết rằng, đoạn thẳng là một phần đường thẳng. Nên mối
tương quan giữa điểm M(x
m
, y
m
) với đoạn thẳng AB, (A(x
a
, y
b
), B(x
b
, y
b
)) như
sau:
Điểm M nằm trên đoạn AB khi nó thỏa mãn 2 điều kiện sau:
1. M phải thuộc đường thẳng đi qua A, B
⇔
F (A, B, M) = 0.
2. M nằm giữa Avà B
⇔
(x
m
- x
a
)*(x
m
- x
b
) < = 0 và (y

1.3.2. Đường thẳng cắt đoạn thẳng
Cho phương trình đường thẳng A1*x + B1*y + C1 = 0 (1) và đoạn
AB, A(x1, y1), B(x2, y2).
Đặt A2 = y1- y2; B2 = x2- x1;
C2 = - (A2*x1 + B2 * y1);
D = A1*B2 - A2*B1;
Dx = B1*C2 - B2*C1;
Dy = A2*C1 - A1* C2;
Mối quan hệ giữa (1) và AB được thể hiện:
* Nếu D
≠
0 và điểm P(Dx/D, Dy/D) nằm trên đoạn AB thì (1) cắt đoạn AB.
* Nếu D
≠
0 và điểm P(Dx/D, Dy/D) nằm ngoài đoạn AB thì (1) cắt đường
thẳng chứa AB nhưng không cắt AB.
* Nếu D = Dx = Dy = 0 thì AB trùng với (1).
* Nếu D = 0, Dx
≠
0 hoặc Dy
≠
0 thì AB song song với (1).
1.3.3. Đoạn thẳng cắt đoạn thẳng
Kiến thức phổ thông như sau: “Trong mặt phẳng tọa độ cho đường
thẳng d: ax + by + c = 0. Khi ấy, một trong hai nửa mặt phẳng bờ d, ngoại trừ
d, gồm các điểm có tọa độ thoả mãn bất phương trình: ax + by + c > 0. Nửa
12
mặt phẳng kia gồm các điểm có tọa độ thoả mãn bất phương trình: ax + by + c
< 0”.
Từ đó ta dễ dàng chứng minh được kết quả sau: “Điều kiện cần và đủ

xy A, B, C, D ;
// Tinh gia tri ham F tai diem M voi F la ham ung voi phuong trinh duong
thang đi qua AB
float F(xy A, xy B, xy M)
{ float T;
T = (M.x - A.x) * (B.y - A.y) - (M.y - A.y)* (B.x - A.x);
return T;
}
int KhacPhia (xy A, xy B, xy C, xy D)
// Kiem tra xem C, D co nam khac phia so voi đuong thang đi qua A, B hay khong?
13
{ int t;
If ( F ( A,B,C) * F( A, B, D) ) < = 0 ) t = 1;
Else t = 0;
}
void main()
{printf( “ nhap toa do A, B”);
scanf(“%f%f%f%f” , &A.x, &A.y, &B.x, &B.y);
printf( “ nhap toa do C, D”);
scanf(“%f%f%f%f”,&C.x, &C.y, &D.x, &D.y);
If (khacphia(A,B,C,D) = = 1 && Khacphia (C,D,A,B) = = 1)
Printf (“Hai đoan thang cat nhau”);
Else printf (“

Khong cat nhau”);
Getch();}
1.4. Một số bài tập áp dụng
1.4.1. Kiểm tra một điểm thuộc một tia
Bài toán: kiểm tra điểm M có thuộc tia AB hay không?
Điểm M thuộc tia AB ⇔ 2 điều kiện

- x
c
)*(x
m
- x
d
) ≤ 0 và (y
m -
y
c
)*(y
m
- y
d
) ≤ 0.
2. A không nằm giữa B, M ⇔ (x
m
- x
a
)*(x
b
- x
a
) ≥ 0 và (y
m
- y
a
)*(y
b
- y

(abs(A. y + i * (B. y - A. y)) < = Ymax) i++;
M.x = A. x

+ i * (B.x - A.x);
M.y = A. y

+ i * (B.y - A.y);
}
void Ket_qua()
{If ( Khacphia (A,B,C,D) = = 1)
{
Tim_M;
If(Khacphia(C,D,A,M) = = 1) printf (“Tia AB cat đoan CD”);
Else printf (“

Tia AB khong cat doan CD” );
}
Else printf (

“ Tia AB khong cat doan CD ”
‘
);
}
15
void main()
{<Nhập A,B,C,D>;
Ket_ qua();
Getch();}
1.4.3. Kiểm tra tính lồi, lõm của đa giác
Bài toán: Cho file DAGIAC.INP có cấu trúc như sau: dòng đầu ghi số

typedef struct
{
float x,y;
}xy;
xy a[200];
16
int n;
float s0,s1;
void docfile()
{ FILE *f;int i;
f = fopen("dagiac.inp","r+");
fscanf(f,"%d",&n);
for (i = 1;i< = n;i++)
fscanf(f,"%f%f",&a[i].x,&a[i].y);
a[n+1] = a[1];
s0 = 0;
for( i = 1;i< = n;i++)
s0 = s0+(a[i+1].x-a[i].x)*(a[i+1].y+a[i].y);
s0 = abs(s0)/2;
}
void inkq(int i)
{FILE *f1;
f1 = fopen("dagiac.out","w+");
fprintf(f1,"%d",i);
fclose(f1);
}
void xuly()
{xy b[100];
int t = 0;
int i,j,k;

A
3
A
5
A
6
A
7
A
4
M
18
Để giải bài toán này ta có hai cách sau:
C1: Trước hết ta tìm M’(x, y) sao cho x > max {x
i
|x
i
là hoành độ một
đỉnh i của đa giác; i = 1, 2 }. Còn y có giá trị sao cho đoạn MM’ không
chứa đỉnh nào của đa giác, y có thể tìm bằng phương pháp duyệt trung điểm
của các cạnh hay lựa chọn ngẫu nhiên. Tiếp đó ta đếm số giao điểm của đoạn
MM’ so với tất cả các cạnh của đa giác:
+ Nếu số giao điểm là lẻ thì M nằm trong đa giác.
+ Nếu số giao điểm là chẵn thì M nằm ngoài đa giác.
Chú ý: Nếu M thuộc một cạnh hay một đỉnh nào đó của đa giác thì ta
cần xử lý riêng.
C2: Cho trước điểm M(x, y) và một đa giác P, M không nằm trên cạnh
của P. Xét nửa đường thẳng có gốc tại M, song song với trục tung Oy và
hướng theo chiều dương. Tính tổng số giao điểm của nửa đường thẳng này
với tất cả các cạnh của đa giác. Nếu số giao điểm này là lẻ thì M nằm trong đa

+c[i+1].y * (c[k+1].x-c[i+1].x) s = s+1;
}
t = (s%2);
}
return t;
}
1.4.5. Bài toán tìm phần giao, phần hợp của hai đường tròn
Bài toán: Trong mặt phẳng tọa độ cho trước tọa độ tâm và độ dài bán
kính của hai đường tròn. Hãy tìm diện tích phần giao và diện tích phần hợp
của chúng.
20
Dữ liệu: Vào cho trong file CIRCLE.INP gồm hai dòng, mỗi dòng chứa 3 số
theo thứ tự là hoành độ, tung độ và bán kính của đường tròn.
Dữ liệu: Ra ghi vào file CIRCLE.OUT gồm hai dòng, dòng đầu tiên ghi một
số thực là diện tích phần giao, dòng tiếp theo ghi diện tích phần hợp (các số
thực được lấy chính xác đến hai chữ số thập phân).
Ví dụ:
CIRCLE.INP
0 0 1
0 0 3
CIRCLE.OUT
3.12
28.30
Thuật toán tìm diện tích phần giao (hay còn gọi là phương pháp chia
lưới): Chia mặt phẳng ra thành một lưới các ô vuông bởi các đường thẳng
song song với các trục tọa độ. Kiểm tra từng ô vuông, nếu nó nằm trong cả
hai đường tròn (thuộc phần giao của hai đường tròn) thì ta cộng thêm vào giá
trị diện tích cần tìm một lượng bằng diện tích của ô vuông đó.
Một số lưu ý với phương pháp này:
- Phương pháp này có thể mở rộng để tìm diện tích phần giao và phần

return t;
}
void docfile()
{FILE *f;
f = fopen("circle.inp","r+");
fscanf(f,"%f%f%f",&x1,&y1,&r1);
22
fscanf(f,"%f%f%f",&x2,&y2,&r2);
fclose(f);
s = 0;
}
void ketqua()
{
f = fopen("circle.out","w+");
fprintf(f,"%4.2f\n",s);
fprintf(f,"%4.2f",M_PI*(r1*r1+r2*r2)-s);
fclose(f);
}
void xuly()
{
docfile();
if(khoangcach(x1,y1,x2,y2)<r1+r2) i = x1-r1;
k = x1+r1;
h = y1+r1;
while (i<k)
{
j = y1-r1;
while(j<h)
{
if(khoangcach(i,j,x1,y1)<r1)

≤
N
≤
100).
 N dòng tiếp theo mỗi dòng chứa tọa độ của một đỉnh của đa giác được
liệt kê theo thứ tự đi vòng quanh đa giác theo chiều ngược kim đồng hồ.
24
Các tọa độ là các số thực có trị tuyệt đối không quá 10000. Độ dài mỗi
cạnh của đa giác đều không bé hơn 1.
Kết quả: Ghi ra file DAGIAC.OUT:
 Dòng đầu tiên ghi P là số cạnh của đa giác có thể nhìn thấy được dưới
một góc vuông từ một điểm nào đó trên đa giác.
 Dòng thứ hai ghi tọa độ của điểm nằm trên đa giác mà từ đó có thể nhìn
thấy dưới một góc vuông P cạnh của đa giác. (sai số không quá 10
-3
sẽ
được bỏ qua).
Ví dụ:
DAGIAC.INP DAGIAC.OUT
4
0 0
1 0
1 1
0 1
4
0.0000 0.0000
Để giải quyết bài toán này thì kiến thức phổ thông không thể không
biết đó là:
AB
⊥

c
), D(x
d
, y
d
).
Phân tích bài toán: điều kiện của bài toán đặt ra không có gì phức tạp,
nhưng cái khó của bài toán này là ổ chỗ: làm thế nào để lấy được từng điểm
nằm trên đa giác ra để kiểm tra?. Phương án tốt nhất là ta dùng phương pháp
lưới như đã trình bày ở mục 1.4.5.
Thuật toán như sau:
• Tìm một hình chữ nhật chứa đa giác đã cho, hình chữ nhật đó có điểm
dưới trái A có tọa độ là (min(X), min(Y)), điểm trên phải C có tọa độ là
(max(X), max(Y)), trong đó X = {x
i
| là hoành độ thứ i của đỉnh thứ i của
25

Trích đoạn Thuật toán

---