Lý thuyết hình học trong toán tin

Lý thuyết hình học trong toán tin
1. Điểm, đường thẳng, đoạn thẳng: a. Điểm (Point): Trong hình học, chúng ta xét trong hệ Đề các xoy, thì một điểm có toạ độ: (x,y). Chính vì thế ta lưu tọa độ một điểm trong một bản ghi Record: Type point = Record x , y : integer ; End ; Point_Chung = Record x ,y : Real ; End ; Chính vì vậy khi xét tới toạ độ của P(x,y) thì ta xét P.x, P.y Chúng ta biết khoảng cách giữa hai điểm P(x1,y1)và Q(x2,y2) trong mặt phẳng: Function Khoang_Cach(P,Q: Point_Chung ) : Real ; Begin Khoang_Cach:=Sqrt(Sqr(P.x-Q.x)+Sqr(P.y-Q.y)); End ; b. Đường thẳng (line): Trong hình học, chúng ta có phương trình của một đường thẳng trong mặt phẳng: Ax+By+C =0. Chúng ta coi A, B, C là biểu diễn cho đường thẳng đó. Nếu một đường thẳng (d): Ax + By + C = 0, đi qua 2 điểm A (x1,y1) và B(x2,y2) thì nó có: A:= y1- y2; B:= x2 - x1; C:= -(A.x1+B.y1). Chính vì thế chúng ta dùng thủ tục xác định A, B, C của một đường thẳng đi qua 2 điểm như sau: Procedure Xac_DinhABC(P, Q: Point, var A , B , C: Longint ); Begin A := P.y-Q.y ; B := Q.x-P.x ; C := -(A*P.x+B*P.y ) ; End ; Và chúng ta có thể coi đường thẳng là một kiểu: Type Lines = Record a , b , c : Longint; End ; Chú ý: * ″Lines″ chứ không phải là ″Line″, vì trong Pascal có thủ tục Line để vẽ đường thẳng. Thông thường chúng ta làm bài hình học để quan sát trực quan thì chúng ta thường biểu diễn lên hình vẽ. Chính vì thế chúng ta cần phải tránh những sai sót không đáng có. * Sở dĩ chúng ta phải khai báo A, B, C trong Longint vì nếu chúng ta lưu A, B, C trong Longint thì lúc chúng ta tính toán phương trình không tràn bộ nhớ số học. c. Đoạn thẳng: Đoạn thẳng là một phần của đường thẳng, bị giới hạn x, y. Chúng ta xét đoạn thẳng thông thường cho đi qua 2 điểm. Chính vì thế toạ độ x, y bị giới hạn trong khoảng đó. 2. Phương trình tương quan giữa điểm và đường thẳng, đoạn thẳng: a. Tương quan giữa điểm và đường thẳng: Cho đường thẳng (d) có phương trình: Ax +By + C = 0 và P(x,y). Thì phương trình: F(x,y) = A*P.x + B*P.y + C, là phương trình tương quan của P với (d). Đúng vậy: * Nếu F (x,y)=0 thì P thuộc (d). Ngược lại nếu F(x,y)<>0 thì P không thuộc (d). * Nếu Q (x1,y1) mà nằm cùng phía không thuộc (d) thì F (x1,y1)*F(x,y)>0, và nếu khác phía thì F(x1,y1)*F(x,y)<0. Đây là một trong những điều kiện giúp ích cho ta rất nhiều trong giải toán tin hình học và cũng là một phương tiện thiết kế chương trình trong hình học dẽ dàng hơn. Chúng ta xây dựng hàm Phuong_Trinh để xác định mối tương quan của đường thẳng với một điểm: Function Phuong_trinh (L : Lines ; P : Point_Chung ) : Real ; Begin Phuong_Trinh:=L.a*P.x+L.b*P.y+L.c; End ; b. Tương quan của điểm với đoạn thẳng. Chúng ta biết rằng, đoạn thẳng là một phần đường thẳng. Nên mối tương quan giữa điểm P(x,y) với đoạn thẳng AB, (A (x1,y1), B(x2,y2)) là: - Nếu P[AB] thì: + F(x,y)=0, tức là: a*x+b*y+c=0, với a=y1-y2; b=x2-x1 và c=- (a*x1+b*y1). + (x