Hình học - Giao điểm của hai đoạn thẳng

25.9.2004*Giao điểm của hai đoạn thẳng25.9.2004Chương 11: Giao điểm của hai đoạn thẳng*Tính chất của đoạn thẳngĐịnh nghĩaMộ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 chox3 = a x1 + (1 - a) x2y3 = a y1 + (1 - a) y20  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 p1p2Cá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.2004Chương 11: Giao điểm của hai đoạn thẳng*Tích chéoĐịnh nghĩa Tích chéo của hai vectors p1 = (x1,y1) và p2 = (x2 ,y2) là Nhận xétNếu p1  p2 > 0 thì vectơ p1 nằm theo chiều kim đồng hồ từ vectơ p2 đối với (0, 0)Nếu p1  p2 0 thì p0p1 nằm theo chiều kim đồng hồ từ p0p2 Nếu (p1 - p0)  (p2 - p0) 0 and d2 0)) and ((d3 > 0 and d4 0)) 6 then return TRUE(xem tiếp slide tới)25.9.2004Chương 11: Giao điểm của hai đoạn thẳng*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 TRUE11 elseif d3 = 0 and ON-SEGMENT(p1, p2, p3)12 then return TRUE13 elseif d4 = 0 and ON-SEGMENT(p1, p2, p4)14 then return TRUE15 else return FALSE25.9.2004Chương 11: Giao điểm của hai đoạn thẳng*Xác định hai đoạn thẳng có cắt nhau không (tiếp)Thủ tục ON-SEGMENTInput: 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 TRUE3 else return FALSE