13.11.2004 1
Hình Hoïc Tính Toaùn
13.11.2004 Chương 35: Hình
học tính toán
2
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 Chương 35: Hình
học tính toán
3
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 Chương 35: Hình
học tính toán
4
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 Chương 35: Hình
học tính toán
5
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 Chương 35: Hình
học tính toán
6
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 Chương 35: Hình
học tính toán
7
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 Chương 35: Hình
học tính toán
8
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:
°
INSERT(T, s): chèn đoạn thẳng s vào T
°
DELETE(T, s): xoá đoạn thẳng s khỏi T
°
ABOVE(T, s): trả về đoạn thẳng ở ngay trên s trong T
°
BELOW(T, s): trả về đoạn thẳng ở ngay dưới s trong T.
13.11.2004 Chương 35: Hình
học tính toán
9
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 Chương 35: Hình
học tính toán
10
Xác đònh có cặp đoạn thẳng nào cắt nhau không

ANY-SEGMENTS-INTERSECT(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 INSERT(T, s)
6 if (ABOVE(T, s) tồn tại và cắt s)
hay (BELOW(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 ABOVE(T, s) và BELOW(T, s) đều tồn tại
và ABOVE(T, s) cắt BELOW(T, s)
10 then return TRUE
11 DELETE(T, s)
12 return FALSE
13.11.2004 Chửụng 35: Hỡnh
hoùc tớnh toaựn
11
Thửùc thi ANY-SEGMENTS-INTERSECT
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 Chương 35: Hình
học tính toán
12
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 ANY-SEGMENTS-INTERSECT
13.11.2004 Chương 35: Hình
học tính toán
13
Tính đúng đắn
ª
Theorem 35.1 (Tính đúng đắn)
Giải thuật ANY-SEGMENTS-INTERSECT 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 ANY-SEGMENTS-INTERSECT 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ì
ANY-SEGMENTS-INTERSECT trả về TRUE.
13.11.2004 Chương 35: Hình
học tính toán
14
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 Chương 35: Hình
học tính toán
15
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 Chương 35: Hình
học tính toán
16
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 Chương 35: Hình
học tính toán
17
Phân tích ANY-SEGMENTS-INTERSECT
ª
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 ANY-SEGMENTS-INTERSECT 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 Chöông 35: Hình
hoïc tính toaùn
18
35.4 Tìm bao loài
ª
Töï ñoïc.
13.11.2004 Chương 35: Hình
học tính toán
19
35.4 Tìm cặp điểm gần nhau nhất
ª
Tự đọc.