Bài giảng cơ sở lập trình nâng cao - Chương 9
lượt xem 5
download
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). 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)
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng cơ sở lập trình nâng cao - Chương 9
- Chương 9 PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − HÌNH HỌC − 1
- 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 2
- Hình ảnh 3
- 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 P y2 2 P B Y y1 1 yp P A X 0 xp x1 x x 2 4
- 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 − x1 y − y1 = x2 − x1 y2 − y1 � (y 2 − y1 )( x − x1 ) − ( x2 − x1 )( y − y1 ) = 0 � (y 2 − y1 ) x + ( x1 − x2 ) y + x2 y1 − x1 y2 = 0 � (y1 − y 2 ) x + ( x2 − x1 ) y + x1y 2 − x2 y1 = 0 5
- 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 = (y1 − y 2 ) A = (y 2 − y1 ) B = (x 2 − x1 ) hay B = (x1 − x2 ) C = ( x1 y2 − x2 y1 ) C = ( x2 y1 − x1 y2 ) 6
- 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)
- 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 Ax0 + By0 + C F ( x0 , y0 ) h= = A2 + B2 A2 + B 2 P(x0, y0) h (d) 8
- 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 Lồi Lõm 4 3 5 9
- Cấu trúc dữ liệu cơ bản CTDL 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; 10
- Cấu trúc dữ liệu cơ bản cài đặt void TaoDuongThang(Point p1, Point p2, Line &line) { line.A = line.B = line.C = } double F(Point p, Line line) { } 11
- Cấu trúc dữ liệu cơ bản cài đặt double KhoangCachDiemVaDuongThang(Point p, Line line) { } 12
- Cấu trúc dữ liệu cơ bản cài đặt bool CungPhia(Point A, Point B, Line line) { } 13
- Đ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 14
- Điểm và đoạn thẳng, đường thẳng và tia cài đặt bool DiemThuocDuongThang(Point p, Point A, Point B) { } 15
- Đ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) 16
- Điểm và đoạn thẳng, đường thẳng và tia cài đặt bool DiemThuocDoanThang(Point p, Point A, Point B) { } 17
- Đ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 uuu r uuu r AP = k AB Với k≥0 P B P A 18
- Đ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 19
- Điểm và đoạn thẳng, đường thẳng và tia cài đặt bool DiemThuocTia(Point p, Point A, Point B) { } 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cơ sở lập trình - Chương 3: Các cấu trúc điều khiển
56 p | 137 | 22
-
Bài giảng Cơ sở lập trình 1: Giới thiệu môn học - Lê Quý Tài
9 p | 132 | 8
-
Bài giảng Cơ sở lập trình: Chương 1 - Lê Viết Mẫn
55 p | 73 | 5
-
Bài giảng Cơ sở lập trình Csharp: Bài 4 - Cấu trúc lặp
17 p | 79 | 4
-
Bài giảng Cơ sở lập trình: Chương 1 - Thuật toán và thuật giải
30 p | 14 | 4
-
Bài giảng Cơ sở lập trình: Chương 2 - Tổng quan về lập trình máy tính
14 p | 7 | 3
-
Bài giảng Cơ sở lập trình: Chương 4 - Các cấu trúc điều khiển
41 p | 14 | 3
-
Bài giảng Cơ sở lập trình - Trường ĐH Thương mại
108 p | 41 | 3
-
Bài giảng Cơ sở lập trình: Chương 1 - Khái niệm lập trình
428 p | 17 | 3
-
Bài giảng Cơ sở lập trình: Các phần tử cơ bản của ngôn ngữ C
55 p | 9 | 2
-
Bài giảng Cơ sở lập trình: Kiểu cấu trúc
26 p | 7 | 2
-
Bài giảng Cơ sở lập trình: Kiểu chuỗi ký tự
21 p | 4 | 2
-
Bài giảng Cơ sở lập trình: Kiểu con trỏ
50 p | 3 | 2
-
Bài giảng Cơ sở lập trình: Kiểu dữ liệu mảng
54 p | 5 | 2
-
Bài giảng Cơ sở lập trình: Các khái niệm cơ bản về lập trình
20 p | 7 | 2
-
Bài giảng Cơ sở lập trình: Các cấu trúc điều khiển trong ngôn ngữ C
38 p | 9 | 2
-
Bài giảng Cơ sở lập trình: Chương trình con
22 p | 3 | 2
-
Bài giảng Cơ sở lập trình: Kiểu tập tin
32 p | 3 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn