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

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

1. 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
2. Chương 9 PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − HÌNH HỌC−
3. 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
4. Hình ảnh
5. 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(xp, yp) – Đoạn thẳng: XY – Đường thẳng: Qua 2 điểm P1, P2 – Tia: Tia AB y P2 y2 P1 B Y y1 y P p A X 0 xp x1 x2 x
6. 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 P1(x1, y1), P2(x2, y2). x−− x y y 11= x2−− x 1 y 2 y 1 (y2 − y)( 1x − x 1 )( − x 2 − x 1 )( y − y)0 1 = (y2 − y 1 )x + ( x 1 − x 2 ) y + x 2 y 1 − x 1 y 2 = 0 (y1 − y 2 )x + ( x 2 − x 1 ) y + x 1 y 2 − x 2 y 1 = 0
7. 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 F( x , y )= Ax + By + C = 0 A =−(y12 y ) A =−(y21 y ) Bx=−(x21 ) hay Bx=−(x12 ) C=−() x1 y 2 x 2 y 1 C=−() x2 y 1 x 1 y 2
8. 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 y + + + + + + + + − + − − + − − − − − 0 x
9. Cấu trúc dữ liệu cơ bản • Khoảng cách từ điểm P(x0, y0) đến đường thẳng (d) có phương trình F(x,y)=Ax+By+C=0 Ax++ By C F(,) x y h ==0 0 0 0 A2++BAB 2 2 2 P(x0, y0) h (d)
10. 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 1 3 1 2 2 0 0 4 3 5
11. 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;
12. 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) { }
13. Cấu trúc dữ liệu cơ bản double KhoangCachDiemVaDuongThang(Point p, Line line) { }
14. Cấu trúc dữ liệu cơ bản bool CungPhia(Point A, Point B, Line line) { }
15. Đ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(x0, y0) và đường thẳng đi qua 2 điểm A(x1, y1) và B(x2, y2) • 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(x0, y0) = 0
16. Điểm và đoạn thẳng, đường thẳng và tia bool DiemThuocDuongThang(Point p, Point A, Point B) { }
17. Đ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(x0, y0) có thuộc đoạn thẳng nối 2 điểm A(x1, y1) và B(x2, y2) • 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(x0, y0) = 0 • Min(x1, x2)≤x0≤Max(x1, x2) • Min(y1, y2)≤y0≤Max(y1, y2)
18. Điểm và đoạn thẳng, đường thẳng và tia bool DiemThuocDoanThang(Point p, Point A, Point B) { }
19. Đ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(x0, y0) có thuộc tia AB không (trong đó A(x1, y1), B(x2, y2)) • P thuộc tia AB nếu AP= k AB Với k≥0 P B P A
20. Đ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(x0, y0) = 0 • (x0-x1)(x2-x1)≥0 • (y0-y1)(y2-y1)≥0
21. Điểm và đoạn thẳng, đường thẳng và tia bool DiemThuocTia(Point p, Point A, Point B) { }
22. 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 A1 x+ B 1 y + C 1 = 0 A2 x+ B 2 y + C 2 = 0 ▪ Thuật toán: Giải hệ phương trình A1 x+ B 1 y + C 1 = 0 A1 x+ B 1 y = − C 1 hay A2 x+ B 2 y + C 2 = 0 A2 x+ B 2 y = − C 2
23. Giao điểm 2 đoạn thẳng, đường A1 xthẳng+ B 1 y = − C 1 A2 x+ B 2 y = − C 2 – Bước 1: Tính d=−AA1 B 2 2 B 1 dx=− C2 B 1 C 1 B 2 dy=− A2 C 1 AC 1 2 • 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 dx x = – Nếu d≠0 thì giao điểm có tọa độ d dy y = d
24. Giao điểm 2 đoạn thẳng, đường thẳng int TimGiaoDiem2DuongThang(Line line1, Line line2, Point &p) { }
25. Đ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 n−1 (x−+ x )( y y ) S =  i++11 i i i i=0 2 1 n−1 =(xi++11 − x i )( y i + y i ) 2 i=0 • Chú ý: Đỉnh Pn cũng là đỉnh P0
26. Đa giác 1 + + • Ý nghĩa: 0 2 – Đối với đa giác lồi: S bằng − − HIỆU s các hình thang 3 nằm trên với s các hình thang nằm dưới 1 + • Đối với đa giác lõm: S bằng − 0 2 + tổng đại số các diện tích 3 của hình thang − − 4
27. Đa giác double TinhDienTichDaGiac(Polygon T) { }
28. Đ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
29. Đ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ác Ngược lại P nằm ngoài đa giác
30. Đ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 PiPi+1 và 2 điểm Pi và Pi+1 không thuộc đoạn thẳng Pi P A Pi+1
31. Đa giác – Điểm Pi không thuộc đoạn PA, Pi+1 thuộc đoạn PA và 2 điểm Pi và Pi+2 nằm 2 phía khác nhau so với đoạn PA Pi Pi+1 P A Pi+2 • Pi và Pi+1 thuộc đoạn PA, Pi-1 và Pi+2 không thuộc đoạn PA và khác phía so với PA Pi-1 Pi Pi+1 A P Pi+2
32. Đa giác int DiemTrongDaGiac(Polygon T, Point P) { }
33. Đ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
34. Đa giác • Thuật toán Đa giác T lồi khi – Với mỗi cạnh PiPi+1 (0≤i<n) • Đỉnh Pi+2 và đỉnh Pj (0≤j<n) phải cùng phía so với đường thẳng qua cạnh PiPi+1 – Chú ý: • Đỉnh Pn được xem như là đỉnh P0, • Đỉnh Pn+1 được xem như đỉnh P1
35. Đa giác int LaDaGiacLoi(Polygon T) { }
36. Đa giác • Bài toán 8 [Bao lồi]: Cho tập điểm P0, P1, , Pn-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.
37. Đ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 T0, T1, , Ti. Chọn điểm Ti+1 thỏa điều kiện • Ti+1 chưa được chọn • Tập điểm đã chọn nằm về một phíap11 so với đường thẳng qua p đoạn TiTi+1 9 p 8 p7 p6 p5 p4 p3 p2 p1 p0
38. Đa giác void TimBaoLoi(Point p[], int n, Polygon &T) { }
39. 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 #define EPS 0.001 coi như E bằng 0 if (abs(E) < EPS) { }