TAILIEUCHUNG - 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
Bài giảng cung cấp cho người học các kiến thức: Phương pháp thiết kế thuật toán − hình học, cấu trúc dữ liệu cơ bản, điểm và đa giác, đa giác lồi . Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. chi tiết nội dung bài giảng. | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − HÌNH HỌC − Chương 9 2 Algorithm Design 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 3 Hình ảnh 4 Điểm, Đường, Tia, Giao 2 đường thẳng Đa giác, điểm trong đa giác, Bao lồi 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 P x yp y xp x1 x2 y1 y2 0 P1 P2 B A X Y 5 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). 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 7 Quy tac nho: Ax: y1-y2 By: x2-x1 C: tich ve trai – tich ve phai (x1y2-x2y1) 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(x0, y0) đến đường thẳng (d) có phương trình F(x,y)=Ax+By+C=0 h (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õ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 11 Cấu trúc dữ liệu cơ bản void TaoDuongThang(Point p1, Point p2, Line &line) { = = = } double F(Point p, Line line) { } cài đặt void TaoDuongThang(Point p1, Point p2, Line &line) { = ( - ); = ( - ); = (* - *); } // F(x,
đang nạp các trang xem trước
