intTypePromotion=1
ADSENSE

Bài giảng Chương 11: Giao điểm của hai đoạn thẳng

Chia sẻ: Đinh Trường Gấu | Ngày: | Loại File: PPT | Số trang:13

94
lượt xem
2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu về Công nghệ thông tin, mời các bạn cùng tham khảo nội dung "Bài giảng Chương 11: Giao điểm của hai đoạn thẳng" dưới đây. Nội dung bài giảng cung cấp cho các bạn những kiến thức về tính chất của đoạn thẳng, tính chéo, xác định hai đoạn thẳng có cắt nhau không.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Chương 11: Giao điểm của hai đoạn thẳng

  1. Giao điểm của hai đoạn thẳng 25.9.2004 1
  2. Tính chất của đoạn thẳng ª Định nghĩa – Một tổ hợp lồi của hai điểm khác nhau p1   (x1,y1) và p2   (x2 ,y2)  là một điểm p3   (x3 ,y3) sao cho x3     x1   (1   a) x2 y3     y1   (1   a) y2    a   1 . – Đoạn thẳng p1p2 là tập mọi tổ hợp lồi của p1 và p2 , ký hiệu đt p1p2 – Các điểm đầu mút của đoạn thẳng p1p2 là p1 và p2 – Đoạn thẳng có hướng p1p2 là đoạn thẳng p1p2 được định hướng từ  p1 đến p2 , ký hiệu p1 p2 . 25.9.2004 Chương 11: Giao điểm của hai đoạn  2 thẳng
  3. Tích chéo ª Định nghĩa Tích chéo của hai vectors p1   (x1,y1) và p2   (x2 ,y2) là x1 x2 p1 p2 det y1 y2 x1 y2 x2 y1 ª Nhận xét – Nếu p1   p2   0 thì vectơ p1 nằm theo chiều kim đồng hồ từ vectơ  p2 p2 đối với (0, 0) (0,0) p1 – Nếu p1   p2   0 thì vectơ p1 nằm ngược chiều kim đồng hồ từ  p1 vectơ p2 đối với (0, 0) (0,0) p2 – Nếu p1   p2 = 0 thì O, p1 và p2 thẳng hàng. 25.9.2004 Chương 11: Giao điểm của hai đoạn  3 thẳng
  4. Tích chéo (tiếp) y y vectơ nằm ngược chiều p p2 kim đồng hồ từ p (0,0) p1 x (0,0) x vectơ nằm theo chiều kim đồng hồ từ p p1   p2  là diện tích của hình bình hành 25.9.2004 Chương 11: Giao điểm của hai đoạn  4 thẳng
  5. Tích chéo (tiếp) ª Nhận xét   Cho hai đoạn thẳng có hướng p0 p1 và p0 p2 . Dùng phép tịnh tiến mà  vectơ tịnh tiến là   p0 , ta thấy – Nếu (p1   p0)   (p2   p0)   0 thì p0 p1 nằm theo chiều kim đồng hồ  từ p0 p2  – Nếu (p1   p0)   (p2   p0)   0 thì p0 p1 nằm ngược chiều kim đồng  hồ từ p0 p2 . p2  p2  p1  p1  ngược chiều theo chiều kim đồng hồ kim đồng hồ p0  p0  25.9.2004 Chương 11: Giao điểm của hai đoạn  5 thẳng
  6. Xác định hai đoạn thẳng có cắt nhau không ª Bài toán   Cho hai đoạn thẳng p1p2 và  p3p4 . Hỏi: Hai đoạn thẳng có cắt nhau  không?  Hai cách giải quyết ª Cách giải 1: giải hệ thống phương trình bậc nhất để tìm tọa độ của  điểm cắt (nếu có). Cách giải này cần dùng phép chia nên không chính  xác khi tử số gần bằng 0. ª Cách giải 2: không cần dùng phép chia (xem slide tới). 25.9.2004 Chương 11: Giao điểm của hai đoạn  6 thẳng
  7. Xác định hai đoạn thẳng có cắt nhau không (tiếp) – Định nghĩa: Một đoạn thẳng p1p2 nằm hai bên (“straddle”) một  đường thẳng nếu p1 và p2 nằm ở hai bên khác nhau của đường  thẳng. (Trường hợp biên: p1 hay p2 nằm trên đường thẳng.) L p2  L p1  p2  p1  đt p1p2 nằm hai bên đường thẳng L L đt p1p2 không nằm hai bên p1  đường thẳng L p2  25.9.2004 Chương 11: Giao điểm của hai đoạn  7 thẳng
  8. Xác định hai đoạn thẳng có cắt nhau không (tiếp) – Định lý: Hai đoạn thẳng cắt nhau nếu và chỉ nếu một trong các  điều kiện sau (hoặc cả hai) là đúng. ª 1. Mỗi đoạn thẳng nằm hai bên đường thẳng chứa đoạn thẳng  kia. ª 2. Một điểm đầu mút (điểm cuối) của đoạn thẳng này nằm  trên đoạn thẳng kia.  b Đoạn thẳng a nằm hai bên đường  thẳng chứa b, và đoạn thẳng b nằm  a hai bên đường thẳng chứa a 25.9.2004 Chương 11: Giao điểm của hai đoạn  8 thẳng
  9. Xác định hai đoạn thẳng có cắt nhau không (tiếp) Dùng tích chéo để xác định một đoạn thẳng có nằm hai bên một đường thẳng hay không. p2 p3 Các tích chéo (p3   p1)   (p2   p1)  p4 và (p4   p1)   (p2   p1) có dấu khác  nhau, do đó đt p3 p4 nằm hai bên  (p3   p1)   (p2   p1)   0 đường thẳng chứa đt p1 p2 (và  p1 ngược lại) (p4   p1)   (p2   p1)   0 p4 Các tích chéo (p3   p1)   (p2   p1)  p3 và (p4   p1)   (p2   p1) có cùng  p2 dấu, do đó đt p3 p4 không nằm hai  bên đường thẳng chứa đt p1 p2 (và  p1 (p3   p1)   (p2   p1)   0 ngược lại) (p4   p1)   (p2   p1)   0 25.9.2004 Chương 11: Giao điểm của hai đoạn  9 thẳng
  10. Xác định hai đoạn thẳng có cắt nhau không (tiếp) p3 p2 (p3   p1)   (p2   p1)   0 p4 (p4   p1)   (p2   p1)   0 p1 p4 p4 (p4   p1)   (p2   p1)   0 p2 p3 p3 p2 (p3   p1)   (p2   p1)   0 p1 p1 25.9.2004 Chương 11: Giao điểm của hai đoạn  10 thẳng
  11. Xác định hai đoạn thẳng có cắt nhau không (tiếp) – Thủ tục để kiểm tra hai đoạn thẳng p1p2 và p3p4 có cắt nhau không  (mã giả). Thủ tục trả về TRUE nếu hai đoạn thẳng cắt nhau và trả  về FALSE nếu chúng không cắt nhau. SEGMENTS­INTERSECT(p1, p2, p3, p4)   1 d1   DIRECTION(p3, p4, p1)   2  d2   DIRECTION(p3, p4, p2)   3  d3   DIRECTION(p1, p2, p3)   4  d4   DIRECTION(p1, p2, p4)   5 if ((d1 > 0 and d2  0 and d4 
  12. Xác định hai đoạn thẳng có cắt nhau không (tiếp) (tiếp)   7 elseif d1 = 0 and ON­SEGMENT(p3, p4, p1)   8  then return TRUE   9 elseif d2 = 0 and ON­SEGMENT(p3, p4, p2) 10  then return TRUE 11 elseif d3 = 0 and ON­SEGMENT(p1, p2, p3) 12  then return TRUE 13 elseif d4 = 0 and ON­SEGMENT(p1, p2, p4) 14  then return TRUE 15 else return FALSE 25.9.2004 Chương 11: Giao điểm của hai đoạn  12 thẳng
  13. Xác định hai đoạn thẳng có cắt nhau không (tiếp)   Thủ tục ON­SEGMENT   Input: pi , pj , pk , mà pk thẳng hàng với đoạn pi pj    Output: TRUE nếu pk nằm trên đoạn pi pj       FALSE nếu pk nằm ngoài đoạn pi pj  DIRECTION(pi , pj , pk ) 1 return (pk   pi )   (pj   pi ) ON­SEGMENT(pi , pj , pk ) 1 if min(xi , xj )   xk   max(xi , xj ) and min(yi , yj )   yk   max(yi ,  yj ) 2 then return TRUE 3 else return FALSE 25.9.2004 Chương 11: Giao điểm của hai đoạn  13 thẳng
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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