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 CAOBiên soạn: Ths.Tôn Quang ToạiTonQuangToai@yahoo.comTPHCM, NĂM 2013TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCMKHOA CÔNG NGHỆ THÔNG TINPHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − HÌNH HỌC −Chương 9Nội dungCấu trúc dữ liệu cơ bảnĐiểm và đoạn thẳng, đường thẳng và tiaGiao điểm 2 đoạn thẳng, đường thẳngĐa giácĐiểm và đa giácĐa giác lồiBao lồiHình ảnhCấu trúc dữ liệu cơ bảnMộ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, P2Tia: Tia ABPxypyxpx1x2y1y20P1P2BAXYCấu trúc dữ liệu cơ bảnPhươ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).Cấu trúc dữ liệu cơ bảnPhương trình của đường thẳngDạng tổng quáthayCấu trúc dữ liệu cơ bảnĐường thẳng chia mặt phẳng làm 3 phầnPhần 1: Gồm các điểm trên đường thẳng F(x,y)=0Phần 2: Gồm các điểm làm cho F(x,y)>0Phần 3: Gồm các điểm làm cho F(x,y)<0xy0++++++++++Cấu trúc dữ liệu cơ bảnKhoả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=0h(d)P(x0, y0)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õm0123012345LồiLõmCấu trúc dữ liệu cơ bảntypedef struct PointTag{ double x, y;} Point;typedef struct LineTag{ double A, B, C;} Line;#define MAXPOINT 100typedef struct PolygonTag{ Point aPoints[MAXPOINT]; int n;} Polygon;CTDLCấu trúc dữ liệu cơ bảnvoid TaoDuongThang(Point p1, Point p2, Line &line){ line.A =  line.B =  line.C = }double F(Point p, Line line){}cài đặtCấu trúc dữ liệu cơ bảndouble KhoangCachDiemVaDuongThang(Point p, Line line){}cài đặtCấu trúc dữ liệu cơ bảnbool CungPhia(Point A, Point B, Line line){}cài đặtĐiểm và đoạn thẳng, đường thẳng và tiaBà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ánBước 1: Viết phương trình dưới dạng tổng quátF(x, y) = Ax+By+C=0Bước 2: P thuộc đường thẳng AB nếu F(x0, y0) = 0Điểm và đoạn thẳng, đường thẳng và tiacài đặtbool DiemThuocDuongThang(Point p, Point A, Point B){}Điểm và đoạn thẳng, đường thẳng và tiaBà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ánBước 1: Viết phương trình dưới dạng tổng quát F(x, y) = Ax+By+C=0Bước 2: P thuộc đoạn AB nếu thỏa mãn các điều kiện F(x0, y0) = 0Min(x1, x2)≤x0≤Max(x1, x2)Min(y1, y2)≤y0≤Max(y1, y2)Điểm và đoạn thẳng, đường thẳng và tiacài đặtbool DiemThuocDoanThang(Point p, Point A, Point B){}Điểm và đoạn thẳng, đường thẳng và tiaBà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 Với k≥0ABPPĐiểm và đoạn thẳng, đường thẳng và tiaThuật toán Bước 1: Viết phương trình dưới dạng tổng quátF(x, y) = Ax+By+C=0Bướ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Điểm và đoạn thẳng, đường thẳng và tiacài đặtbool DiemThuocTia(Point p, Point A, Point B){}Giao điểm 2 đoạn thẳng, đường thẳngBà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átThuật toán: Giải hệ phương trình hayGiao điểm 2 đoạn thẳng, đường thẳngBước 1: TínhBước 2: Biện luậnNếu d=dx=dy=0 thì 2 đường thẳng trùng nhauNếu d=0 và (dx≠0 hay dy≠0) thì 2 đường thẳng song songNếu d≠0 thì giao điểm có tọa độGiao điểm 2 đoạn thẳng, đường thẳngcài đặtint TimGiaoDiem2DuongThang(Line line1, Line line2,  Point &p){}Đa giácBà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 TThuật toán: Gọi S là diện tích đa giác Chú ý: Đỉnh Pn cũng là đỉnh P0Đa giác01234++0123++Ý 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áccài đặtdouble TinhDienTichDaGiac(Polygon T){}Đa giácBà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 TpppppppĐa giácThuậ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ácNgượ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ác3 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ẳngPAPiPi+1Đ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 PAPAPiPi+2Pi+1Pi 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 PAPAPiPi+1Pi+2Pi-1Đa giáccài đặtint DiemTrongDaGiac(Polygon T, Point P){}Đa giácBà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õmLồiLõmĐa giácThuậ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Đa giáccài đặtint LaDaGiacLoi(Polygon T){}Đa giácBà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.Đa giácThuật toán Bước 1: Sắp xếp các điểm có tung độ tăng dầnBước 2: Chọn đỉnh thứ nhất là đỉnh có tung độ lớn nhấtBướ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ệnTi+1 chưa được chọnTập điểm đã chọn nằm về một phía so với đường thẳng qua đoạn TiTi+1 p1p2p3p4p5p6p7p8p9p11p0Đa giáccài đặtvoid TimBaoLoi(Point p[], int n, Polygon &T){}Chú ý về lập trình với số thựcTránh phép chia: Thay thế phép chia thành phép nhânSo 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.001if (abs(E) < EPS){ }HẾT CHƯƠNG 9