intTypePromotion=1

Bài giảng Phân tích thiết kế giải thuật - Chương 35: Hình học tính toán

Chia sẻ: Đinh Trường Gấu | Ngày: | Loại File: PPT | Số trang:19

0
48
lượt xem
1
download

Bài giảng Phân tích thiết kế giải thuật - Chương 35: Hình học tính toán

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 35: Hình học tính toán trong "Bài giảng Phân tích thiết kế giải thuật" giới thiệu đến bạn đọc những kiến thức giải thuật thô sơ, kỹ thuật quét, thứ tự có đoạn thẳng, tính đúng đắn. Hy vọng, đây là tài liệu tham khảo hữu ích dành cho các bạn.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Phân tích thiết kế giải thuật - Chương 35: Hình học tính toán

  1. Hình Học Tính Toán 13.11.2004 1
  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 2
  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à  (n2), 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 3
  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 4
  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 s1 và s2 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 đó. s2 s1 – Nếu s1 và s2 là có thể so sánh được tại x và giao điểm của s1  với đường thẳng quét ở cao hơn giao điểm của s2 với cùng  đường thẳng quét đó, thì ta nói s1 ở trên s2 , ký hiệu s1  x  s2 . 13.11.2004 Chương 35: Hình học tính toán 5
  6. Thứ tự các đoạn thẳng (tiếp) e d g a i b h c f r t u v z w (a) (b) a  r c a  t b b  u c e  v  f  nhưng  f  w e  b  t c Mọi đường thẳng quét mà đi qua vùng  a  t c xám đều có các đoạn thẳng e và f ở liên  Đoạn thẳng d không so sánh được với tiếp nhau trong quan hệ thứ tự của nó các đoạn thẳng khác trong hình (a). 13.11.2004 Chương 35: Hình học tính toán 6
  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 7
  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 8
  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 9
  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 học tính toán 10
  11. Thực thi ANY­SEGMENTS­INTERSECT  e a d c f b 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 11
  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 q b p 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 12
  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 13
  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. a p b z   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. 13.11.2004 Chương 35: Hình học tính toán 14
  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. q q p q p p z z z p p p q q q z z z 13.11.2004 Chương 35: Hình học tính toán 15
  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. q p z   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. 13.11.2004 Chương 35: Hình học tính toán 16
  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 học tính toán 17
  18. 35.4    Tìm bao lồi ª Tự đọc. 13.11.2004 Chương 35: Hình học tính toán 18
  19. 35.4    Tìm cặp điểm gần nhau nhất ª Tự đọc. 13.11.2004 Chương 35: Hình học tính toán 19
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2