Bài giảng Giải thuật - Chương 11, Phần 2: Hình học tính toán

Hình Học Tính Toán 
13.11.2004 
1 
35.2 Xác định có cặp đoạn thẳng nào cắt nhau không 
Bài toán : Cho tập các đoạn thẳng trong mặt phẳng. Xác định có cặp đoạn thẳng nào cắt nhau hay không. 
Để đơn giản, giả sử: 
Không có đoạn thẳng nào là thẳng đứng 
Không có ba đoạn thẳng nào cắt nhau tại một điểm chung. 
13.11.2004 
2 
Chương 35: Hình học tính toán 
Giải thuật thô sơ 
Giải thuật thô sơ: Kiểm tra xem mỗi cặp đoạn thẳng có cắt nhau hay không. Thời gian chạy là ( n 2 ), với n là số các đoạn thẳng. 
13.11.2004 
3 
Chương 35: Hình học tính toán 
Kỹ thuật quét 
Giải thuật hữu hiệu dùng kỷ thuật quét (sweeping): 
Dùng một đưòng thẳng thẳng đứng quét từ trái sang phải và xem xét các thay đổi của phần giao của đường thẳng quét với các đoạn thẳng. 
 Đường thẳng quét (sweep line) 
Đường thẳng quét thẳng đứng, vị trí hiện thời là toạ độ x 
x 
13.11.2004 
4 
Chương 35: Hình học tính toán 
Thứ tự các đoạn thẳng 
Định nghĩa một thứ tự hoàn toàn trên các đoạn thẳng cắt bởi đường thẳng quét. 
Hai đoạn thẳng s 1 và s 2 không cắt nhau là có thể so sánh được tại x nếu đường thẳng quét tại vị trí x cắt cả hai đoạn thẳng đó. 
Nếu s 1 và s 2 là có thể so sánh được tại x và giao điểm của s 1 với đường thẳng quét ở cao hơn giao điểm của s 2 với cùng đường thẳng quét đó, thì ta nói s 1 ở trên s 2 , ký hiệu s 1 > x s 2 . 
s 2 
s 1 
13.11.2004 
5 
Chương 35: Hình học tính toán 
a 
b 
c 
d 
e 
g 
h 
f 
i 
r 
t 
u 
v 
z 
w 
(a) 
(b) 
a > r c 
a > t b 
b > t c 
a > t c 
b > u c 
Đoạn thẳng d không so sánh được với 
các đoạn thẳng khác trong hình (a). 
e > v f nhưng f > w e 
Mọi đường thẳng quét mà đi qua vùng xám đều có các đoạn thẳng e và f ở liên tiếp nhau trong quan hệ thứ tự của nó 
Thứ tự các đoạn thẳng (tiếp) 
13.11.2004 
6 
Chương 35: Hình học tính toán 
Các cấu trúc dữ liệu trong kỹ thuật quét 
Đường thẳng quét 
Khi di chuyển đường thẳng quét, giải thuật trữ và duy trì các thông tin sau 
Tình trạng của đường thẳng quét (sweep-line status): cho biết thứ tự giữa các đối tượng (đoạn thẳng) bị cắt bởi đường thẳng quét với nhau 
Lịch của các biến cố (event-point schedule): dãy các tọa độ x , sắp từ trái sang phải, xác định các vị trí dừng của đường thẳng quét. 
13.11.2004 
7 
Chương 35: Hình học tính toán 
Các thao tác lên sweep-line status 
Chi tiết giải thuật hữu hiệu dùng kỷ thuật quét 
Đường thẳng quét 
Khi di chuyển đường thẳng quét, giải thuật trữ và duy trì các thông tin sau 
Tình trạng của đường thẳng quét (sweep-line status): Các thao tác lên T : 
 I NSERT ( T , s ) : chèn đoạn thẳng s vào T 
 D ELETE ( T , s ) : xoá đoạn thẳng s khỏi T 
 A BOVE ( T , s ) : trả về đoạn thẳng ở ngay trên s trong T 
 B ELOW ( T , s ) : trả về đoạn thẳng ở ngay dưới s trong T . 
13.11.2004 
8 
Chương 35: Hình học tính toán 
Event-point schedule 
Lịch của các biến cố (event-point schedule): dãy các tọa độ x , sắp từ trái sang phải, xác định các vị trí dừng của đường thẳng quét. 
Mỗi điểm đầu mút của các đoạn thẳng (của tập input S ) là một điểm biến cố (event point), là điểm mà thứ tự T thay đổi. 
Lịch của các biến cố là tĩnh và được xây dựng bằng cách sắp xếp các điểm đầu mút của các đoạn thẳng theo thứ tự từ trái qua phải. 
13.11.2004 
9 
Chương 35: Hình học tính toán 
Xác định có cặp đoạn thẳng nào cắt nhau không 
A NY -S EGMENTS -I NTERSECT ( S ) 
1 T   
2 Sắp các điểm đầu mút của các đoạn thẳng trong S theo 
 thứ tự từ trái sang phải, breaking ties... 
