LỜI CẢM ƠN
Trước hết, xin chân thành cảm ơn đến :
Ban Giám Hiệu Trường Đại Học Sư Phạm TP. Hồ Chí Minh. Trong suốt 4
năm học tại trường, Ban Giám Hiệu đã tạo mọi điều kiện tốt để em có thể
học tập, trau dồi thêm kiến thức cho mình.
Ban chủ nhiệm Khoa Toán – Tin Học.
Toàn thể quí thầy cô thuộc tổ bộ môn Tin, đã tận tình giảng dạy những kiến
thức chuyên môn cho em. Đó là những kiến thức nền tảng giúp em vững
bước trên con đường học tập và nghiên cứu sâu hơn về chuyên môn sau này.
Xin chân thành cảm ơn đến : Thầy Ngô Quốc Việt, người đã trực tiếp cung cấp đề
tài và hướng dẫn thực hiện đề tài này.
Và cuối cùng, xin cảm ơn đến những người bạn của tôi. Những người đã trao đổi,
đóng góp, phê bình và động viên tôi trong thời gian thực hiện đề tài này.
1
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

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
3
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
4
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 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
2
: (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
i
, (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.
6
Chương 1
GIỚI THIỆU VỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN
1.1 Hệ quản trị cơ sở dữ liệu

và quy trình kiến thức chuyên gia, nơi tập hợp các quy định, quy phạm, tiêu
8
Hệ quản trị
CSDL
Trình ứng dụng Truy vấn
Bộ quản lí
dữ liệu
Bộ xử lí
truy vấn
Bộ quản lí
tệp (hệ điều
hành)
CSDL
chuẩn, định hướng, chủ trương ứng dụng của nhà quản lý, các kiến thức
chuyên ngành và các kiến thức về công nghệ thông tin.
1.2.2 Các thuật ngữ trong các ứng dụng GIS
1.2.2.1 Theme (chủ đề)
Trong GIS, những thông tin địa lý không gian tương ứng với một chủ
đề riêng biệt thì được hình thành trong một theme. Một theme giống như
một mối quan hệ được định nghĩa trong mô hình quan hệ, nó gồm một lược
đồ với những mô tả. Những con sông, những thành phố, những quốc gia,…
là những ví dụ về theme.
1.2.2.2 Map (bản đồ)
Khi một theme được biểu thị trên giấy hoặc trên màn hình máy tính
thì những gì mà chúng ta thấy gọi là một bản đồ (map) với những màu sắc, tỉ
lệ, những sự kiện,…Bản đồ địa hình, bản đồ xe lửa, bản đồ thời tiết là những
mẫu bản đồ mà chúng ta hay thấy.
Hình 2 : Một bản đồ Việt Nam
9
1.2.2.2 Đối tượng địa lý (Geographic Objects)

i
A
 theme), trong đó p
i
A
là một thuộc tính
trên tập thuộc tính mô tả của theme. Phép chọn theme kí hiệu là
σ
Ai
p
(T).
Hình 4 : Minh họa phép chọn
1.3.3 Phép hợp theme (Theme Union)
Hợp của hai theme (theme x theme  theme) là hợp của các đối tượng địa
lý có lược đồ quan hệ giống nhau. T
1
và T
2
là kí hiệu của hai theme thì hợp
của chúng là T
1


T
2
.
11
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).
12

14
Hình 9 : Merger
1.4 Hệ quản trị cơ sở dữ liệu hỗ trợ cho cơ sở dữ liệu địa lý không gian
Hệ quản trị cơ sở dữ liệu quan hệ :
Những đặc trưng chính :
• Các theme được trình bày bằng các bảng quan hệ. Một đối tượng địa
lí là một bộ (một dòng) của quan hệ, mỗi cột là một thuộc tính.
• Các thuộc tính có kiểu chữ số (chuỗi và số).
• Có ngôn ngữ truy vấn SQL.
Xét theme Country với các thuộc tính được cho trong bảng quan hệ sau cùng
với các bảng liên quan với Country :
Country
Boundary
Name Capital Populatio
n
Id-boundary
Germany
France
…
Berlin
Paris
…
78.5
58
…
B1
B2
…
Id-boundary Id-contour
B1

…
P1
P2
P3
…
P4
P5
…
…
Id-point X Y
P1
P2
P3
P4
P5
…
452
365
386
296
589
…
1000
875
985
825
189
…
16
Hình 10 : Biểu diễn quan hệ giữa các quốc gia

