Tài liệu Các thuật toán xén điểm, đoạn thẳng

Vấn đề tối ưu hóa tốc độ
· Ý tưởng chung :
¨ Đối với các đoạn thẳng đặc biệt như nằm hoàn toàn
trong hoặc hoàn toàn bên ngoài cửa sổ (ví dụ như đoạn
P1P2 và P3P4 trong hình trên) : không cần phải tìm giao
điểm.
¨ Đối với các đoạn thẳng có khả năng cắt cửa sổ : cần phải
đưa ra cách tìm giao điểm nhanh.
· Nhận xét
¨ Các đoạn thẳng mà có cả hai điểm nằm hoàn toàn trong
cửa sổ thì cả đoạn thẳng nằm trong cửa sổ, đây cũng
chính là kết quả sau khi xén (ví dụ như đoạn thẳng
P1P2), mặt khác đối với các đoạn thẳng mà có hai điểm
nằm về cùng một phía của cửa sổ thì luôn nằm ngoài cửa
sổ và sẽ bị mất sau khi xén (ví dụ như đoạn thẳng P3P4).
¨ Với các đoạn thẳng có khả năng cắt cửa sổ (ví dụ như
đoạn thẳng P5P6 và P7P8) để việc tìm giao điểm nhanh
cần rút gọn việc tìm giao điểm với những biên cửa sổ
không cần thiết để xác định phần giao nếu có của đoạn
thẳng và cửa sổ.