3 for mổi điểm p trong danh sách sắp xếp của các điểm đầu mút 
4 do if p là điểm đầu mút bên trái của đoạn thẳng s 
5 then I NSERT ( T , s ) 
6 if (A BOVE ( T , s ) tồn tại và cắt s ) 
 hay (B ELOW ( T , s ) tồn tại và cắt s ) 
7 then return TRUE 
8 if p là điểm đầu mút bên phải của đoạn thẳng s 
9 then if cả hai A BOVE ( T , s ) và B ELOW ( T , s ) đều tồn tại 
 và A BOVE ( T , s ) cắt B ELOW ( T , s ) 
10 then return TRUE 
11 D ELETE ( T , s ) 
12 return FALSE 
13.11.2004 
10 
Chương 35: Hình học tính toán 
Thực thi A NY -S EGMENTS -I NTERSECT 
a 
b 
c 
d 
e 
f 
a 
a 
a 
d 
d 
e 
e 
b 
c 
a 
c 
d 
d 
b 
c 
b 
c 
b 
b 
b 
thời gian 
13.11.2004 
11 
Chương 35: Hình học tính toán 
Breaking ties 
Nếu khi sắp xếp các điểm đầu mút của các đoạn thẳng trong S từ trái sang phải mà có nhiều điểm có cùng tọa độ x thì breaking ties như sau 
Các điểm đầu mút bên trái được xếp trước các điểm đầu mút bên phải. 
a 
b 
p 
q 
p được xếp trước q khi sắp xếp các điểm đầu mút 
ở dòng 2 của A NY -S EGMENTS -I NTERSECT 
13.11.2004 
12 
Chương 35: Hình học tính toán 
Tính đúng đắn 
Theorem 35.1 (Tính đúng đắn) 
	Giải thuật A NY -S EGMENTS -I NTERSECT chạy trên tập S trả về TRUE nếu và chỉ nếu có cắt nhau giửa các đoạn thẳng. 
Chứng minh 
“”: xem mã ta thấy A NY -S EGMENTS -I NTERSECT trả về TRUE chỉ khi nào nó tìm thấy hai đoạn thẳng cắt nhau. 
“”: Sẽ chứng minh rằng nếu tồn tại hai đoạn thẳng cắt nhau thì A NY -S EGMENTS -I NTERSECT trả về TRUE . 
13.11.2004 
13 
Chương 35: Hình học tính toán 
Tính đúng đắn (tiếp) 
Giả sử tồn tại một giao điểm. 
Gọi p là giao điểm bên trái nhất, gọi a và b là các đoạn thẳng cắt nhau tại p . 
Tồn tại đường quét z mà tại đó a và b trở nên liên tiếp nhau trong thứ tự toàn phần. 
Tồn tại điểm đầu mút q mà là event point để cho a và b trở nên liên tiếp nhau trong thứ tự toàn phần. 
Có 2 trường hợp: A) giải thuật xử lý q và B) giải thuật không xử lý q . 
p 
z 
a 
b 
13.11.2004 
14 
Chương 35: Hình học tính toán 
Tính đúng đắn (tiếp) 
A) 
Trường hợp 1 : đoạn thẳng a hay b được chèn vào T , và đoạn thẳng kia ở trên hay dưới nó. Các dòng 4-7 tìm thấy trường hợp này. 
p 
p 
p 
z 
z 
q 
q 
q 
p 
z 
q 
p 
z 
q 
z 
p 
q 
z 
13.11.2004 
15 
Chương 35: Hình học tính toán 
Tính đúng đắn (tiếp) 
Trường hợp 2 : các đoạn thẳng a và b đang trong T , và một đoạn thẳng ở giữa chúng được xóa. Các dòng 8-11 tìm thấy trường hợp này. 
Trong cả hai trường hợp, giải thuật tìm thấy p và trả về TRUE . 
B) 
Nếu q không được giải thuật xử lý, thì có nghĩa là giải thuật đã quay về trước khi xử lý xong tất cả các event points. Vậy giải thuật đã tìm thấy một giao điểm và trả về TRUE . 
p 
z 
q 
13.11.2004 
16 
Chương 35: Hình học tính toán 
Phân tích A NY -S EGMENTS -I NTERSECT 
Thời gian chạy 
Giả sử tập đoạn thẳng S gồm có n đoạn thẳng. Dùng cấu trúc dữ liệu thích hợp (ví dụ: dựa trên cây nhị phân cân bằng) để hiện thực T sao cho các thao tác lên T đều tốn O (lg n ) thời gian. 
Thời gian chạy của giải thuật A NY -S EGMENTS -I NTERSECT gồm 
Dòng 1: O (1) thời gian 
Dòng 2: O ( n lg n ) thời gian 
Vòng lặp for : O ( n lg n ) thời gian 
Vậy thời gian chạy tổng cộng của giải thuật là O ( n lg n ). 
13.11.2004 
17 
Chương 35: Hình học tính toán 
35.4 Tìm bao lồi 
Tự đọc. 
13.11.2004 
18 
Chương 35: Hình học tính toán 
35.4 Tìm cặp điểm gần nhau nhất 
Tự đọc. 
13.11.2004 
19 
Chương 35: Hình học tính toán