Giáo trình Đồ họa máy tính I (Phần 2)

3.1 Mở đầu

Một trong những bài toán quan trọng của đồ họa máy tính là xác định được phần giao (còn gọi là cắt xén) các nguyên sơ giao điểm của hai đoạn thẳng, giao của đường thẳng với đường tròn hay đa đa giác lồi. Vấn đề ở đây là xác định các đối tượng có giao nhau không? Nếu có thì tìm giao của chúng.

Như đã đề cập trong Chương 1, các thuật toán cần thực hiện nhanh nhất có thể được để cung cấp người sử dụng cập nhật nhanh các kết quả thay đổi trong ứng dụng. Chúng ta sẽ áp dụng các phương pháp giải tích để giải quyết các bài toán trong chương này.

3.2

Giao của hai đoạn thẳng

Một bài toán thông dụng trong đồ họa máy tính là xác định giao của hai đoạn thẳng. Đây là một phần quyết định của những thuật toán tìm giao (chẳng hạn, giao hai đa giác) và xuất hiện trong nhiều tiến trình khác, Phần này áp dụng việc tham số hoá của đoạn thẳng để giải quyết bài toán sau

Bài toán

Trong mặt phẳng cho hai đoạn thẳng AB và CD. Xác định giao điểm của chúng nếu có.