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: Phương pháp thiết kế thuật toán − hình học

Chia sẻ: Phuc Nguyen | Ngày: | Loại File: PPTX | Số trang:40

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

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. Mời các bạn cùng tham khảo chi tiết nội dung bài giảng.

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: Phương pháp thiết kế thuật toán − hình học

  1. TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM KHOA CÔNG NGHỆ THÔNG TIN CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Ths.Tôn Quang Toại TonQuangToai@yahoo.com
  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 – y Tia: Tia AB P y2 2 P B Y y1 1 yp P A X 0 xp x1 x x 2
  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 − 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
  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 = (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 )
  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 y – Phần 3: Gồm các điểm làm cho F(x,y)
  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 Ax0 + By0 + C F ( x0 , y0 ) h= = A2 + B2 A2 + B 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 3 – Đa giác 1lõm 1 2 2 0 0 Lồi Lõm 4 3 5
  11. 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;
  12. 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) { }
  13. Cấu trúc dữ liệu cơ bản cài đặt double KhoangCachDiemVaDuongThang(Point p, Line line) { }
  14. Cấu trúc dữ liệu cơ bản cài đặt 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
  16. Điểm và đoạn thẳng, đường cài đặt 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 cài đặt 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)) • uuu r P thuộc tia AB nếu uuu r 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
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
2=>2