MỤC LỤC

Lời cảm ơn 1

Mục lục 2

Danh mục các hình vẽ 5

NỘI DUNG CỦA ĐỒ ÁN :

Chương 1 : Giới thiệu về cơ sở dữ liệu không gian 7

1.1 Hệ quản trị cơ sở dữ liệu 7

1.2 Những thuật ngữ dùng trong các ứng dụng cơ sở dữ liệu không gian 8

1.2.1 Khái niệm về hệ thống thông tin địa lý 8

1.2.2 Các thuật ngữ trong các ứng dụng GIS 9

1.2.2.1 Theme 9

1.2.2.2 Map 9

1.2.2.3 Đối tượng địa lý 10

1.3 Các phép toán trên dữ liệu địa lý không gian 10

1.3.1 Phép chiếu theme 10

1.3.2 Phép chọn theme 11

1.3.3 Phép hợp theme 11

1.3.4 Phép phủ theme 13

1.3.5 Phép lựa chọn hình học 14

1.3.6 Phép kết hợp 14

1.4 Hệ quản trị cơ sở dữ liệu hỗ trợ cho cơ sở dữ liệu địa lý không gian 15

1.5 Các yêu cầu đối với hệ quản trị cơ sở dữ liệu không gian 16

Chương 2 : Biểu diễn đối tượng không gian 17

2.1 Mô hình không gian địa lý 17

2.1.1 Mô hình thực thể 17

2.1.2 Mô hình không gian 18

2.2 Các phương thức biểu diễn 18

2.2.1 Phương thức Tessellation 18

2.2.2 Phương thức Vector 20

2.2.3 Phương thức biểu diễn Nửa-Phẳng 21

2.3 Biểu diễn hình học của tập các đối tượng 21

2.3.1 Mô hình Mạng 21

2.3.2 Mô hình TôPô 23

Chương 3 : Mô hình Lôgic và ngôn ngữ truy vấn 25

3.1 Các lược đồ tham chiếu 25

3.1.1 Các đơn vị quản lý 25

3.1.2 Mạng lưới giao thông giữa các thành phố 25

3.1.3 Land-Use 26

3.2 Các câu truy vấn mẫu 26

3.3 Các kiểu dữ liệu không gian trừu tượng 27

3.3.1 Mở rộng mô hình với các kiểu dữ liệu không gian trừu tượng 27

3.3.2 Xây dựng các kiểu dữ liệu không gian trừu tượng 29

3.4 Mô hình quan hệ mở rộng với ADT 31

3.4.1 Biểu diễn của lược đồ tham chiếu 31

3.4.2 Truy vấn 34

3.5 Mô hình hướng đối tượng 38

3.5.1 Các khái niệm cơ bản trong hệ cơ sở dữ liệu hướng đối tượng 38

3.5.2 Biểu diễn của lược đồ tham chiếu 39

3.5.3 Các lớp không gian 41

Chương 4 : Mô hình dữ liệu ràng buộc 43

4.1 Mô hình dữ liêu không gian với các ràng buộc 43

4.2 Mô hình dữ liệu ràng buộc tuyến tính 48

4.2.1 Biểu diễn dữ liệu 48

4.2.2 Truy vấn bậc nhất 48

Chương 5 : Các thuật toán cho đối tượng hình học 51

5.1 Các khái niệm cơ bản 51

5.1.1 Thuật toán 51

5.1.2 Phân tích thuật toán 52

5.2 Các chiến lược thuật toán hữu hiệu 53

5.2.1 Thuật toán gia tăng : Ví dụ bao lồi 53

5.2.2 Chiến lược chia để trị : Ví dụ nửa mặt phẳng giao nhau 56

5.2.3 Phương thức đường quét : Ví dụ hình chữ nhật giao nhau 58

5.3 Phân chia đa giác 60

5.3.1 Hình thang hóa một đa giác đơn 60

5.3.2 Tam giác hóa một đa giác đơn 61

5.4 Các thuật toán cho cơ sở dữ liệu không gian 64

