Bài giảng Cơ sở lập trình nâng cao - Chương 9: Phương pháp thiết kế thuật toán Hình học - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAO 
Biên soạn: Ths.Tôn Quang Toại 
TonQuangToai@yahoo.com 
TPHCM, NĂM 2013 
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − HÌNH HỌC − 
Chương 9 
Nội dung 
Cấu trúc dữ liệu cơ bản 
Điểm và đoạn thẳng, đường thẳng và tia 
Giao điểm 2 đoạn thẳng, đường thẳng 
Đa giác 
Điểm và đa giác 
Đa giác lồi 
Bao lồi 
Hình ảnh 
Cấu trúc dữ liệu cơ bản 
Một số cấu trúc dữ liệu hình học cơ bản 
Điểm: P(x p , y p ) 
Đoạn thẳng: XY 
Đường thẳng: Qua 2 điểm P 1 , P 2 
Tia: Tia AB 
P 
x 
y p 
y 
x p 
x 1 
x 2 
y 1 
y 2 
0 
P 1 
P 2 
B 
A 
X 
Y 
Cấu trúc dữ liệu cơ bản 
Phương trình của đường thẳng 
Đường thẳng được xác định bởi 2 điểm P 1 (x 1 , y 1 ), P 2 (x 2 , y 2 ). 
Cấu trúc dữ liệu cơ bản 
Phương trình của đường thẳng 
Dạng tổng quát 
hay 
Cấu trúc dữ liệu cơ bản 
Đường thẳng chia mặt phẳng làm 3 phần 
Phần 1: Gồm các điểm trên đường thẳng F(x,y)=0 
Phần 2: Gồm các điểm làm cho F(x,y)>0 
Phần 3: Gồm các điểm làm cho F(x,y)<0 
x 
y 
0 
+ 
+ 
+ 
+ 
+ 
+ 
+ 
+ 
+ 
+ 
Cấu trúc dữ liệu cơ bản 
Khoảng cách từ điểm P(x 0 , y 0 ) đến đường thẳng (d) có phương trình F(x,y)=Ax+By+C=0 
h 
(d) 
P(x 0 , y 0 ) 
Cấu trúc dữ liệu cơ bản 
Đa giác: được xác định bởi tập đỉnh được liệt kê thứ tự theo chiều kim đồng (hay ngược chiều kim đồng hồ) 
Đa giác lồi 
Đa giác lõm 
0 
1 
2 
3 
0 
1 
2 
3 
4 
5 
Lồi 
Lõm 
Cấu trúc dữ liệu cơ bản 
typedef struct PointTag{	 double x, y;} Point; 
typedef struct LineTag{	 double A, B, C;} Line; 
#define MAXPOINT 100 typedef struct PolygonTag{	Point aPoints[MAXPOINT]; 	int n;} Polygon; 
CTDL 
Cấu trúc dữ liệu cơ bản 
void TaoDuongThang(Point p1, Point p2, Line &line){	line.A = 	line.B = 	line.C = } 
double F(Point p, Line line){} 
cài đặt 
Cấu trúc dữ liệu cơ bản 
double KhoangCachDiemVaDuongThang(Point p, Line line){} 
cài đặt 
Cấu trúc dữ liệu cơ bản 
bool CungPhia(Point A, Point B, Line line){} 
cài đặt 
Điểm và đoạn thẳng, đường thẳng và tia 
Bài toán 1 [Điểm có thuộc đường thẳng]: Tìm vị trí tương đối giữa điểm P(x 0 , y 0 ) và đường thẳng đi qua 2 điểm A(x 1 , y 1 ) và B(x 2 , y 2 ) 
Thuật toán 
Bước 1: Viết phương trình dưới dạng tổng quát 
F(x, y) = Ax+By+C=0 
Bước 2: P thuộc đường thẳng AB nếu 
F(x 0 , y 0 ) = 0 
Điểm và đoạn thẳng, đường thẳng và tia 
cài đặt 
bool DiemThuocDuongThang(Point p, Point A, Point B){} 
Điểm và đoạn thẳng, đường thẳng và tia 
Bài toán 2 [Điểm có thuộc đoạn thẳng] : Kiểm tra điểm P(x 0 , y 0 ) có thuộc đoạn thẳng nối 2 điểm A(x 1 , y 1 ) và B(x 2 , y 2 ) 
Thuật toán 
Bước 1: Viết phương trình dưới dạng tổng quát 
F(x, y) = Ax+By+C=0 
Bước 2: P thuộc đoạn AB nếu thỏa mãn các điều kiện 
F(x 0 , y 0 ) = 0 
Min(x 1 , x 2 ) ≤ x 0 ≤Max(x 1 , x 2 ) 
Min(y 1 , y 2 ) ≤ y 0 ≤Max(y 1 , y 2 ) 
Điểm và đoạn thẳng, đường thẳng và tia 
cài đặt 
bool DiemThuocDoanThang(Point p, Point A, Point B){} 
Điểm và đoạn thẳng, đường thẳng và tia 
Bài toán 3 [Điểm có thuộc tia] : Kiểm tra điểm P(x 0 , y 0 ) có thuộc tia AB không (trong đó A(x 1 , y 1 ), B(x 2 , y 2 )) 
P thuộc tia AB nếu 
Với k≥0 
A 
B 
P 
P 
Điểm và đoạn thẳng, đường thẳng và tia 
Thuật toán 
Bước 1: Viết phương trình dưới dạng tổng quát 
F(x, y) = Ax+By+C=0 
Bước 2: P thuộc tia AB nếu thỏa mãn các điều kiện 
F(x 0 , y 0 ) = 0 
(x 0 -x 1 )(x 2 -x 1 ) ≥0 
(y 0 -y 1 )(y 2 -y 1 ) ≥0 
Điểm và đoạn thẳng, đường thẳng và tia 
cài đặt 
bool DiemThuocTia(Point p, Point A, Point B){} 
Giao điểm 2 đoạn thẳng, đường thẳng 
Bài toán 4 [Giao điểm 2 đường thẳng]: Tìm giao điểm của 2 đường thẳng có phương trình tổng quát 
Thuật toán: Giải hệ phương trình 
hay 
Giao điểm 2 đoạn thẳng, đường thẳng 
Bước 1: Tính 
Bước 2: Biện luận 
Nếu d=dx=dy=0 thì 2 đường thẳng trùng nhau 
Nếu d=0 và (dx ≠0 hay dy≠0 ) thì 2 đường thẳng song song 
Nếu d ≠ 0 thì giao điểm có tọa độ 
Giao điểm 2 đoạn thẳng, đường thẳng 
cài đặt 
int TimGiaoDiem2DuongThang(Line line1, Line line2, 	 Point &p){} 
Đa giác 
Bài toán 5 [Diện tích đa giác]: Cho đa giác T. Hãy tính diện tích của đa giác T 
Thuật toán: Gọi S là diện tích đa giác 
Chú ý: Đỉnh P n cũng là đỉnh P 0 
Đa giác 
0 
1 
2 
3 
4 
+ 
+ 
0 
1 
2 
3 
+ 
+ 
Ý nghĩa: 
Đối với đa giác lồi: S bằng HIỆU s các hình thang nằm trên với s các hình thang nằm dưới 
Đối với đa giác lõm: S bằng tổng đại số các diện tích của hình thang 
Đa giác 
cài đặt 
double TinhDienTichDaGiac(Polygon T){} 
Đa giác 
Bài toán 6 [Kiểm tra 1 điểm nằm trong hay ngoài đa giác]: Cho đa giác T và điểm P. Hãy kiểm tra xem P thuộc miền trong hay miền ngoài của đa giác T 
p 
p 
p 
p 
p 
p 
p 
Đa giác 
Thuật toán: 
Nếu P thuộc bất kỳ cạnh nào của đa giác T thì được xem là thuộc miền trong của đa giác 
Ngược lại kẻ đoạn thẳng PA song song trục hoành và có hoành độ lớn hơn các hoành độ các điểm (dĩ nhiên lớn hơn hoành độ điểm P) 
Tính số giao điểm (num) của đoạn thẳng PA với các cạnh đa giác (cũng là các đoạn thẳng) 
Nếu num lẻ thì P trong đa giácNgược lại P nằm ngoài đa giác 
Đa giác 
3 trường hợp sau được xem như tăng thêm 1 giao điểm 
Đoạn PA cắt cạnh P i P i+1 và 2 điểm P i và P i+1 không thuộc đoạn thẳng 
P 
A 
P i 
P i+1 
Đa giác 
Điểm P i không thuộc đoạn PA, P i+1 thuộc đoạn PA và 2 điểm P i và P i+2 nằm 2 phía khác nhau so với đoạn PA 
P 
A 
P i 
P i+2 
P i+1 
P i và P i+1 thuộc đoạn PA, P i-1 và P i+2 không thuộc đoạn PA và khác phía so với PA 
P 
A 
P i 
P i+1 
P i+2 
P i-1 
Đa giác 
cài đặt 
int DiemTrongDaGiac(Polygon T, Point P){} 
Đa giác 
Bài toán 7 [Kiểm tra đa giác lồi]: Cho đa giác T. Hãy kiểm tra xem đa giác T là đa giác lồi hay đa giác lõm 
Lồi 
Lõm 
Đa giác 
Thuật toánĐa giác T lồi khi 
 Với mỗi cạnh P i P i+1 (0 ≤ i<n) 
