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) | PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − HÌNH HỌC − Chương 9 1 Algorithm Design 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 Điểm, Đường, Tia, Giao 2 đường thẳng Đa giác, điểm trong đa giác, Bao lồi 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 P x yp y xp x1 x2 y1 y2 0 P1 P2 B A X Y 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). 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 hay 6 Quy tac nho: Ax: y1-y2 By: x2-x1 C: tich ve trai – tich ve phai (x1y2-x2y1) 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)0 Phần 3: Gồm các điểm làm cho F(x,y)<0 x y 0 + + + + + + + + + + Cấu trúc dữ .
