Computational Geometry

Bài toán
Tìm kiếm hình học
Chương 2
Nội dung trình bày
Xác định giao của các đoạn thẳng.
Xác định vị trí điểm.
Tìm kiếm theo khoảng.
Giao của các đoạn thẳng
Bài toán:
Cho tập S gồm n đoạn thẳng (đóng) trên mặt phẳng. Xác định tất cả các giao điểm giữa các đoạn thẳng trong S.
Phương pháp đơn giản nhất
Kiểm tra sự giao nhau của từng cặp đoạn thẳng.
Thuật toán có độ phức tạp thực thi là O(n2).
Số giao điểm nhỏ hơn n2 rất nhiều.
Phương pháp dòng quét
S = {s1, s2, …, sn}
Điểm sự kiện
Trạng thái của đường thẳng quét l là tập hợp các đoạn thẳng cắt l.
Trạng thái thay đổi khi l di chuyển và gặp các điểm sự kiện.
Phương pháp dòng quét
Khi đường thẳng quét gặp điểm sự kiện:
Cập nhật trạng thái dòng quét.
Nếu là điểm mút trên thì thêm đoạn thẳng vào trạng thái.
Nếu là điểm mút dưới thì loại đoạn thẳng khỏi trạng thái.
Kiểm tra sự giao nhau.
Phương pháp dòng quét
Kiểm tra sự giao nhau
Sắp xếp các đoạn thẳng cắt dòng quét từ trái sang phải theo các điểm mút trên.
Kiểm tra sự giao nhau của 2 đoạn kề nhau. Cụ thể là giữa đoạn mới với nhiều nhất 2 đoạn khác.
Trạng thái dòng quét
Dãy có thứ tự các đoạn thẳng cắt dòng quét.
Trạng thái thay đổi tại các điểm sự kiện
Các điểm mút của đoạn thẳng.
Giao điểm của các đoạn thẳng.
Định lý (Kiểm tra sự giao nhau)
Cho si và sj là 2 đoạn thẳng không song song với trục Ox và giao nhau tại p. Giả sử không có đoạn thẳng thứ ba qua p. Khi đó tồn tại điểm sự kiện phía trên p trong đó si và sj kề nhau và được kiểm tra sự giao nhau.
Xử lý điểm sự kiện
Điểm sự kiện là điểm mút trên của đoạn thẳng
Phát hiện giao điểm
Xử lý điểm sự kiện
Điểm sự kiện là giao của 2 đoạn thẳng
Xử lý điểm sự kiện
Điểm sự kiện là điểm mút dưới của đoạn thẳng
Cấu trúc dữ liệu
Lưu hàng đợi sự kiện
Sử dụng cây nhị phân tìm kiếm cân bằng Q.
Thứ tự sắp xếp: p và q là 2 điểm sự kiện thì p < q nếu và chỉ nếu
py > qq hoặc
py = qy và px < qx
Với mỗi điểm p trong Q lưu lại đoạn thẳng có điểm mút trên ứng với p.
Có 2 thao tác
Chuyển đến điểm sự kiện kế tiếp.
Chèn điểm sự kiện mới vào.
Cấu trúc dữ liệu
Lưu trạng thái dòng quét
Sử dụng cây nhị phân tìm kiếm cân bằng T.
Thứ tự sắp xếp: r và s là 2 đoạn thẳng thì r < s nếu và chỉ nếu
rx1 < sx1 hoặc
rx1 = sx1 và rx2 < sx2
Thuật toán xác định giao các đoạn
Input: Tập các đoạn thẳng S trong mặt phẳng
Output: Tập các giao điểm và các cặp đoạn thẳng tương ứng.
B1: Khởi tạo Q. Chèn các điểm mút của các đoạn thẳng vào Q. Khi gặp điểm mút trên lưu lại đoạn thẳng tương ứng.
B2: Khởi tạo T là trạng thái rỗng.
B3: while Q ≠ {}
Xác định điểm sự kiện p kế tiếp trong Q và xóa p;
XulySukien(p);
Thuật toán xử lý sự kiện
Thuật toán xử lý sự kiện
B1: U(p) = {s ∈ S : đoạn thẳng có điểm mút trên là p}
B2:
L(p) = {s ∈ T : đoạn thẳng có điểm mút dưới là p};
C(p) = {s ∈ T : đoạn thẳng chứa p bên trong};
B3: if card(L(p) ∪ U(p) ∪ C(p)) > 1
p là giao điểm của các đoạn L(p) ∪ U(p) ∪ C(p).
B4: T = T - L(p) ∪ C(p)
B5: T = T + U(p) ∪ C(p). Thứ tự các đoạn thẳng trong T ứng với thứ tự các đoạn thẳng giao với dòng quét phía dưới p. Nếu có đoạn song song với Ox thì có thứ tự là lớn nhất.
Thuật toán xử lý sự kiện
B6: if U(p) ∪ C(p) = {}
sl và sr là hai đoạn kề trái, phải của p trong T
TimSukien(sl, sr, p)
B7: else
s’ là đoạn ngoài cùng bên trái của U(p) ∪ C(p) trong T
sl đoạn kề trái của s’ trong T
TimSukien(sl, s’, p)
s” là đoạn ngoài cùng bên phải của U(p) ∪ C(p) trong T
sr đoạn kề trái của s’ trong T
TimSukien(s”, sr, p)
Tìm sự kiện cho sl, sr, p
If sl và sr giao phía dưới dòng quét hoặc phía trên và bên phải p và giao điểm chưa xuất hiện trong Q
Chèn giao điểm vào Q
Định lý (Độ phức tạp của thuật toán)
Thời gian thực thi: O(nlogn + Ilogn), với I là số giao điểm.
Không gian lưu trữ: O(n)
Xác định vị trí điểm
q
S
Xác định bằng các dãi
Phân hoạch đồ thị theo truc Oy thành các dãi.
Tìm kiếm nhị phân theo tọa độ x, xác định dãi chứa q trong O(logn).
q
Tìm kiếm trên dãi
Sắp xếp các đoạn trong một dãi theo thứ tự từ trên xuống.
Mỗi đoạn gắn nhãn là mảnh f chứa q.
Tìm kiếm nhị phân trên các đoạn xác định vị trí của q.
q
Độ phức tạp
Với 2 lần tìm kiếm nhị phân:
Tối đa 2n dãi cho đồ thị n cạnh.
n cạnh của một dãi
thời gian thực thi là O(logn).
Không gian gồm:
O(n) cho phân hoạch đồ thị thành 2n dãi.
O(n) cho các cạnh trong một dãi.
Tổng không gian là O(n2).
Xác định bằng các hình thang
Đưa đồ thị S về dạng S’ gồm các mảnh hình thang, tam giác và hình thang hở.
Một mãnh f’ ∈ S’ nằm trong một mãnh f ∈ S. Nếu biết mảnh q ∈ f’ thì xác định được f.
S’
q
Phân hoạch dạng thang
T(S) là đồ thị dạng thang của S.
Mỗi mảnh trong T(S) có 1 hoặc 2 lề dọc và đúng 2 lề ngang.
Gọi lề ngang trên và dưới của mảnh ∆ của T(S) là top(∆) và bottom(∆).
Phân hoạch dạng thang
Các trường hợp lề trái của mảnh ∆ của T(S)






