Báo cáo Ứng dụng diện tích đại số tam giác giải một số bài toán hình học trong Tin học - Ngô Quang Hợp

ỨNG DỤNG DIỆN TÍCH ĐẠI SỐ TAM GIÁC GIẢI MỘT SỐ BÀI TOÁN HÌNH HỌC TRONG TIN HỌC 
GV: NGÔ QUANG HỢP 
CÁCH TIẾP CẬN GIẢI BÀI TOÁN THEO PH Ư ƠNG PHÁP TRUYỀN THỐNG 
Tiếp cận theo các kiến thức hình học tính toán thuần túy theo góc nhìn Toán học với rất nhiều công thức phức tạp 
Điểm trong mặt phẳng , vector, góc, phương trình đường thẳng 
Phép quay, tịnh tiến, tích chấm, tích chéo 
Công thức liên quan đến các hàm sin, cos, tan 
Khó khăn cho ng ư ời học và giáo viên 
Điểm (point) 
y P 
x P 
P 
struct point{ 
 int x, y; 
}; 
ĐỐI TƯỢNG HÌNH HỌC CƠ SỞ 
O 
y 
x 
Đa giác (Polygon) 
point P[MaxN]; 
ĐỐI TƯỢNG HÌNH HỌC CƠ SỞ 
O 
y 
x 
P 1 
P 2 
P 3 
P n 
P 4 
P 5 
P 6 
ĐOẠN THẲNG (segment) 
Công thức tính khoảng cách đọan thẳng 
point P, Q; 
 Bình ph ư ơng khoảng cách 
