intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng cơ sở lập trình nâng cao - Chương 9

Chia sẻ: Impossible_1 Impossible_1 | Ngày: | Loại File: PPTX | Số trang:39

Thêm vào BST
Báo xấu
58
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng cơ sở lập trình nâng cao - Chương 9

  1. Chương 9 PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − HÌNH HỌC − 1
  2. 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
  3. Hình ảnh 3
  4. 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
  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). 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
  6. 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
  7. 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)
  8. 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
  9. 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
  10. 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
  11. 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
  12. Cấu trúc dữ liệu cơ bản cài đặt double KhoangCachDiemVaDuongThang(Point p, Line line) { } 12
  13. Cấu trúc dữ liệu cơ bản cài đặt bool CungPhia(Point A, Point B, Line line) { } 13
  14. Đ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
  15. Điểm và đoạn thẳng, đường thẳng và tia cài đặt bool DiemThuocDuongThang(Point p, Point A, Point B) { } 15
  16. Đ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
  17. Điểm và đoạn thẳng, đường thẳng và tia cài đặt bool DiemThuocDoanThang(Point p, Point A, Point B) { } 17
  18. Đ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
  19. Đ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
  20. Điểm và đoạn thẳng, đường thẳng và tia cài đặt bool DiemThuocTia(Point p, Point A, Point B) { } 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
8=>2