Đỉnh P i+2 và đỉnh P j (0 ≤j<n ) phải cùng phía so với đường thẳng qua cạnh P i P i+1 
Chú ý: 
Đỉnh P n được xem như là đỉnh P 0 , 
Đỉnh P n+1 được xem như đỉnh P 1 
Đa giác 
cài đặt 
int LaDaGiacLoi(Polygon T){} 
Đa giác 
Bài toán 8 [Bao lồi]: Cho tập điểm P 0 , P 1 , , P n-1 (n ≤ 100). Hãy tìm đa giác lồi có các đỉnh là một số điểm trong số n điểm đã cho và chứa các điểm còn lại, đồng thời có chu vi nhỏ nhất. 
Đa giác 
Thuật toán 
Bước 1: Sắp xếp các điểm có tung độ tăng dần 
Bước 2: Chọn đỉnh thứ nhất là đỉnh có tung độ lớn nhất 
Bước 3 [Lặp]: Giả sử đã chọn được các đỉnh T 0 , T 1 , , T i . Chọn điểm T i+1 thỏa điều kiện 
T i+1 chưa được chọn 
Tập điểm đã chọn nằm về một phía so với đường thẳng qua đoạn T i T i+1 
p 1 
p 2 
p 3 
p 4 
p 5 
p 6 
p 7 
p 8 
p 9 
p 11 
p 0 
Đa giác 
cài đặt 
void TimBaoLoi(Point p[], int n, Polygon &T){} 
Chú ý về lập trình với số thực 
Tránh phép chia: Thay thế phép chia thành phép nhân 
So sánh số thực: Khi so sánh biểu thức E ( E chứa số thực ) với số 0, chúng ta thường chọn số dương  nhỏ cỡ một phần ngàn . Nếu trị tuyệt đối của E nhỏ hơn  thì được coi như E bằng 0 
#define EPS 0.001 if (abs(E) < EPS){	} 
HẾT CHƯƠNG 9