5.4.1 Thuật toán kiểm tra điểm trong đa giác 64

5.4.2 Thuật toán kiểm tra đoạn thẳng giao nhau 65

5.4.3 Thuật toán kiểm tra đa giác giao nhau 67

5.4.4 Thuật toán Windowing 67

5.4.5 Thuật toán Clipping 68

Tài liệu tham khảo 71

DANH MỤC CÁC HÌNH VẼ

Hình 1 : Sự tương tác của hệ QTCSDL với người dùng và với CSDL

Hình 2 : Một bản đồ Việt Nam

Hình 3 : Minh họa phép chiếu

Hình 4 : Minh họa phép chọn

Hình 5 : Minh họa phép hợp theme : (a) Những quốc gia có dân số trên 10 triệu, (b) Những quốc gia có dân số ít hơn 10 triệu, (c) Hợp của hai theme (a) và (b).

Hình 6 : Phủ theme : (a) theme những quốc gia phía Tây Châu Âu, (b) Những ngôn ngữ được dùng ở Tây Âu.

Hình 7 : Window

Hình 8 : Clipping

Hình 9 : Merger

Hình 10 : Biểu diễn quan hệ giữa các quốc gia

Hình 11 : (a) Đường gấp khúc khép kín; (b) Đường gấp khúc không đơn; (c) Đường gấp khúc không đơn điệu.

Hình 12 : (a) Đa giác đơn; (b) Đa giác không đơn; (c) Đa giác lồi; (d) Đa giác đơn điệu.

Hình 13 : Tessellation có quy tắc : (a) chia theo lưới vuông, (b) chia theo lục giác đều.

Hình 14 : Tessellation không có quy tắc : (a) các vùng địa chính, (b) biểu đồ Voronoi.

Hình 15 : Biểu diễn đa giác P bằng các pixel.

Hình 16 : Biểu diễn đa giác bằng phương thức vector.

Hình 17 : Đa giác P được biểu diễn bằng các nửa mặt phẳng giới hạn bởi các đường L1, L2, L3.

Hình 18 : Minh họa mô hình mạng.

Hình 19 : Biểu diễn của các đa giác trong mô hình Tôpô.

Hình 20 : Các đơn vị quản lí.

Hình 21 : Minh họa lược đồ 2.

Hình 22 : (a) Điểm, (b) Đường gấp khúc, (c) Đường gấp jgúc phức tạp, (d) Đa giác, (e) tập đa giác, (f) hỗn hợp.

Hình 23 : (a) Hai đa giác lồi, (b) Hai đa giác không lồi, (c) Đường và đa giác, (d) Đường và đa giác có một đoạn chung, (e) Hai đa giác kề nhau.

Hình 24 : Mô hình dữ liệu không gian của các tập điểm trong R : (a) Tập điểm xác định, (b) Tập điểm không xác định.

Hình 25 : Biểu diễn đường gấp khúc trong cơ sở dữ liệu ràng buộc.

Hình 26: Đa giác không lồi trong cơ sở dữ liệu ràng buộc.

Hình 27 : Giao của Road và Spat.

Hình 28 : Ba mức trong sơ đồ.

Hình 29 : Kết quả giao của Road và Spat.

Hình 30 : Biểu diễn kết quả của Query 2.

Hình 31 : Biểu diễn kết quả của Query 3.

Hình 32 : (a) Các tiếp tuyến từ p , (b) Bao lồi mới.

Hình 33 : Minh họa thuật toán gia tăng bao lồi.

Hình 34 : Minh họa thuật toán nửa phẳng giao nhau.

Hình 35 : Minh họa thuật toán dùng đường quét.

Hình 36 : Hình thang hóa một đa giác đơn.

Hình 37 : Sự tách hình thang.

Hình 38 : Chia đa giác đơn thành các thành phần đơn điệu.

Hình 40 : Minh họa thuật toán điểm trong đa giác.

Hình 41 : Thuật toán đường quét.

Hình 42 : Clipping một cạnh dựa vào nửa phẳng H.

Hình 43 : Minh họa xén đa giác qua 4 bước.