Tiểu Luận Phương pháp thiết kế thuật toán giải quyết một số bài toán trong hình học

1. Các khái niệm cơ bản
1.1. Điểm
Điểm là một đối tượng hình học cơ sở. Trong không gian hai chiều với hệ trục toạ độ Descart người ta biểu diễn điểm là bởi một cặp số thực (x, y). Để đơn giản trong việc biểu diễn và tính toán trên máy tính chúng ta sử dụng cặp toạ độ số nguyên để biểu diễn cho một điểm.
Với ngôn ngữ lập trình Pascal ta khai báo cấu trúc của điểm như sau:
TYPE POINT = Record
x, y : Integer;
END;
VAR p : POINT;
​ 1.2. Đoạn thẳng và các tính chất của đoạn thẳng
Đoạn thẳng là một phần của đường thẳng đi qua hai điểm P1, P2 và được giới hạn bởi hai điểm phân biệt P1 và P2.
Với ngôn ngữ lập trình Pascal ta khai báo cấu trúc của đoạn thẳng như sau:
TYPE LINE = Record
P1, P2 : POINT;
END;
VAR l : LINE;
​ Cho hai điểm phân biệt P1 = (x1, y1) và P­2 = (x2, y2), tổ hợp lồi của hai điểm P1 và P2 là bất kỳ điểm P3 (x3, y3) sao cho với a mà 0 £ a £ 1, ta có x3 = ax1 + (1 - a)x2 và y3 = ay1 + (1 - a)y2. Ta có thể viết gọn lại như sau: P3 = aP1 + (1 - a)P2. Theo trực giác thì P3 nằm trên đoạn thằng P1 và P2, hai điểm P1 và P2 được gọi là các điểm cuối của đoạn thẳng P1P2. Nếu ta quan tâm đến thứ tự sắp xếp của P1 và P2 thì ta nói về đoạn thẳng có hướng , Nếu P1 là gốc (0, 0) thì ta có thể xem đoạn thẳng có hướng như vectơ .
1.3. Đa giác
Đa giác là một danh sách các điểm, với hai điểm cạnh nhau được nối bởi một đoạn thẳng và điểm đầu và điểm cuối trùng nhau. Đa giác bao giờ cũng là một đường khép kín. Thông thường chúng ta sử dụng mảng các điểm để biểu diễn một đa giác, trong một số trường hợp chúng ta có thể sử dụng danh sách liên kết.
Với ngôn ngữ lập trình Pascal ta khai báo cấu trúc của đa giác như sau:
VAR polygon : Array[0 100] of POINT;
​