phân biệt được là thuộc tính cơ bản trong khái niệm thực thể.
Đối tượng của mô hình thực thể :
• Điểm : Điểm được sử dụng để biểu diễn vị trí của thực thể mà không
phụ thuộc vào hình dạng của nó. Ví dụ như thành phố, nhà thờ,… là
những thực thể có thể được xem như là một điểm trên bản đồ.
• Đối tượng tuyến tính : Loại hình học cơ bản mà ta xét là đường gấp
khúc (polyline). Một đường gấp khúc là một tập hợp các đoạn thẳng
nối với nhau, mỗi điểm nối là đỉnh chung của hai đoạn, trừ hai điểm
ngoài cùng là chỉ thuộc về một đoạn. ta có các loại đường gấp khúc
sau :
Đường gấp khúc khép kín là đường gấp khúc có hai điểm ngoài cùng
trùng nhau.
Đường gấp khúc đơn là đường gấp khúc không có hai đoạn không
liên tiếp giao nhau.
Đường gấp khúc là đơn điệu đối với đường L nếu mỗi đường L’ trực
giao với L gặp đường gấp khúc tại tối đa một điểm.
18
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.
• Đối tượng bề mặt (surfacic objects) : Dùng để biểu diễn thực thể có
diện tích lớn. Đa giác là loại hình chính ta nghiên cứu. Một đa giác là
một miền được bao bởi một đường gấp khúc khép kín. Ta có các loại
đa giác sau :
Đa giác là đơn nếu đường biên của nó là một đường gấp khúc đơn.
Đa giác P là đa giác lồi nếu hai điểm bất kì A, B thuộc P thì đoạn AB
cũng nằm trong P.
Đa giác đơn điệu là giác đơn mà đường biên của nó có thể tách ra
thành hai đường gấp khúc đơn điệu. Tính đơn điệu của đa giác thường
đối với trục tọa độ.
Hình 12 : (a) Đa giác đơn; (b) Đa giác không đơn; (c) Đa giác lồi; (d)

Hình 15 : Biểu diễn đa giác P bằng các pixel.
2.2.2 Phương thức Vector
Trong phương thức vector, một điểm được biểu diễn bằng cặp tọa độ của nó.
Đối tượng tuyến tính và đối tượng bề mặt thì được biểu diễn bằng cấu trúc
của cách biểu diễn điểm như danh sách, tập hợp, mảng.
Biểu diễn dữ liệu trong mô hình thực thể bằng phương thức vector :
• Đường gấp khúc được biểu diễn bằng một danh sách các điểm <p
1
,
…,p
n
>, trong đó p
i
là đỉnh, cặp (p
i
,p
1+i
) với i<n, là một cạnh.
• Đa giác cũng được biểu diễn bằng một danh sách các điểm, nhưng
danh sách biểu diễn đó là một đường gấp khúc khép kín, nghĩa là cặp
(p
n
,p
1
) cũng là một cạnh của đa giác.
• Một miền (region) thì được biểu diễn bằng tập các đa giác.
Kí hiệu cặp bằng []; danh sách bằng <>; tập hợp bằng {}. Ta có cấu trúc
biểu diễn của điểm, đường gấp khúc, đa giác và miền như sau :
Point : [x: real, y: real]
Polyline : < point >

d
+ a
1+d

≤
0
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.
2.3 Biểu diễn hình học của tập các đối tượng
2.3.1 Mô hình Mạng
22
Trong mô hình mạng, có hai khái niệm mà chúng ta cần đề cập đến : Đó là
các Nút (Nodes) và các Cung (arcs) của một mạng.
Một nút là một điểm mà nó nối các cung của mạng với nhau.
Một cung là một đường gấp khúc mà nó bắt đầu bằng một nút và kết thúc
bằng một nút.
Hình 18 : Minh họa mô hình mạng
Như vậy, ta có hai loại điểm : Điểm chính quy và Nút
Điểm cuối của cung và các điểm cô lập trong mặt phẳng gọi là nút.
Đỉnh của đa giác và chóp của đường thẳng gọi là các điểm chính quy.
Dựa vào các khái niệm trên, chúng ta có hai loại mô hình mạng : mạng
phẳng (planar network) và mạng không phẳng (nonplanar network).
Trong mạng phẳng, mỗi giao điểm của cạnh được xem là một nút. Mỗi nút
đó không tương ứng với một thực thể hữu hình trong thế giới thực.
Trong mạng không phẳng, các cạnh có thể ngang qua nhau mà không có các
giao điểm.
Chúng ta có cách biểu diễn các đối tượng trong mô hình mạng như sau :
• Point : [x: real, y:real]
• Node : [point, <arc>]
23

, P
2
, < > ]
N
1
: [ [3,0], < a, f, e >]
P
1
được biểu diễn bằng danh sách các arc a, b, f.
P
2
được biểu diễn bằng danh sách các arc c, d, e, f.
f được biểu diễn bằng một nút đầu (node-start) N
1
, nút cuối (node-end) N
2
,
đa giác trái (left-poly) P
1
, đa giác phải (right-poly) P
2
và một danh sách
điểm là rỗng.
N
1
được biểu diễn bằng điểm [3,0] và một danh sách các arc là a, f, e.
25