T(S) của tập S gồm n cạnh có tối đa 6n+4 đỉnh và 3n+1 mảnh hình thang.
Phân hoạch dạng thang
Mảnh thang liền kề:
Cấu trúc dữ liệu
Phân hoạch dạng thang T(S)
Cấu trúc tìm kiếm D
Cấu trúc dữ liệu
Cấu trúc lưu trữ phân hoạch dạng thang T(S)
Mảnh thang ∆ gồm:
top(∆), right(∆), leftp(∆), rightp(∆).
4 mảnh thang lân cận.
Sử dụng danh sách liên kết.
Cấu trúc tìm kiếm D
Sử dụng dạng cây nhị phân tìm kiếm.
Thuật toán xác định vị trí điểm
Input: Tập các đoạn thẳng không giao nhau S và điểm q.
Output: Vị trí của q.
B1: Xác định hình chữ nhật giới hạn R
Khởi tạo T
D = ∅
B2: Xác định một hoán vị s1, s2, …, sn của S
B3: i = 1
B4: Tìm các ∆0, ∆1, …, ∆k là các mảnh thang trong T và giao với si
B5: Xóa ∆0, ∆1, …, ∆k khỏi T và thay bằng các mảnh thang mới xuất hiện bởi si
B6: Xóa các nốt lá ứng với ∆0, ∆1, …, ∆k trong D và tạo các nốt lá ứng với các mảnh thang mới
B7: Nếu i < n thì i = i + 1. Quay lại B4.
B8: Tìm vị trí của q thông qua D.
Hiệu chỉnh T và D
Đặt Si = {s1, s2, …, si}. T và D
T ban đầu là T(S0) = T(∅)
D ban đầu chỉ có 1 nốt lá là R
T(Si) được xây dựng từ T(Si-1)
Nếu điểm mút trái p của si không có trong D. Xác định ∆0 ∈ T(Si-1) chứa p.
Nếu p có trong D thì p nằm trên
đường thẳng dọc đi qua một
x-nốt. Ta xem như p nằm bên
phải x-nốt.
p
Hiệu chỉnh T và D
Input: T(Si-1), D, si
Output: ∆0, ∆1, …, ∆k giao với si
B1: Đặt p và q là điểm mút trái và phải của si
B2: Tìm ∆0 chứa p trong D
B3: j = 0
B4: Nếu q ở bên phai rightp(∆j)
Nếu rightp(∆j) ở phía trên si thì ∆j+1 là lân cận phải dưới của ∆j. Ngược lại ∆j+1 là lân cận phải trên của ∆j.
Ngược lại, chuyển sang B6.
B5: j = j + 1. Quay lại B4.
B6: Trả về các ∆0, ∆1, …, ∆j
Hiệu chỉnh T và D
Hiệu chỉnh T(S) và D
Hiệu chỉnh T và D
Quy tắc hiệu chỉnh D
Nếu ∆0 chứa điểm mút trái của si thì thay ∆0 bằng x-nốt ứng với điểm mút trái và y-nốt ứng với si.
Nếu ∆k chứa điểm mút phải của si thì thay ∆k bằng x-nốt ứng với điểm mút phải và y-nốt ứng với si.
∆1, …, ∆k-1 được thay bằng các y-nốt ứng với si.
Gắn các x-nốt và y-nốt mới với các nốt lá tương ứng.
Thuật toán xác định vị trí điểm bằng phân hoạch dạng thang T(S) của tập n đoạn thẳng không chéo nhau S có độ phức tạp:
O(nlogn) thực thi để xây dựng T(S) và D.
O(n) không gian lưu trữ.
O(logn) thực thi xác định điểm.