long long CDistance( point p1, point p2){ 
 long long tmp1 = (p1.x-p2.x)*(p1.x-p2.x); 
 long long tmp2 = (p1.y-p2.y)*(p1.y-p2.y); 
 long long tmp = tmp1 + tmp2; 
 return tmp; 
} 
ĐỐI TƯỢNG H...chiều kim đồng hồ (CCW) 
CCW 
CW 
DẠNG 3: XÁC ĐỊNH CHIỀU LIỆT KÊ CÁC ĐỈNH TRONG TAM GIÁC 
DẠNG TOÁN ÁP DỤNG 
Xét đa giác có các đỉnh đ ư ợc liệt kê theo thứ tự P 1 P 2 P 3 P 4 P 5 P 6 , ta xác định chiều được liệt kê của các đỉnh bằng cách nào? 
P 6 
P 5 
P1 
P2 
P 4 
P3 
Lần lượt xét dấu diện tích đại số của các tam giác (P 1 P 2 P 3 ), (P 2 P 3 P 4 ), (P 3 P 4 P 5 ), ( P 4 P 5 P 6 ), ( P 5 P 6 P 1 ), ( P 6 P 1 P 2 ). 
Nếu toàn bộ các dấu đều là dấu d ư ơng thì các đỉnh đ ư ợc liệt kê ng ư ợc chiều kim đồng hồ . 
DẠNG 4: XÁC ĐỊNH CHIỀU LIỆT KÊ CÁC ĐỈNH TRONG ĐA GIÁC 
DẠNG TOÁN ÁP DỤNG 
Ng ư ợc lại thì đ ư ợc liệt kê theo chiều kim đồng hồ. 
Làm thế nào để xác định đa giác đã cho là đa giác lồi ? 
Xét đa giác có các đỉnh đ ư ợc liệt kê theo thứ tự P 1 P 2 P 3 P 4 P 5  P n 
Lần lượt xét dấu diện tích đại số của các tam giác (P 1 P 2 P 3 ), (P 2 P 3 P 4 ), (P 3 P 4 P 5 ),, ( P n-1 P n P 1 ). 
Nếu tất cả diện tích đại số của các tam giác trên là cùng dấu thì đa giác đã cho là đa giác lồi . 
P1 
P2 
P3 
P4 
P5 
Pn 
DẠNG 4: KIỂM TRA TÍNH LỒI CỦA ĐA GIÁC 
DẠNG TOÁN ÁP DỤNG 
Nếu tồn tại một giá trị ng ư ợc dấu thì đa giác đã cho không lồi 
bool DaGiacLoi( point p[], int n ) 
{ 
 int t = STamgiac(p[0],p[1],p[2]); 
 for(int i=1; i<n ; i++) 
 { 
 int tmp = STamgiac(p[i], p[i+1], p[(i+2)%n]); 
 if (!((t<0)==(tmp<0))) 
 return false ; 
 } 
 return true ; 
} 
Cho đ ư ờng thẳng d1 đi qua hai điểm P 1 , P 2 , đ ư ờng thẳng d2 đi qua 2 điểm P 3, P 4 . 
Xác định hai đ ư ờng thẳng d1 và d2 có cắt nhau hay không? 
P3 
P2 
P1 
P4 
d1 
d2 
Tính diện tích đại số của các tam giác: (P 1 P 3 P 2 ) và (P 1 P 4 P 2 ): . 
*Hai đ ư ờng thẳng d1 và d2 cắt nhau diện tích đại số của hai tam giác hoặc trái dấu hoặc có duy nhất một giá trị bằng 0 . 
*Hai đ ư ờng thẳng d1 và d2 không cắt nhau diện tích đại số của hai tam giác cùng dấu . 
*Hai đ ư ờng thẳng trùng nhau khi cả hai diện tích đại số có giá trị là 0 
DẠNG 5: XÁC ĐỊNH HAI ĐƯỜNG T.... 
Y 
X 
O 
BÀI TẬP MINH HOẠ 2: CÁC HÌNH VUÔNG 
BÀI TẬP VẬN DỤNG 
Y 
X 
O 
BÀI TẬP MINH HOẠ 2: CÁC HÌNH VUÔNG 
BÀI TẬP VẬN DỤNG 
Y 
X 
O 
BÀI TẬP MINH HOẠ 2: CÁC HÌNH VUÔNG 
BÀI TẬP VẬN DỤNG 
Y 
X 
O 
BÀI TẬP MINH HOẠ 2: CÁC HÌNH VUÔNG 
BÀI TẬP VẬN DỤNG 
Làm thế nào để có thể nhanh chóng sắp xếp các đỉnh theo thứ tự tăng dần về góc? 
O 
P 5 
P1 
P2 
P 4 
P3 
BÀI TẬP MINH HOẠ 2: CÁC HÌNH VUÔNG 
BÀI TẬP VẬN DỤNG 
O 
P2 
P1 
Xét dấu diện tích đại số của tam giác P 1 OP 2 : 
Nếu dấu âm P 1 OP 2 đ ư ợc ghi ng ư ợc chiều kim đồng hồ P 1 có góc lớn h ơ n P 2 
Nếu dấu d ư ơng P 1 OP 2 đ ư ợc ghi theo chiều kim đồng hồ P 1 có góc nhỏ hơn P 2 
bool SoSanh( point p1, point p2) 
{ 
 point O; O.x=0; O.y=0; 
 if (STamgiac(p1,O,p2)>0) 
 return true ; 
 return false ; 
} 
BÀI TẬP MINH HOẠ 2: CÁC HÌNH VUÔNG 
BÀI TẬP VẬN DỤNG 
Bài toán: 
Trên mặt phẳng với hệ tọa độ trực chuẩn cho điểm có tọa độ nguyên P 1 P 2  P n . 
Yêu cầu: Hãy xác định đa giác có diện tích nhỏ nhất chứa n điểm nói trên (có thể nằm trên biên của đa giác). 
BÀI TẬP MINH HOẠ 3: XÁC ĐỊNH BAO LỒI 
BÀI TẬP VẬN DỤNG 
Một đa giác chứa tất cả các điểm. Tuy nhiên rõ ràng đây ch ư a phải là đa giác có diện tích nhỏ nhất 
BÀI TẬP MINH HOẠ 3: XÁC ĐỊNH BAO LỒI 
BÀI TẬP VẬN DỤNG 
Bài toán: 
Trên mặt phẳng với hệ tọa độ trực chuẩn cho điểm có tọa độ nguyên P 1 P 2  P n . 
Yêu cầu: Hãy xác định đa giác có diện tích nhỏ nhất chứa n điểm nói trên (có thể nằm trên biên của đa giác). 
Đa giác nhỏ nhất thỏa yêu cầu đề bài. 
Co đa giác nhỏ dần để tìm đa giác thỏa yêu cầu 
BÀI TẬP MINH HOẠ 3: XÁC ĐỊNH BAO LỒI 
BÀI TẬP VẬN DỤNG 
P0 
Pn-1 
Thuật toán: 
B1 – Sắp xếp các điểm theo thứ tự tăng dần về hoành độ, nếu có nhiều điểm có cùng hoành độ thì sắp theo tung độ tăng dần 
BÀI TẬP MINH HOẠ 3: XÁC ĐỊNH BAO LỒI 
BÀI TẬP VẬN DỤNG 
B2- Chọn 2 điểm P0 và Pn-1 làm hai điểm bắt đầu . 
B3- Xây dựng đ ư ờng bao lồi trên và d ư ới dựa trên nhận xét nh ư sau: 
	Các điểm nằm trên đ